코딩테스트

문제 제출안

\--> 시간 초과를 받는다. insert를 쓰면 시간이 많이 초과됨

정답

정답

from collections import dequeimport sysN = int(input())list = deque()for i in range(N): a = sys.stdin.readline().split() if a0 == 'push_front':

파이썬으로 코딩테스를 준비하는 사람이라면 math라이브러리를 사용해서 답을 쉽게 찾을 수 있지만, gcd = 최대 공약수 , lcm = 최소 공배수라는 것을 꼭 기억하고 있자

소수: 숫자 중 본인과 1로만 나누어지는 숫자, 1은 아님

풀이: 대표적인 다이나믹프로그래밍 문제라고 볼 수 있다.bottom_up방식을 사용했고, 다이나믹프로그래밍은 기존에 했던 연산을 다시 하지 않게 하기 위함이 강하므로 dp 배열을 만들어주는 것이 좋다.

타일을 채우면서 21 12가 있으니 한칸을 채울때와 두칸을 채울때를 나눠서 계산하면 된다.늘 다이나믹 프로그래밍은 경우의 수를 생각해보면서 규칙을 정하면 된다.

2\*N 타일 문제와 동일하게 앞에서부터 경우의 수를 생각해준다. 더해야 하는 것이 1,2,3 밖에 없으니 본인보다 각각 1,2,3만큼 적은거의 합들과 똑같다.

업로드중..

이 문제 또한 쉬운계단 수 처럼 뒤의자리가 각각 0과 1로 끝나는 경우의 수를 찾으면 된다. 0으로 끝나는 수는 앞의자리에서 0과 1로 끝나는 수의 합과 같고 , 1로 끝나는 경우의 수는 0에서만 올 수 있기때문에 앞의자리의 0의개수와 같다

각 수열 순서대로 추가했을시 수열의 크기를 정하면 된다.예를 들어 첫번째 10을 추가하는 경우는 수열의 크기가 1, 그 다음 20을 추가하는 경우는 그 전에 리스트에서 나보다 작은 숫자 중 가장 큰 수열의 크기에서 +1을 하면됨

기존 가장 긴 증가하는 부분 수열과 앞에 쪽 풀이는 같다.대신 이번에는 수열도 포함해야하는데, 기존 답이었던 x = max(d)로 두고 array의 반대부터 내려오면서 리스트에 추가해준다.

앞에서 가장 긴 수열을 고르는 것처럼 해당 숫자를 선택했을때와 안했을때로 나눠준다. 앞에서 계속 더해나가면서 만약 합이 0보다 작아지면 그 뒤의 숫자와 더하면 -인 부분이니깐 합이 0보다만 크면 숫자는 계속 커질 수 있다.

업로드중..

해당 문제는 브루트포스 문제로 모든 결과를 해보는 것이다. 9명중 7명이 선택되는 모든 경우의 수를 선정해서 합의 100이 되는 결과를 보여주면 되는 것이다.

풀이를 보면 굉장히 단순하지만 이걸 생각해내기가 어렵다.브루트포스(모든 가능한 경우의 수를 넣어보는 무식한 방법)으로 풀 수 있고, 입력된 값들을 뺀 값의 나머지들의 전부 0인 경우가 해당 년도인 것을 알아차려야 풀 수 있었다.

정답

이 문제 또한 브르투포스로 모든 가능성에 대해서 해보아야한다. 모든 숫자 중 한개씩 빼내어서 부러진 숫자가 존재하면 빼고 부러진 숫자없이 도달했다면 최솟값을 넣으면 된다.

N개중에 몇개를 고르는 방식 잘 기억해서 사용하기

해당 부분을 다 1로 채워주면 겹치는 부분을 감안해도 그 넓이만 나온다.

색종이-1과 다르게 변을 구하는 문제이다. 전치행렬을 이용해서 0,1이 바뀌는 순간을 구하면됨

풀이방법은 이전 색종이 문제들과 똑같이 순서에 맞게 해당 번호를 채워주면 된다. 하지만 숫자를 찾을때 방법이 여러가지가 있는데 이번엔 빈도수 배열을 선언해줘서 해보았다.

순열을 통해 쉽게 풀 수 있다.

Temp Body

어노테이션을 클래스에 선언하면 그 클래스는 JPA가 관리한다. 그러므로 DB의 테이블과 Class(VO, DTO)와 맵핑한다면 반드시 @Entity를 붙여주어야 한다.@Entity가 붙은 클래스에는 다음 제약사항이 필요하다.필드에 final, enum, interfac

