본문 바로가기

[Algorithms]

 (38)
BOJ. 11657번. 타임머신 이번 문제는 벨만-포드 알고리즘을 활용한 문제다. 실제 코드 상에서도, 각 정점을 돌아보면서 최소비용을 갱신해 나가는 형태가 다익스트라(우선순위 큐)를 사용하지 않은 코드랑 비슷했다. 물론 음의 가중치가 포함된 문제라 다익스트라로는 해결할 수 없다. + 추가로 거리를 계산할 때 오버플로우가 나는 바람에 출력초과가 나왔다. 넘칠 것 같으면 처음부터 long으로 넉넉하게 잡아주는 것도 실수를 줄이는 방법이 될 것 같다. www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000..
BOJ. 1238번. 파티 이 문제는 다익스트라 알고리즘을 뒤집어 붙이는 문제이다. 처음에 리스트로 맵을 만든 다음, 해당 맵을 기준으로 두가지 다익스트라 알고리즘(하나는 정방향, 하나는 역방향)을 만들려고 했다가, 데이터 자체를 반전시키는 편이 훨씬 간편하다는 것을 깨닫고 선회했다. 문제 풀이는 간단하다. 1. 정방향에 따른 방문체크배열, 인접리스트, 최소비용행렬을 선언한다. 2. 역방향도 마찬가지로 만들어 준다. 3. 정방향과 역방향 각각에 따른 최소비용행렬을 둘다 계산한 다음, 정향향,역방향 비용의 합 중 최대비용인 놈을 찾으면 끝 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터..
[Theory] Graph 6. 최소비용 - 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 하나의 시작 정점에서 끝 정점까지의 최단경로를 구하기 위한 알고리즘이다. 음의 가중치를 가지지 않으며, PriorityQueue의 사용여부에 따라 시간복잡도는 O(V^2)~O(E+VlogV)까지 나타난다. 음의 가중치를 허용하는 경우에는 벨판-포드(Bellman-Ford)알고리즘을 사용할 수 있다. (모든 정점들에 대한 최단경로를 구하는 데는 DP개념을 적용한 플로이드-워샬(Floyd-Warshall)을 사용할 수 있다.) 본론으로 돌아와서, 시작 정점이 주어졌을 때 각 정점까지의 최단경로를 구하려면 어떻게하면 될까? 다음 코드는 priorityQueue를 사용하지 않는 코드이다. import java.io.BufferedReader; import java.io.I..
BOJ. 11780번. 플로이드 2 플로이드 1에 이어서 플로이드 2 문제도 풀어보았다. 1번이랑 다른 점은, 플로이드 워셜을 돌면서 바뀌는 내용들을 저장해야 된다는 것이다. 나는 ArrayList 배열을 선언해서, 최소비용이 갱신이 될 때마다 이를 저장하도록 만들었다. 그리고 마지막에 배열의 각 지점들을 돌면서 저장된 리스트 내용들을 출력하면 끝! www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net package week_11; import java.io.BufferedReader; impo..
BOJ. 20061번. 모노미노도미노 2 구현 순서에 주의해서 풀면 그리 어렵지 않게 해결할 수 있다. 이전에는 구현문제에 애를 많이 먹었는데, 한두어달 문제를 조금씩 풀다보니 조금씩 익숙해지고 있는 중인 것 같다. 나는 초록색 구역과 파란색구역을 따로 나누지 않고, 초록색 테이블을 대각선으로 반전시키면 파란색과 초록색 테이블이 동일해진다는 아이디어를 가지고, 두가지 구역을 같은 로직으로 처리했다. www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net import java.io.Buffered..
BOJ. 1600번. 말이 되고픈 원숭이 말이 되고픈 원숭이... 나를 보는 것 같다^^. 이 문제는 일반적인 BFS를 하되, 1. 평범하게 상하좌우로 움직일 수 도 있고 / 2. 말로 움직일 수 도 있다. 따라서 방문체크를 할 때, 당시의 말의 움직인 횟수가 영향을 미치기 때문에 차원을 3차원으로 늘려서 케이스를 나눠 생각해야 한다. 이 아이디어만 생각해낸다면 쉬운 BFS문제이다. www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net import java.io.BufferedReader..
[Theory] Graph 5. MST - PRIM PRIM 알고리즘은 하나의 정점에서 파생된 간선들 중에서 하나를 선택해서 MST를 만들어 가는 방식이다. 알고리즘의 동작방식은 다음과 같다. 1. 시작은 아무 정점이든 상관 없다. 2. 시작한 정점 및 인접하는 정점들 중 최소비용의 간선을 선택한다. 3. 모든 정점이 선택될 때 까지 계속 반복한다. [동작 과정] 보통 Prim의 경우, 간선들의 최소를 골라내기 위해 PriorityQueue를 사용하기도 하지만, 아래 코드에서는 이를 사용하지 않고, 코드로 그대로 나타내었다. 1. 먼저 신장트리에 연결되지 않은 정점 중에서 edge비용이 최소인 정점을 골라낸다. 2. 이어서 신장트리에 포함되지 않은 정점들 중에서 최솟값이 나오면 업데이트 한다. for(int c=0; c
[Theory] Graph 4. MST - KRUSKAL KRUSKAL 알고리즘은 간선을 하나씩 선택해서 MST(Minimun Spanning Tree) 를 찾는 과정이다. 여기서 MST(Minimum Spanning Tree)는 우리말로 '최소 신장 트리' 라고 하는데, 무향 가중치 그래프에서 신장트리를 구성하는 가중치의 합이 최소인 트리를 말한다. 더불어 신장트리(Spanning Tree)라는 것은 무향 그래프에서 n개의 정점과, n-1개의 간선으로 이루어진 트리를 말한다. 알고리즘의 동작과정을 요약하면 다음과 같다. 1. 모든 간선을 가중치에 따라 오름차순으로 정렬한다. (Sort) 2. 가중치가 낮은 간선부터 골라 트리를 만든다 ( 이때 사이클이 발생하면 다음으로 낮은 간선을 선택한다 ) 3. n-1개의 간선을 고를때 까지 반복한다. 이번엔 그림으로 살..
BOJ. 16637번. 괄호 추가하기 이 문제를 처음에 접근할 때, 하나의 배열로 인덱스를 모두 관리하려고 했었는데 그게 쉽지 않았다. 따라서 number와 operation에 대한 배열 두개로 나눠서 풀었는데 훨씬 인덱스 관리가 편리해졌다. 1. 기본적인 아이디어는 dfs이다 2. 각 재귀호출 시 마다, operation의 인덱스를 하나씩 키워가면서 계산한다. 3. 이때 계산은 괄호를 추가하는 경우, 추가하지 않는 경우로 나누며 3-1. 괄호 추가하는 않는(필요없는) 경우 : 그대로 연산한 결과를 다음 연산자에게 넘겨준다. 3-2. 괄호 추가하는 경우: 다음연산자를 먼저 계산하고, 다다음 연산자에게 넘겨준다. www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 ..
BOJ. 2638번. 치즈 어디서 이렇게 비슷하게 생긴 문제들이 계속 나타나는지 모르겠다ㅎㅎ 단순한 BFS문제다. 다만 내부에 공기층이 생긴 경우 이를 따로 처리해 주어야 한다. 나는 거꿀로 외부에서부터 BFS탐색을 돌면서 외부 공기층을 2로 바꾸고, 이 외부 공기층( 2 )와 2면 이상 인접한 치즈들을 녹여주었다. www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net package week9; import java.io.BufferedReader; import java.io.IO..

티스토리툴바