뱀귤 블로그

문제 링크 : https://www.acmicpc.net/problem/6118

수혀니가 있는 1번 헛간으로부터 가장 먼 헛간들의 갯수, 거리를 구하는 문제입니다.

간선 가중치가 없고 모든 최장거리를 전부 구해야되기 때문에 BFS를 사용하면 쉽게 해결할 수 있습니다.

한가지 주의할 점은 N이 최대 20,000 이기 때문에 O(N^2)인 인접행렬을 이용할 경우 시간초과가 납니다.

인접리스트 BFS를 돌면서 최대 거리, 최대 거리의 갯수, 재서기가 숨은 가장 작은 헛간을 찾아주시면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/1620

문제는 굉장히 길지만 핵심은 포켓몬을 말하면 번호를, 번호를 말하면 포켓몬을 출력하는 문제입니다.

포켓몬이 최대 100,000마리이기 때문에 Map 자료구조를 사용하여 key, value를 바꿔가며 두번씩 넣었습니다.

간단하니 코드로 보는게 이해하기 쉽습니다.

문제 링크 : https://www.acmicpc.net/problem/1697

수빈이가 동생과 만나는 시간을 출력하는 문제입니다.

간단하게 BFS를 이용하여 해결할 수 있습니다.

처음 수빈이의 위치를 Queue에 넣고 +1, -1, *2 한 위치를 각각 Queue에 넣어가며 BFS를 합니다.

그리고 수빈이가 한번 방문했던 위치를 계속 체크하여 중복 방문을 하지 않도록 하면 됩니다.

그리고 수빈이의 시작 위치가 동생보다 크다면 무조건 -1을 반복하여 만나는 수밖에 없으므로 N-K를 바로 출력합니다

문제 링크 : https://www.acmicpc.net/problem/1238

모든 마을에서 출발하여 X 마을에 들렀다가 다시 돌아오는 길이 가장 큰 값을 구하는 문제입니다.

N이 크지 않아서 플로이드와샬, 다익스트라 어느것으로 해도 풀리는 문제입니다.

하지만 X에 대한 최단 경로만 구하면 되는 상황에서 모든 정점에 대해 다익스트라를 하는 것은 비효율 적입니다.

그래서 'X마을 -> 다른 모든 마을' 의 최단경로와 '다른 모든 마을 -> X마을' 의 최단경로.

단 두번만 다익스트라를 돌려서 문제를 해결할 수 있습니다.

X마을에서의 최단 경로는 시작점을 X로 놓고 하면 되지만

X마을로 향하는 최단 경로는 조금 다릅니다.

입력받는 간선의 값을 전부 뒤집어서 넣은 뒤에 시작점을 X로 하여 구해야 합니다.

인접행렬을 예로 들면 원래는 edge[v1][v2] = cost 이렇게 입력하는 식을 edge[v2][v1] = cost 로 입력한 edge 배열을 이용하여 구할 수 있습니다.

저는 처음부터 인접리스트를 두개 생성하여 구하는 방법으로 하였습니다.

문제 링크 : https://www.acmicpc.net/problem/1753

시작점이 주어지면 각 정점에 대한 최단 경로를 출력하는 문제입니다.

다익스트라 알고리즘을 사용해서 풀면 됩니다.

처음에는 아무 생각 없이 인접행렬로 만들어서 풀었었는데 메모리 초과가 나왔습니다.

정점의 갯수가 최대 2만개여서 인접행렬을 만든다면 최대 2억개의 int 배열을 할당하기 때문에 당연히 메모리가 터집니다.

그래서 인접리스트로 만들었더니 통과하였습니다.

문제 링크 : https://www.acmicpc.net/problem/10815

상근이가 갖고 있는 숫자가 맞는지 확인하는 문제입니다.

배열 크기는 약 2700만 정도까지 할당이 가능하기 때문에 boolean 배열을 선언해서 해도 됩니다.

하지만 boolean 배열을 쓴다면 BitSet 이라는 자료구조를 사용하면 더 좋습니다.

일반적으로 boolean 배열은 값마다 1Byte씩 차지하는데 BitSet은 1bit만 차지합니다.

무려 7bit를 아끼는 효과가 있죠.

값을 넣을 때 주의할 점은 BitSet 역시 인덱스를 사용하기 때문에 음수 인덱스를 참조하면 에러가 발생합니다.

인덱스가 0부터 시작할 수 있도록 10,000,000 을 더해줍시다!

그리고 입/출력이 많기 때문에 BufferedReader와 BufferedWriter를 사용해주는 것이 좋습니다.

문제 링크 : https://www.acmicpc.net/problem/2240

자두가 먹을 수 있는 자두의 최대 갯수를 구하는 문제입니다.

[현재 시간][자두가 이동한 횟수] 를 배열로 한 DP로 해결을 할 수 있습니다.

위치에 대한 인덱스를 만들지 않은 이유는 자두가 이동한 횟수로 현재 위치를 알 수 있기 때문입니다.

자두는 무조건 나무 1에서 시작합니다.

자두가 0, 2, 4, ... 처럼 짝수번 움직이면 자두의 현재 위치는 나무 1입니다.

만약 자두가 1, 3, 5 .. 처럼 홀수번 움직인다면 자두의 현재 위치는 나무 2입니다.

그렇기 때문에 dp[i][j] 는 나무 1일때와 2일때 서로 겹치는 일이 없습니다.

한가지 주의할 점은 현재 시간이 1일때는 항상 나무 1에 떨어지는 경우만 카운트해야 한다는 점입니다.

그 외에는 자두가 가만히 있는 경우 dp[i-1][j] 와 움직인 경우 dp[i-1][j-1] 로 나누어 처리를 해주면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/2473

백준 2470번 두 용액 문제의 업그레이드 버전입니다.

두 용액을 O(n) 시간에 구했었습니다.

세 용액은 배열의 숫자 하나를 지정해서 (두 용액 + 지정된 용액) 의 합이 0에 가장 가까운지 판단하면 됩니다.

따라서 배열을 순회하면서 두 용액 구하는 과정을 N번 반복하면 되기 때문에 O(N^2) 시간에 구할 수 있습니다.

한 가지 주의할 점은 두 용액 문제에서는 용액의 합으로 나올 수 있는 최대값이 2,000,000,000 이었기 때문에 int 형으로도 풀렸지만

세 용액 문제에서는 3,000,000,000 이상이 될 수 있기 때문에 long 타입으로 풀어줘야 합니다.