주어진 배열로 만들 수 있는 모든 순열을 만들고(브루트포스) 그 배열의 연속합이 가장 큰 것을 찾아주면 되는 문제

특정 경로를 지나가는 외판원 문제는 유명한 문제이다. dfs를 통해 풀 수 있고, 넣어줘야하는 값과, 백트래킹 해주는 부분이 많이 어렵게 느껴졌다. 반복적인 풀이를 통해 감을 잡아야겠다.

dfs를 통해서 풀었고 많이 봐왔던 순열 문제이다. N과 M(2)처럼 for문의 시작부분만 손을 대주면 쉽게 풀 수 있다.

들어가는 학생의 앞에 들어가는 학생보다 큰 학생의 수를 구하면 된다

달팽이 문제와 똑같이 방향을 지정해주고, 만약 범위를 벗어나거나 해당 그래프에 값이 차있다면 방향을 전환해주면서 채워주면 된다. 풀이에서는 범위 체크 안하기 위해서 1로 둘러쌌다.

똑같이 순열문제처럼 풀어주되, 만들어진 순열에 모음이 들어가 있다면 모음+1 안들어가있다면 자음+1을 해서 조건에 맞는 것만 출력해주도록 한다

해당 날짜를 선택할때와 안할때를 나눠준다.\->dp로도 풀 수 있는 문제이기 때문에 풀어보자

기존에 비슷한 문제를 풀지 않았으면 조금 난해한 문제이긴하다. 각팀에 넣을때 안넣을때를 전부 비교해서 푸는 문제이다.

사실 문제의 정확한 의도가 무엇인지 찾기가 힘들었던것 같다. 예시와 같이 친구가 5명 이상 한줄로 이어지는 경우를 찾으면 되는 답이어서 dfs를 이용해서 풀었다.

무방향 그래프는 bfs를 통해 풀면 쉽게 풀린다.또한 입력이 많은 경우에는 input() 대신 sys.stdin.readline()을 사용하자

처음 본 이 문제는 나에게 매우 까다로운 문제였다. 풀이 방법은 bfs로 돌면서 본인과 연결되어 있는 노드에 대해서 다른 그룹으로 지정해주고, 돌다가 본인과 연결되어 있는데 같은 그룹으로 속해있으면 False를 반환해주면 된다.

dfs 통해서 연결되어 있는것끼리 방문을 했고, 만약 연결되어 있다면 숫자를 동일한걸로 바꿔주었다.

기존에 풀던 dfs만 잘 활용하면 되서 간단한 문제이지만, python3로 푸니 런나임에러, pypy3에서만 정답처리 되었다. 아마 하나하나 dfs로 설정해주어서 그런것 같은데 좀 더 클린코딩하는 방법도 추후에 추가해야겠다.

최단경로를 풀때, 다익스트라, 플루워드워셜도 있지만 이렇게 2차원그래프로 주어진 경우에는 bfs를 통해 많이 풀도록 한다.

bfs를 활용해 넣을 수 있는 수를 넣었다. 이때 visited를 list가 아닌 set으로 하니 문제가 풀렸다.

기존에 풀던 방식으로 bfs를 사용하면서 본인의 나왔던 부모루트를 저장하면서 풀어주면 된다.

괄호와 비교하여 모든 값을 넣어보면 된다.

풀이 nqueens처럼 해당 가로, 세로 부분이 다 다른지 확인해주면 된다

visited배열을 사용할때는 append로 추가하지말고 false True로 할 수 있게 하자.

파이썬에서 알파벳에 관련된 visited처리시에는 ord()를 적극 이용해야한다.

이미 방문한 번호에 대한 처리를 해주어야 시간초과 및 메모리 초과를 해결할 수 있다.주사위대로만 가는경우, 뱀에 걸리는 경우, 사다리 통해 가는 경우를 다 넣어주어야한다.

크게 어려울 것 없이 기본적인 bfs방식의 풀이이다

기존 풀이 방법:시간초과가 떴고, L과 R을 문자로 바꾸고 하다보니 아무래도 시간이 초과가 난 거 같다기존 풀이:정답풀이:수학적인 방법으로 바꿔주니, 다행히 정답처리가 되었다.

Ref : https://mangkyu.tistory.com/95WAS와 WS의 차이WAS(Web Application Server) \- 비즈니스 로직을 넣을 수 있음.tomcat, php, ASP, .Net등WS(Web Server) \- 비즈니스 로직

https://www.acmicpc.net/problem/14502벽을 임의로 3개 세우는 함수에는 dfs를 전이 시키는 함수에는 bfs를 사용해서 풀었다. 이때 참고할 점은 dfs부분에서 넣어준 함수가 bfs 실행 이후에도 같아야 하기 때문에 temp_arr

