편집 시간: 2022년 4월 7일 오후 6:48 코드 Algorithm/2473.py at main · Junroot/Algorithm 풀이 용액의 수가 최대 5000개이므로 O(N^2)으로 해결될거라고 생각했다. 기존 용액 문제에서 투 포인터로 O(n)만에 해결했으니 투 포인터를 사용하면서 한 번 더 n개를 루프돌아도 되겠다는 생각이 들었다. 그래서 용액 하나를 고정시키고 용액의 산성도가 0개 가까운 정도를 투 포인터를 이용해서 구했다.
편집 시간: 2022년 2월 24일 오후 3:25 코드 Algorithm/2407.py at main · Junroot/Algorithm 풀이 n에 대한 팩토리얼을 계산하면서, n보다 작은 값의 팩토리얼 값들을 배열에 저장해두면 O(n)으로 해결이 가능하다.
오답 여부: o 편집 시간: 2022년 2월 24일 오후 4:04 코드 Algorithm/2263.py at main · Junroot/Algorithm 풀이 포스트오더로부터 부모 노드를 찾고 인오더로부터 왼쪽 자식 노드와 오른쪽 자식 노드를 찾는 것은 쉽게 찾아냈다. 하지만 인오더와 포스트오더의 인덱스를 계산하는데 어려움을 겪었다. 굳이 문자열을 변형하지 않고 인오더의 인덱스와 포스트오더의 인덱스를 함수의 파라미터로 넘기면 헷갈리지 않는다는 것을 다른 사람 풀이를 참고해서 알게되었다.
편집 시간: 2022년 3월 1일 오후 7:13 코드 Algorithm/2252.py at main · Junroot/Algorithm 풀이 위상 정렬을 구현하면 쉽게 해결할 수 있는 문제다.
편집 시간: 2022년 4월 6일 오후 10:23 코드 Algorithm/2239.py at main · Junroot/Algorithm 풀이 단순 브루트로 문제를 풀 수 있다. (스도쿠의 칸수) * (한 칸에 들어갈 수 있는 숫자의 수) * (사용할 수 있는 수 찾는 과정) = 81 * 9 * 9 = 6516 밖에 되지 않기 때문이다.
오답 여부: o 편집 시간: 2022년 2월 24일 오후 2:29 코드 Algorithm/2206.py at main · Junroot/Algorithm 풀이 기본적으로 BFS로 풀면된다. 하지만 방문한 위치를 체크하는 방법에서 어려움을 겪었다. 잘못된 풀이1 처음에는 벽을 부수든 부수지않든 한 번 방문한 위치는 재방문하지 않도록 구현했다. 하지만 어떤 위치에 대해서 기존에는 벽을 부수고 갔지만, 같은 횟수로 이동해서 벽을 부수지 않고 갈 수 있는 방법이 있다면 큐에 담을 필요가 있었다. 잘못된 풀이2 잘못된 풀이1때문에 나는 큐에 담겨있는 것중 거리가 가장 짧고, 거리가 같다면 아직 벽을 부수지 않은 것을 먼저 꺼내서 처리하면 해결될 거라고 생각했다....
오답 여부: o 편집 시간: 2022년 4월 4일 오후 6:27 코드 Algorithm/2166.py at main · Junroot/Algorithm 풀이 여러개의 삼각형으로 나누어서 면적을 합하면 되겠다고는 빠르게 생각해냈다. 하지만 아래와 같은 문제가 있었다. 좌표 3개가 주어졌을 때, 삼각형 면적 구하기 벡터의 외적을 사용할 생각을 전혀못했다. 두 벡터 a, b가 있을 때 두 벡터를 외적한 벡터의 크기는 |a||b|sinθ 라는 것을 완전히 잊고 있었다. 오목 다각형의 경우 삼각형의 면적을 단순히 모두 더해서 반환하면 될거라고 생각했다. 하지만 이는 볼록 다각형의 경우에만 해당한다....
편집 시간: 2022년 2월 7일 오후 8:41 코드 Algorithm/2164.py at main · Junroot/Algorithm 풀이 큐를 이용해서 해결할 수 있다.
편집 시간: 2022년 4월 29일 오후 8:36 코드 Algorithm/21611.py at main · Junroot/Algorithm 풀이 처음에는 구슬 정보를 하나의 리스트로 표현해서 처리해보려고했다. 하지만 이 방법은 블리자드가 일어나는 인덱스를 계산하는데 상당히 복잡해졌다. 두 번째 접근 방법으로 격자를 나타내는 이중 배열에서 문제의 조건들을 처리하도록 구현했다. 이 때 현재 위치에서 다음 위치를 계산하는 과정이 필요했는데 이를 그림으로 그려보니 규칙이 보였다. 이를 수식으로 구한 뒤 다음위치를 찾을 수 있는 로직을 완성했다. 추가적으로 블리자드가 일어난 뒤 중간에 빈 칸이 발생한 것을 앞으로 한칸씩 미는 과정을 굳이 구현할 필요가 없다....
편집 시간: 2022년 4월 29일 오후 8:29 코드 Algorithm/21610.py at main · Junroot/Algorithm 풀이 단순 시뮬레이션 문제다. 주의해야될 점을스자면 5번 과정에 기존에 구름이 있던 위치를 알아야되기 때문에 3번 과정을 제일 마지막에 하도록 처리한다. 그리고 구름이 이동하는 거리는 격자의 크기만큼 이동하면 같은 상황이 되므로 거리를 격자의 크기로 나눈 나머지만큼 이동시킨다.
오답 여부: o 편집 시간: 2022년 3월 29일 오후 4:15 코드 Algorithm/2098.py at main · Junroot/Algorithm 풀이 모든 경우를 탐색하면 O(N!). 즉, 최악의 경우 16!번 탐색해야되기 때문에 당연히 아닐거라고 생각했다. 하지만, 메모이제이션을 사용하면 O(N * 2^N) 만에 풀 수있다. 최악의 경우도 1,048,576번만 탐색하게 된다. 아직 메모이제이션을 사용했을때 시간복잡도 계산에 익숙하지 않은 것이 문제를 풀지 못 한 원인이 아닐까라고 생각한다. f(a, k): k에 담겨있는 노드들을 방문한 상태고 현재 위치가 a번 노드일 때 최소 비용...
편집 시간: 2022년 2월 21일 오후 2:09 코드 Algorithm/1991.py at main · Junroot/Algorithm 풀이 재귀함수를 이용하면 쉽게 구현할 수 있다.
편집 시간: 2022년 1월 31일 오후 5:52 코드 Algorithm/1978.py at main · Junroot/Algorithm 풀이 에라토스테네스의 체를 이용하면 쉽게 풀 수 있다. 2부터 (입력받은 수 중 최대값) 사이의 소수들을 모두 구하면된다.
오답 여부: o 편집 시간: 2022년 2월 24일 오후 2:58 코드 Algorithm/1967.py at main · Junroot/Algorithm 풀이 잘못된 풀이 처음에는 분할 정복으로 문제를 접근했다. 현재 루트 노드x에서 자식 노드를 두개 선택해서 두 깊이의 합을 f(x)라고 했을 때, x의 자식 노드들 a,b에 대해서 f(a), f(b)가 있을 때 max( f(x), f(a), f(b) ) 답이라고 생각했지만 수많은 재귀와 연산과정으로 메모리 초과 또는 시간초과가 발생했다. 맞는 풀이 트리에서 지름을 구하는 방법이 따로 있었다. 임의의 노드에서 트리 안에 가장 먼 노드를 a라고 했을 때, a와 가장 먼 노드 사이의 거리가 지름에 해당한다....
편집 시간: 2022년 2월 16일 오후 9:29 코드 Algorithm/1932.py at main · Junroot/Algorithm 풀이 dp로 풀 수 있다. f(i,j): i행 j열의 값의 최대값 f(i, j) = max(f(i - 1, j), f(i - 1, j + 1)) + triangle[i, j]
편집 시간: 2022년 2월 12일 오후 9:30 코드 Algorithm/1931.py at main · Junroot/Algorithm 풀이 그리디도 풀 수 있다. 회의가 일찍 끝나는 순으로 회의실을 배정하면, 최대한 많은 회의를 배정할 수 있다.
편집 시간: 2022년 2월 12일 오후 9:42 코드 Algorithm/1927.py at main · Junroot/Algorithm 풀이 python의 heapq를 이용하면 된다. 하지만 priority queue를 직접 구현해봤다. 새로운 값을 추가했을 때, 힙의 마지막에 추가한 뒤 자신위 부모보다 작을 때까지 하나씩 위로 올린다. 값을 삭제할 때는 가장 마지막 노드를 부모로 올린 뒤에 자신의 자식노드와 비교하면서 자신이 자식 노드보다 클 때 까지 아래로 하나씩 내린다. 이 때, 자식 둘이 모두 부모보다 작을 경우 둘 중 더 작은 자식과 교환해야된다....
편집 시간: 2022년 2월 7일 오후 8:28 코드 Algorithm/1920.py at main · Junroot/Algorithm 풀이 집합의 조회는 O(1)기 때문에, 집합을 이용하면된다.
오답 여부: o 편집 시간: 2022년 2월 24일 오후 3:23 코드 Algorithm/1918.py at main · Junroot/Algorithm 풀이 먼제 중위 표기식과 후위 표기식 모두 항의 순서는 바뀌지 않는 것을 확인했어야됐다. 그리고 후위 표기식은 뒤에 있는 항을 대상으로한 연산자를 먼저 기입해야된다. 따라서 연산자를 순서대로 확인하면서 뒤에 있는 연산자보다 앞에 있는 연산자를 먼저 처리해야된다면, 미리 처리해야된다. A+B*C-D/E ABC*+DE/- 위의 예에서도 - 연산자가 * 연산자보다 우선순위가 낮기 때문에 앞에 있는 연산자를 먼저처리하여 ABC*+ 가 되고, 그 이후에 DE/- 가 된다....
편집 시간: 2022년 2월 16일 오후 3:43 코드 Algorithm/18870.py at main · Junroot/Algorithm 풀이 좌표를 압축하기 위해서는 해당 숫자가 몇 번째로 큰 지 확인해야되기 때문에 정렬을 할 수 밖에 없다. 최대한 적은 개수를 정렬하기 위해서, 중복된 수를 제거한 뒤 정렬을 했다.