[백준] 11722번 - 가장 긴 감소하는 부분 수열 (한줄평) LIS 알고리즘을 알면 쉽게 풀 수 있었던 문제! 유사 문제: 11053, 11054 https://hseungyeon.tistory.com/304 [다이나믹 프로그래밍] ▲ 11053번 - 가장 긴 증가하는 부분 수열 [백준] 11053번 - 가장 긴 증가하는 부분 수열 (한줄평) 풀었던 문제지만 다시 풀려니 기억이 잘 안나서 어려웠던 문제.. 꼭 복습이 필요하다!!! 풀이 시간: 30분 이내 유사 문제: https://hseungyeon.ti hseungyeon.tistory.com https://hseungyeon.tistory.com/305 [다이나믹 프로그래밍] 11054번 - 가장 긴 바이토닉 부분 수열 [백준] 11054번 - ..
[이코테] 예제1 - 피보나치 수열 (한줄평) 다이나믹 프로그래밍의 대표적인 예제로 어렵지 않게 풀 수 있는 문제 (풀이1) 단순 재귀 풀이 시간: 1분 이내 1) 문제 해결 아이디어 단순 재귀 함수로 구현했을 때 시간복잡도는 O(2**n)이다. 이미 계산한 것에 대해 호출할 때마다 또 계산을 하기 때문에 n이 커질수록 수행 시간이 기하급수적으로 늘어나는 문제가 있다. 예를 들어, f(6)을 호출할 때 f(3)이 3번이나 호출된다. f(100)이라면 어마어마한 연산을 수행하는데 수백억년이 넘어간다. 2) 소스코드 # 1. 피보나치 수열(단순 재귀) def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2) print(fibo(4..
[이코테] 예제4 - 계수 정렬(Counting Sort)(174p) 풀이 시간: 5분 이내 1) 문제 해결 아이디어 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 떄만 사용할 수 있지만 매우 빠른 정렬 알고리즘(데이터의 개수: n, 최댓값: k) 평균 시간 복잡도: O(n + k) 공간 복잡도: O(n + k) 2) 소스코드 # 계수 정렬(Counting Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] count = [0] * (max(array) + 1) # 모든 범위를 포함하는 리스트 # 오름차순 정렬 for i in array: count[i] += 1 for i in range(len(count)): for j in rang..
[이코테] 예제1 - 선택 정렬(Selection Sort)(159p) 풀이 시간: 10분 이내 1) 문제 해결 아이디어 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복 (최솟값을 맨 앞에 있는 값과 바꾸고 그 다음 최솟값을 앞에서 2번째 값과 바꾸는 과정을 반복) 평균 시간 복잡도: O(n**2) 공간 복잡도: O(n) swap: 리스트에서 두 변수의 위치를 변경하는 작업 파이썬에서는 간단하게 swap를 할 수 있음(tmp 사용할 필요X) arr = [1, 2, 3, 4, 5] # 0번째 & 1번째 값 서로 바꾸기 arr[0], arr[1] = arr[1], arr[0] 2) 소스코드 # 선택 정렬(Selection Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] #..
[백준] 2331번 - 반복수열 풀이 시간: 20분 이내 1) 문제 해결 아이디어 이 문제는 설명에 나와있는대로 구현을 하면 되는 문제였다. 아이디어만 쉽게 떠올리면 금방해결되는 문제! D[1] = A D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합 위와 같은 연산을 반복했을 때 만들어지는 수열에서 반복되는 부분을 제외한 수들의 개수를 구하는 것이다. 반복이 시작되는 지점의 인덱스를 찾아 그 인덱스를 출력시켜주면 된다. 여기서 중요한 점은 연산을 해서 현재 만들어낸 값(num)이 수열(d)에 있다는 조건을 최초로 만족할 때 그 값(num)이 반복이 시작되는 값이 된다는 것이다. 그러므로 반복이 시작되는 값의 인덱스(start)를 찾으면 정답이다. 2) 소스코드 a, p = map(int..
[백준] 10451번 - 순열 사이클 풀이 시간: 20분 이내 매번 위치벡터를 이용한 DFS/BFS문제를 풀다가 오랜만에 그래프 문제를 만나 평소보다 조금 시간이 걸리긴 했지만 쉽게 풀 수 있는 문제였고 DFS, BFS 중 편한 방식으로 풀면 된다. 이 문제의 경우 메모리, 시간 측면에서 모두 DFS로 푸는 것이 더 효율적인 결과가 나왔기 때문에 DFS로 푸는 것을 추천한다. (풀이1) DFS 1) 문제 해결 아이디어 2) 소스코드 t = int(input()) # 테스트 케이스 수 # DFS def dfs(v): visited[v] = True # 현재노드 방문처리 nv = graph[v] # 인접 노드 # 아직 방문하지 않은 노드라면 dfs 호출 if not visited[nv]: dfs(nv) fo..