처음엔 dfs 방식으로 벽 하나씩 1을 모두 바꿔주는 방식으로 풀이를 했고, 당연히 시간 초과가 떴다.다음으로 푼 방식은 visited배열과 큐에 벽 부수는 횟수도 추가시켜 3차원 배열을 통해 문제를 풀어주었다. 3차원 배열을 생각해내는게 쉽지 않았다.

벽부수고 이동하기 -1 에서 부술 수 있는 벽의 개수만 지정해주면 금방 풀 수 있는 문제.배운점1) visited함수의 3차원 선언2) 리스트 sys선언

전형적인 그리디 알고리즘이다. 종료시간이 빨라야 최대한 많은 회의를 잡을 수 있다는 것을 알면된다.

풀이 dfs를 통해 쉽게 풀 수 있으나, 답이 계속 오류가 떴다. 그 이유는 max값이 음수가 나올 수도 있는데, 처음에 max = 0으로 지정해줘서 뜨는 오류

풀이 bfs를 활용해서 풀었고, 현재 1로 되어있는 부분만 q에 넣는다. 이후 인접한 과일들을 먼저 +1씩해주고 가장 큰 숫자를 출력

그리디 알고리즘으로 풀 수 있는 매우 쉬운 문제이다. sort()를 통해 크기순으로 세워주고 그의 합을 지속적으로 구해주면 된다.

풀이 방법을 생각하기 쉽지 않았다.각 행을 돌면서 같지 않는 부분이 있으면 전환해준다. 이때 전환은 함수를 이용해서 작성해준다.각 행을 다 돌았는데 리스트가 동일하지 않는 경우도 확인해준다.

그리디 알고리즘이라 하면 가장 큰 것부터, 가장 작은 것부터 이런 식으로 단순하게 생각했다. 그러나 난이도가 올라갈 수록 최적의 해를 찾는 것 또한 그리디의 일부라는 것을 알게 되었다. 이 문제에서 바꿔줄지 말지를 결정하는 것이 최적의 해고 , 또한 경우의 수도 생각해

가장 긴 증가하는 수열(LIS)는 기존풀이 방식(dp)과 이분탐색으로 풀어볼 수 있다.문제와 같이 크기가 큰 수열은 시간초과가 뜨기 때문에 시간 복잡도가 O(nlog n)인 이분탐색을 사용해야한다.

이진탐색을 활용해 문제를 풀어준다. 이때 count()함수를 따로 만들어 생기는 전선의 갯수를 리턴하고 가장 큰 라인의 절반 값부터 1씩 줄어들게 만들어 값을 구한다

유명한 냅색 알고리즘을 통해서 dp 를 활용해 풀어주어야한다.

union, find 함수를 이용해 연결된 부모 찾기를 통해 풀어주었다. 그러나 RecrusionErrorr가 떴는데 재귀 깊이 제한을 풀어주어야한다고 한다.import syssys.setrecursionlimit(1000000)

1차원 배열에서 연속된 배열이나 특정 값을 구하는 문제에서는 투포인터를 사용해서 시간복잡도를 줄일 수 있다.

먼저 주어진 n보다 작거나 같은 소수들을 리스트로 만들어주고 투포인터로 찾아주면 간단하게 풀린다.

해당문제는 bfs문을 짜는데는 어렵지 않지만 가지치기 즉 시간을 줄이는 곳에서 고민이 필요하다.

말처럼 이동하는 부분과 변사이를 이동할때를 두개 다 넣어주되, k번을 넘지 않도록 해준다.k번 넘은 여부는 이전에 벽 부수고 이동하기 처럼 visited배열을 3차원으로 만들어줘서 넘은 여부를 확인해준다.3차원 배열 기억하기 -> \[\[False \* (k+1) fo

처음에 dfs를 통해 바이러스가 들어갈 자리를 구하다가 시간초과가 나서 파이썬 라이브러리 combination을 통해서 풀어주었다. 해결과정에서 선택되지 않은 바이러스를 놓을 수 있는자리를 어떻게 처리할까 싶어서 바이러스가 놓인 자리를 3으로 만들어주고 그 외에 바이러

처음에는 bfs로 푸려고 했으나 당연히 메모리 및 시간 초과... 배열의 크기가 클때는 완전탐색은 하지말자 ㅠㅠ...다이나믹 프로그래밍을 사용하는 경우를 정리를 잘 해놔야할 것 같다. 배열의 크기가 크고 누적값을 구하거나 기존 값의 영향을 받는거면 사용한다!그래서 다이