편집 시간: 2022년 3월 2일 오후 10:30 코드 Algorithm/12100.py at main · Junroot/Algorithm 풀이 bfs를 이용해서 모든 경우를 탐색하여 최대값을 구했다. 특정 방향으로 숫자를 합칠 때, 이미 한 번 합쳐진 숫자는 합쳐지지 못하는 점을 주의해야된다. 이를 해결하기위해, 루프를 돌면서 자신과 그 뒤에 있는 숫자가 같은 경우는 두 수를 합치고 index를 2만큼 늘리도록 구현을 했다. index_of_numbers = 0 while index_of_numbers < len(numbers) - 1: if numbers[index_of_numbers] == numbers[index_of_numbers + 1]: new_column.append(numbers[index_of_numbers] * 2) index_of_numbers += 1 else: new_column....
오답 여부: o 편집 시간: 2022년 4월 8일 오후 6:19 코드 Algorithm/1208.py at main · Junroot/Algorithm 풀이 평범하게 모든 수열의 경우의 수를 다 구하면 $2^{40}$이므로 시간 초과가 발생할 것이다. 처음에는 dp같은 방법으로 접근하였으나 중복되는 경우가 없기 때문에 효과가 없었다. 결국 답을 찾아봤는데, 수열을 절반으로 나누어 왼쪽과 오른쪽에서 나올 수 있는 합을 각각 따로 구하여 합이 될 수 있는 것을 찾으면 $2*2^{20}$이므로 제한 시간안에 해결할 수 있다. 시간 복잡도가 O($2^{n}$) 같이 제곱 수준일 때는 n의 크기를 절반으로 줄이는 것만(O($2^{{n \over 2}}$))으로도 큰 최적화가 될 수 있다는 것을 확인할 수 있었다....
편집 시간: 2022년 3월 30일 오후 10:05 코드 Algorithm/1202.py at main · Junroot/Algorithm 풀이 담을 수 있는 무게가 작은 가방부터 담으면서, 가방이 담을 수 있는 보석 중에 가장 가치가 높은 보석을 담으면 된다는 것을 알 수 있었다. 다음 가방으로 넘어가면서 앞에서 사용한 보석을 빼고 그 중 가치가 가장 높은 보석을 찾는 방식으로 구현하면 됐다. 이 과정에서 가장 높은 가치를 계속 찾아야되기 때문에 우선순위 큐를 사용했다. 다른 사람 풀이 보석의 정렬을 더 빠르게 하는 방법이 있었다....
오답 여부: o 편집 시간: 2022년 3월 14일 오후 2:58 코드 Algorithm/12015.py at main · Junroot/Algorithm Algorithm/12015-2.py at main · Junroot/Algorithm 풀이 잘못된 풀이 11053 기존에 이 문제에서 수열의 크기가 1000000으로 늘어났다. 즉, nlogn으로 풀어야된다는 뜻이다. 기존문제에서 dp를 사용해서 O(n^2)였는데 dp를 빠르게 구하기 위해서 수열의 크기가 큰것부터 비교하기위헤 우선순위 큐를 사용했다. 하지만 이는 최악의 경우 O(n^2logn)으로 오히려 더 느려진다는 문제가 있었다. 맞는 풀이 완전히 다른 방법으로 접근해야되었다. 그리디 + dp + 바이너리서치를 사용해야되는 문제다....
오답 여부: o 편집 시간: 2022년 3월 14일 오후 7:59 코드 Algorithm/12015.py at main · Junroot/Algorithm Algorithm/12015-2.py at main · Junroot/Algorithm 풀이 잘못된 풀이 11053 기존에 이 문제에서 수열의 크기가 1000000으로 늘어났다. 즉, nlogn으로 풀어야된다는 뜻이다. 기존문제에서 dp를 사용해서 O(n^2)였는데 dp를 빠르게 구하기 위해서 수열의 크기가 큰것부터 비교하기위헤 우선순위 큐를 사용했다. 하지만 이는 최악의 경우 O(n^2logn)으로 오히려 더 느려진다는 문제가 있었다. 맞는 풀이 완전히 다른 방법으로 접근해야되었다. 그리디 + dp + 바이너리서치를 사용해야되는 문제다....
편집 시간: 2022년 3월 1일 오후 7:11 코드 Algorithm/1197.py at main · Junroot/Algorithm 풀이 프루스칼 알고리즘을 이용해서 문제를 해결했다. 정점의 개수가 최대 10000개이므로 프림 알고리즘도 가능하다.
편집 시간: 2022년 2월 7일 오후 8:55 코드 Algorithm/11866.py at main · Junroot/Algorithm 풀이 큐를 이용하면 쉽게 해결할 수 있다.
편집 시간: 2022년 1월 31일 오후 6:08 코드 Algorithm/1181.py at main · Junroot/Algorithm 풀이 기본적인 정렬 알고리즘을 사용하면된다.
편집 시간: 2022년 2월 9일 오후 6:26 코드 Algorithm/11726.py at main · Junroot/Algorithm 풀이 2xn 타일을 놓을 수 있는 경우의 수를 f(n)이라고 했을 때, f(n) = f(n-1) + f(n-2) 라는 점화식을 발견할 수 있으면 된다. 마지막에 1x2 타일을 놓는 경우가 f(n-1), 2*1을 두 개 놓는 경우가 f(n-2)기 때문이다.
편집 시간: 2022년 2월 24일 오후 2:52 코드 Algorithm/11725.py at main · Junroot/Algorithm 풀이 트리의 루트가 1이라 했기때문에, 1부터 시작하는 bfs로 탐색하면된다. 현재 노드에서 이웃하는 아직 방문하지 않은 노드들이 현재 노드의 자식 노드가 된다.
편집 시간: 2022년 2월 12일 오후 9:37 코드 Algorithm/11724.py at main · Junroot/Algorithm 풀이 1부터 n까지 노드를 확인하면서 새로운 노드를 만날 때마다 bfs로 탐색을 한다. 이렇게 bfs를 한 개수를 구하면 된다.
편집 시간: 2022년 2월 12일 오후 9:56 코드 Algorithm/11723.py at main · Junroot/Algorithm 풀이 x값이 1이상 20이하이므로 길이가 21인 bool 리스트를 만들면 쉽게 해결할 수 있다. 이 때, print()를 사용하면 메모리 초과가 발생하는 문제가 있어서 sys.stdout.write() 를 사용했다.
편집 시간: 2022년 2월 24일 오후 3:15 코드 Algorithm/1167.py at main · Junroot/Algorithm 풀이 1967 위와 같은 문제다.
편집 시간: 2022년 2월 24일 오후 3:10 코드 Algorithm/11660.py at main · Junroot/Algorithm 풀이 Summed-area table을 이용하면 O(n^2)만에 해결이 가능하다.
편집 시간: 2022년 1월 31일 오후 6:09 코드 https://github.com/Junroot/Algorithm/blob/main/backjoon/11650.py 풀이 기본적인 정렬 알고리즘을 사용하면 된다.
편집 시간: 2022년 2월 16일 오후 4:10 코드 Algorithm/1149.py at main · Junroot/Algorithm 풀이 모든 경우의 수를 다 구해보는 방법 밖에 없다. 함수 f(index, last_color)를 만들어 함수를 아래와 같이 정의한다. f(index, last_color): index번째 집이 last_color를 사용하지 못할 때 최소 index부터 n번째 집까지 칠하는데 최소 비용 그러면 아래와 같은 점화식이 만들어진다. f(index, last_color) = min( (index번째 집의 color1 비용) + f(index + 1, color1), (index번째 집의 color2 비용) + f(index + 1, color2) )...
오답 여부: o 편집 시간: 2022년 2월 24일 오후 6:17 코드 Algorithm/11444.py at main · Junroot/Algorithm 풀이 처음에 n의 범위를 보고 피보나치 수의 일반항을 이용하는 문제인 줄 알았으나, n이 굉장히 클 때 부동소수점의 값이 잘못될 수도 있다는 사실을 뒤늦게 알게되었다. 행렬의 제곱을 이용하면 O(log n) 만에 해결이 가능하다.
편집 시간: 2022년 2월 24일 오후 2:39 코드 11404번: 플로이드 풀이 정석적인 플로이드 워셜 알고리즘 문제다.
편집 시간: 2022년 2월 9일 오후 6:23 코드 Algorithm/11399.py at main · Junroot/Algorithm 풀이 최소값을 구하기 위해서는 작은 수 순서대로 큰 수에 곱해져야된다. 증명은 따로 하지 않겠다.
편집 시간: 2022년 2월 12일 오후 9:43 코드 Algorithm/11279.py at main · Junroot/Algorithm 풀이 1927 와 풀이가 같다.