오답 여부: o 편집 시간: 2022년 2월 24일 오후 3:49 코드 Algorithm/1865.py at main · Junroot/Algorithm 풀이 문제 그대로 음의 사이클이 존재하는지 확인하면 된다. 벨만 포드 알고리즘을 사용하면 음의 사이클을 확인할 수 있다. 처음에는 시작노드를 1부터 n까지 모든 경우를 다 확인해서 음의 사이클이 발생하는지 확인했는데 이는 시간초과가 발생헀다. distances = [INF for _ in range(n + 1)] 로 시작하고, 값 갱신 조건에 distances[next] != INF 를 빼면 한번의 벨만 포드 알고리즘만으로 해결이 가능하다....
편집 시간: 2022년 3월 3일 오후 2:02 코드 Algorithm/1806.py at main · Junroot/Algorithm 풀이 루프문을 돌면서 해당 index로 끝나는 가장 짧은 수열을 찾는 방식으로 문제를 풀었다. 가장 잛은 수열을 구했다면, 다음 index에서는 앞의 수열에 index에 해당하는 수를 추가해주고 앞에서부터 s이상이 되는 가장 짧은 수가 되도록 수를 하나씩 빼주면 된다. 선입선출 때문에 나는 큐를 이용해서 문제를 풀었지만, 큐의 시작 부분과 끝 부분만 알고 있으면 풀 수 있기때문에 인덱스 두 개로 충분히 풀 수 있다....
편집 시간: 2022년 2월 12일 오후 9:49 코드 Algorithm/1764.py at main · Junroot/Algorithm 풀이 m과 n이 500,000 이하의 자연수기 때문에 정렬해도 문제가 없다는 것을 알 수 있다. 듣도 못한 사람 명단과 보도 못한 사람 명단을 정렬한 뒤 각각의 인덱스를 i, j로 기억하고 더 작은 이름의 인덱스를 1씩 늘리면서 비교하면된다.
편집 시간: 2022년 5월 3일 오후 5:50 코드 Algorithm/1753.py at main · Junroot/Algorithm 풀이 힙을 이용한 다익스트라 알고리즘을 사용하면 구현이 가능하다.
편집 시간: 2022년 2월 9일 오후 6:45 코드 Algorithm/1697.py at main · Junroot/Algorithm 풀이 bfs를 이용하여 탐색하다가 처음으로 k에 도달하는 지점의 시간을 출력하면 된다. 이 때 중복된 위치를 탐색하는 것을 방지하기 위해서 visited라는 집합을 만들어 사용했다.
편집 시간: 2022년 2월 24일 오후 2:35 코드 Algorithm/1629.py at main · Junroot/Algorithm 풀이 제곱을 이용해서 분할 정복을 했다.
편집 시간: 2022년 2월 16일 오후 3:46 코드 Algorithm/1620.py at main · Junroot/Algorithm 풀이 해쉬 맵을 이용하면 어려움 없이 해결할 수 있다. 숫자에 해당하는 이름과 이름에 해당하는 숫자를 해쉬 맵으로 따로 저장한뒤 출력하면 된다.
편집 시간: 2022년 2월 24일 오후 2:52 코드 Algorithm/15654.py at main · Junroot/Algorithm 풀이 정렬된 수열에 대해서 dfs로 문제를 풀면된다. 현재 어떤 숫자를 썼는지 확인하기 위해 visited 배열을 만들었다.
편집 시간: 2022년 2월 16일 오후 7:35 코드 Algorithm/15650.py at main · Junroot/Algorithm 풀이 재귀 함수를 이용해서 모든 경우의 수를 탐색하면 된다.
편집 시간: 2022년 4월 1일 오후 4:30 코드 Algorithm/1463.py at main · Junroot/Algorithm 풀이 1에서 시작해서 x에 도착하기까지 연산의 수로 문제를 바꾸어 해결했다. BFS로 순회하면서 이미 방문한 숫자는 무시했을 때, 최초로 x에 도착했을 때의 연산의 수가 답이 된다.
편집 시간: 2022년 4월 21일 오후 7:59 코드 Algorithm/14501.py at main · Junroot/Algorithm 풀이 인풋 범위를 보니 브루트포스로 구현해도 되지만, dp를 이용해서 풀었다. f(x): x일까지의 최대 이익 f(x) = max(consults[index][2] + f(consults[x][1] - 1), f(x-1)) consults[index][1] == x인 경우만 다른 풀이 다른 사람의 풀이를 보니 상담 완료날짜 기준이 아니라 시작날짜를 기준으로 dp로 풀면 정렬을 할 필요가 없었다. O(nlogn)을 O(n)문제로 해결할 수 있다.
편집 시간: 2022년 4월 21일 오후 4:31 코드 Algorithm/14500.py at main · Junroot/Algorithm 풀이 모든 경우를 다 해보고 가장 큰 값을 찾는다.
편집 시간: 2022년 4월 21일 오후 4:28 코드 Algorithm/14499.py at main · Junroot/Algorithm 풀이 구현 문제다. 주사위를 배열로 저장해두고 회전할 때의 배열이 어떻게 변하는지 직접 그려보면서 풀었다.
오답 여부: o 편집 시간: 2022년 4월 5일 오후 7:35 코드 Algorithm/14003.py at main · Junroot/Algorithm 풀이 12015 이 때와 완전히 똑같이 잘못된 방법으로 접근했다… 풀이 방법도 언급한 문제와 같은데, 추가적으로 가장긴 수열을 출력을 해야된다. 수열을 출력하기 위해서 입력값의 각 숫자가 sequence 에 몇번째 index에 저장이 되는지 기억해두면 출력할 수 있다. 아래 링크를 참고하면 이해하기 쉽다. https://yabmoons.tistory.com/561
편집 시간: 2022년 2월 24일 오후 3:03 코드 Algorithm/13549.py at main · Junroot/Algorithm 풀이 bfs로 풀면되지만, 순간이동하는 경우에는 시간이 흐르지 않기 때문에 큐 대신 우선순위 큐를 사용하면 된다.
편집 시간: 2022년 3월 1일 오후 7:24 코드 Algorithm/13460.py at main · Junroot/Algorithm 풀이 기본적으로 BFS를 사용해서 모든 경우를 탐색하면 된다. 하지만, R과 B의 이동 처리에 대한 문제가 있었다. R과 B가 나란히 붙어있으면, R과 B가 함께 굴러가야되는데 막혀있는 걸로 판별하여 한 구슬만 이동하게 되는 경우가 발생할 수 있기때문이다. 이를 해결하기 위해 한 틱에 한 칸씩 이동시키면서 앞에 가록막는 구슬이 있다면 일단 정지시키도록 했다. 이를 계속 반복하여 R과 B가 더 이상 움직이 못할 때까지 이동시키면 된다....
편집 시간: 2022년 4월 21일 오후 4:26 코드 Algorithm/13458.py at main · Junroot/Algorithm 풀이 간단해서 따로 설명할 것이 없다. 시험장 하나씩 계산해서 합하면된다.
오답 여부: o 편집 시간: 2022년 2월 24일 오후 2:29 코드 Algorithm/12865.py at main · Junroot/Algorithm Algorithm/12865-2.py at main · Junroot/Algorithm 풀이 나쁜 풀이(12865.py) dp로 풀 수 있다. f(i, w): 0번째부터 i번째까지 물건들 중에서 w까지 담을 수 있는 가방이 있을 때, 담을 수 있는 최대 가치 f(i, w) = max( f(i - 1, w - weight[i]) + value[i], f(i - 1, w) ) 하지만 재귀를 이용한 탑다운으로 풀다보니 엄청나게 느린 결과가 나왔다....
편집 시간: 2022년 4월 1일 오후 4:34 코드 Algorithm/12852.py at main · Junroot/Algorithm 풀이 f(N)이 N을 1로 만들기 위해 최소 연산 수라고 가정하면 아래의 식을 만족한다. $$ f(N)=min(\space f(N/3),f(N/2),f(N-1) \space) +1 $$ 위 점화식을 이용해 바텀업으로 dp를 구현하면 쉽게 최소 연산 수를 구할 수 있다. 추가적으로, 자신이 선택한 경로를 저장해두면 연산 과정도 쉽게 구할 수 있다.
편집 시간: 2022년 2월 7일 오후 9:05 코드 Algorithm/1259.py at main · Junroot/Algorithm 풀이 입력값을 숫자가 아니라 문자열로 생각하면 쉽게 풀 수 있다.