jae_coding

문제 문제 링크 문제 접근 DFS - 모든 노드를 방문하고 싶을 때 사용한다. - Root node를 시작으로 다음 분기까지 넘어가기 전에 완전히 탐색하는 것!! - 한 방향으로 계속 탐색을 하다가 더 이상 탐색할 수 없을 때, 갈림길로 돌아와 완전히 탐색한다. - 어떤 노드를 방문했었는지 여부를 반드시 확인해야한다. BFS - Root node를 시작해서 인접한 노드를 먼저 탐색하는 방법 - 시작점에서 가장 가까운 점을 먼저 방문한다 -> 최단 경로나 임의의 경로를 찾고 싶을 때 사용한다 - 재귀적으로 동작하지 않으며, queue를 이용하여 반복적 형태로 구현한다. 코드 import sys from collections import deque # N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작..

문제 문제 링크 문제 접근 DP를 이용하여 제곱수가 N보다 작은 자연수보다 작거나 같게하여 최소한의 제곱수를 사용한다. 코드 import sys N = int(sys.stdin.readline()) dp = [i for i in range(N+1)] for i in range(1, N+1): for j in range(1, i): if pow(j, 2) > i: break if dp[i] > dp[i - pow(j, 2)] + 1: dp[i] = dp[i - pow(j, 2)] + 1 print(dp[N]) 느낀점 루프 안에 조건 문을 합쳐서 깔끔하게 만들어 보려고 했으나 그것은 실해했다. break로 루프를 빠져 나가야 시간 초과가 뜨지 않는다. 이 부분에 대하여 아시는 분 계시다면 댓글 남겨주시면 감..

문제 문제 링크 문제 접근 바이토닉 부분 수열이라는 것은 예를 들어 1 2 3 4 5 4 3 2 1 등과 같이 오름차순으로 정렬되었다가 내림차순으로 정렬이 된 수열 일컷는다. 바이토닉 수열은 이전에 구현한 가장 긴 증가하는 부분수열을 이용하는 것이다. 가장 긴 증가하는 부분 수열 알고리즘과 기존 수열의 reverse한 후 가장 긴 증가하는 부분 수열 알고리즘 결과 값을 더한 후 + 1을 해주면 된다. 코드 import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [0] * N for i in range(N): for j in range(i): if seq[i] > seq[j]: dp[i] ..

문제 문제 링크 문제 접근 이분 탐색과 dp를 이용하여 문제를 풀어야 한다. 이분 탐색은 bi_sects를 구현하는 것을 이용한다. dp를 tuple을 통하여 value와 idx로 넣어서 이용한다. start가 dp의 길이보다 작을 경우에 dp의 이전 idx값을 temp에 추가한다. (이전 idx를 추적하기 위함) 코드 시간 초과 코드 import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [[-1000000001] for _ in range(N)] count = 0 for i in range(N): start = 0 end = len(dp[count]) - 1 while start = ..

문제 문제 링크 문제 접근 이전에 가장 긴 증가하는 수열과 문제 유형이 비슷하지만 dp의 개수만이 아닌 dp의 최대 길이와 dp 내용물을 출력하는 것이다. dp를 우선 구해준 후 dp를 역배열한 후, dp의 최대값을 저장하고 1씩 줄여가면서 같은 값이 있을 때 새로운 리스트에 저장을 해준다. 그리고 리스트를 문자열로 출력해준다. 코드 import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(N): for j in range(i): if seq[i] > seq[j]: dp[i] = max(dp[i], dp[j] + 1) count = max(dp) r..

문제 문제 링크 문제 접근 백준 12015번 과 다른 점은 배열의 값의 범위이다. -1,000,000,000 ~ 1,000,000,000 따라서 dp[0]의 초기 값을 -1,000,000,001로 지정해주어야 한다. 시간복잡도 O(N logN)인 binary search를 사용해야 한다. 코드 import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [-1000000001] for i in range(N): start = 0 end = len(dp) - 1 while start = len(dp): dp.append(seq[i]) else: dp[start] = seq[i] print(len..

문제 문제 링크 문제 접근 백준 11055번 과 다른 점은 N의 range이다. 이점을 잘 생각해야 한다. 1,000 -> 1,000,000 시간복잡도 O(N logN)인 binary search를 사용해야 한다. 코드 시간 초과 코드 (시간 복잡도: O(N^2)) import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(N): for j in range(i): if seq[i] > seq[j]: dp[i] = max(dp[i], dp[j] + 1) print(dp) 통과 코드 ( 시간복잡도: O(NlogN) import sys N = int(sys..

문제 문제 링크 문제 접근 case1: N이 0 또는 1인경우는 0! 또는 1!이므로 1을 출력한다. case2: N 팩토리얼의 수를 구한 후 string타입으로 변경 후 마지막 문자부터 첫번째 문자 순서대로 "0" 인경우 count를 올려준다. 만약 "0"이 아니라면 for문을 빠져나온다. 출력은 count를 하면된다. 코드 import sys N = int(sys.stdin.readline()) num = 1 if N == 0 or N == 1: print(0) else: for i in range(1, N+1): num *= i st = str(num) count = 0 for i in range(len(st)): if st[len(st)-i-1] == "0": count += 1 else: bre..

문제 문제 링크 문제 접근 이 문제는 dp에 대한 개념을 정리하기에 좋은 문제인 듯하다. step1: N과 수열 받아온다. step2: dp의 list를 모두 1로 초기화한다. step3: i번째 수열의 이전 값이 i번째 수열 값보다 크면 dp의 i번째를 dp의 i번째와 이전의 dp보다 큰 값이 있다면 그 값에 +1한 것과 비교하여 높은 것을 dp의 i번째에 넣는다. step4: dp리스트에서 가장 높은 값을 출력한다. 코드 import sys N = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(N): for j in range(i): if array[i] <..

문제 문제 링크 문제 접근 N가지 종류의 동전 -> 가치의 합 K원이 되도록해야한다. 각각의 동전은 몇개라도 사용할 수 있다. 출력: 경우의 수 동전의 종류를 몇가지 사용하는지에 따라 분류한다. (예를들어 3가지면 1가지만 사용했을 경우, 2가지만 사용했을 경우, 3가지를 사용했을 경우를 더한 값이 모든 경우의 수가 된다.) 2차원배열을 사용하면 좋겠지만 메모리 문제로 인하여 1차원 배열을 사용하자 점화식: dp[j] += dp[j-coins[j]] 코드 import sys N, K = map(int, sys.stdin.readline().split()) coins = list() for _ in range(N): coins.append(int(sys.stdin.readline())) coins.sort..