Hyun's_Devlog

https://www.acmicpc.net/problem/1337

투 포인터로 접근한 문제다.

풀이

기준이 될 인덱스 i는 1부터 n까지, 비교할 인덱스 k는 i+1부터 i+4까지 반복문을 수행. 둘의 차이가 5보다 작다면 올바른 배열로 판정한다.

기준 인덱스 i가 바뀔 때마다 최댓값을 갱신한 뒤, 반복문이 끝나고 나면 값을 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/10025

투 포인터, 슬라이딩 윈도우로 접근한 문제다.

풀이

투 포인터를 사용하여 곰이 얼음에 닿을 수 있는 최대거리 (2*k+1) 범위의 얼음합을 좌표값 0부터 1000,000까지 탐색을 하면 된다. 단 k의 크기가 500,000을 넘는다면 모든 좌표에 있는 얼음을 가져올 수 있으므로, 입력을 받으면서 얼음의 최댓값을 미리 계산하여 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/14246

투포인터 문제다. 간단한 문제라고 생각하고서 접근했지만, 약간의 시간이 걸린 문제다.

풀이

head와 tail 두 개의 변수에 구간 합의 시작 인덱스와 끝 인덱스를 할당. 처음에는 둘 다 0으로 시작한다. 주어지는 수는 무조건 자연수다. 그 이야기는 해당 구간의 합이 k보다 크다면, 그 이후의 구간은 모두 조건을 만족한다는 뜻이다. 조건이 맞는다면 tail에 해당하는 인덱스부터 n까지의 개수를 모두 더해준 뒤, head 인덱스를 증가하여 다시 조건을 탐색. 이런 방법으로 구간을 탐색한다.

만일 sum이 k보다 작고, tail이 더 이상 증가할 수 없는 상황이라면, 반복문을 종료하면 된다.  

정답 코드

https://www.acmicpc.net/problem/2018

기초적인 투포인터 문제다.

풀이

1부터 N까지의 수를 오름차순으로 담은 배열을 생성한 뒤, 인덱스를 활용한 구간탐색을 통해 답을 구하면 된다. 시작 인덱스와 끝인덱스는 동일하게 0으로 시작한 뒤, 아래와 같은 조건으로 반복을 수행한다.

• 누적합이 목표 숫자보다 크다면 시작 인덱스가 가리키는 숫자를 뺀 뒤 시작 인덱스 증가
• 누적합이 목표 숫자보다 작거나 같다면 끝 인덱스가 가리키는 숫자를 더 해준 뒤 끝 인덱스 증가
• 누적합이 목표숫자와 같다면 카운트 증가
• 끝 인덱스가 증가할 부분이 없다면 종료

정답코드

https://www.acmicpc.net/problem/1504

다익스트라 알고리즘 문제. 마찬가지로 Rhyno님이 작성한 힙을 사용했다.

풀이

1번에서 n번 정점까지의 최단경로, 하지만 반드시 두지점을 거쳐야 한다는 조건이 붙었다.

[1 -> v1 -> v2 -> n ] 또는 [1 -> v2 -> v1 -> n] 두 가지 최단 경로중 가중치가 더 적은 경로를 반환하면 된다. 1번 정점에서 각 정점으로 향하는 최단경로, v1 정점에서 각 정점으로 향하는 최단경로, v2 정점에서 각 정점으로 향하는 최단경로 총 다익스트라 3번을 돌린 뒤 각 가중치를 적절히 조합해서 반환하면 된다.

하지만 여기서 경로가 없는 조건에 대해 처리해주어야 하므로 이 부분만 신경 써준다면 정답을 받을 수 있다. 본인의 경우 최단경로를 담은 배열을 -1로 초기화한뒤 다익스트라를 통해 갱신하였는데, 아무리 조건을 신경 써서 제출해도 오답판정을 받아 결국 계산 가능한 가중치의 최댓값인 2억으로 초기화하며 예외처리하였다.

정답 코드

https://www.acmicpc.net/problem/1238

다익스트라 알고리즘으로 접근한 문제다. 힙 구현이 필요하다. 직접 구현할 역량이 안되기에, Rhyno님이 작성한 힙을 사용하였다.

풀이

간선과 가중치를 입력받은 map 배열을 통해, 다익스트라 알고리즘을 사용한다. 양방향 간선이 아닌 단방향 간선이기에 우선 파티 장소 x에서 각 마을로 되돌아가는 배열을 생성, 다익스트라 알고리즘을 통해 각 인덱스에 저장. 이후 1 ~ n번 마을에서 x로 향하는 최단거리를 한 번 더 다익스트라 알고리즘을 통해 방금 저장한 배열에 추가시켜 준다. 마지막으로 배열에 담긴 최댓값을 출력한다.

정답 코드

https://www.acmicpc.net/problem/2056

위상정렬과 동적계획법으로 접근가능한 문제다.

풀이법

처음에는 단순히 위상정렬을 통해 큐에 접근할 때마다 가장 오래 걸린 작업시간들을 더하면 될 것이라 생각했다. 하지만 해당방법은 틀린 방법이 다.

후속이 없는 작업의 경우, 다음 탐색에  영향을 끼치지 않아야 하는데, 처음생각한 방법은 이러한 부분을 제외시키지 못했다. 따라서 해당 작업을 완료하는데 걸리는 총시간을 담은 dp 배열을 생성한 뒤, 동적계획법으로 접근해야 한다. next는 다음 작업, curr는 현재작업을 의미할 때, 점화식은 다음과 같다. 여기서 time배열은 순수 작업시간을 의미한다.

dp[next] = max(dp[next], dp[curr]+time[next])

위상정렬을 통한 그래프탐색 이후, dp배열의 최댓값을 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/14567

위상정렬 문제다.

풀이

문제에서 요구하는 것은 선수과목의 순서가 아니라 각 과목을 듣기 위한 최소 학기수.

즉 위상정렬을 사용하여 큐에 몇번 접근하는지를 파악하면 된다. 

입력되는 값을 통해 각 노드의 진입차수를 저장. 진입차수가 0인 노드를 큐에 담아놓고 그래프탐색을 수행하면 된다.

그래프탐색을 통해 다른 노드로 진입시, 해당노드의 진입차수를 하나씩 차감. 0이 된다면 다음 탐색큐에 추가하면 된다.

문제의 정답을 계산하기 위해 반복문을 구분하여 탐색해야 한다. 해당 부분은 코드르 보는 게 이해하기 쉬울 것이다.

정답 코드