알고리즘 풀이
-
BOJ 2146 [다리 만들기]알고리즘 풀이/BFS(너비 우선 탐색) 2018. 10. 4. 06:28
BOJ 다리 만들기 : https://www.acmicpc.net/problem/2146 안녕하세요. 이번 문제는 백준 온라인 저지의 [다리 만들기] 입니다. 1. BFS로 현재 위치에서 갈 수 있는 곳을 확장시킨 뒤, BFS를 빠져나올 때 마다 해당 섬에 번호 부여. 2. 다시 처음부터 BFS를 돌며, 첫 시작지와 섬 번호가 다른 섬을 찾아 떠난다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485import java.util.*;class Node { public ..
-
BOJ 1726 [로봇]알고리즘 풀이/BFS(너비 우선 탐색) 2018. 10. 4. 06:20
BOJ 로봇 : https://www.acmicpc.net/problem/1726 이번 문제는 백준 온라인 저지의 [로봇] 입니다. 재방문을 방지하기위해 Visited를 사용했습니다만, 3차원으로 방향에 대한 방문도 고려하도록 했습니다. 로봇이 할 수 있는 행동인 1~3칸 앞으로 가기, 방향 꺾기 등을 큐에 담으며 탐색을 진행합니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include #include using namespace std;int M..
-
SWEA 5644 [무선 충전]알고리즘 풀이/시뮬레이션 2018. 10. 4. 06:04
SW Expert Academy 무선 충전 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE&&& //SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 문제시 삭제하겠습니다. 간단한 시뮬레이션 문제입니다. 우선 현재 시점에서 사람1과 사람2가 각 배터리의 충전 범위에 들어와있는지 확인합니다. 충전범위에 있을 경우, 각 사람에 맞는 배열로, 해당 배터리의 충전 범위에 들어왔는지 bool을 통해 체크해줍니다. 배터리의 개수만큼 이중 for문을 돕니다. 1. i == j 일 경우 => 만약 둘다 해당 배터..
-
BOJ 3967 [매직 스타]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 10. 2. 03:47
BOJ 매직 스타 : https://www.acmicpc.net/problem/3967 안녕하세요. 이번 문제는 백준 온라인 저지의 [매직 스타] 입니다. 순열 조합 문제인데요, 일반적으로 작성하면, 시간 초과를 부를 수 있습니다. 저는 백트레킹을 할 때, 현재 최소로 설정된 문자열보다 사전순으로 뒤에 있는 경우엔 끝까지 가지 않고 바로 back 했습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include #include using namespace std;vector..
-
BOJ 2234 [성곽]알고리즘 풀이/BFS(너비 우선 탐색) 2018. 10. 2. 03:31
BOJ 성곽 : https://www.acmicpc.net/problem/2234 안녕하세요. 이번 문제는 백준 온라인 저지의 [성곽] 입니다. 우선 1, 2번 요구사항의 경우는, 기본적인 BFS문제입니다. 다만, 입력이 평소의 문제와 조금 다릅니다. 우선, 이진법을 통해 각 위치의 동서남북을 1로 설정합니다. 여기서 MAP을 2배 늘려서 이동을 2칸씩 하고, 벽은 한칸 뒤에 놓았습니다. 다음 3번에서 사용한 방법입니다. 1. 먼저 BFS를 통해 구한 방의 size와 방 번호를 노드 배열형태로 저장. 2. for문을 돌면서, 인접 좌표의 방번호가 다르면, 해당 방의 size를 비교 모든 좌표를 돌면서, 상하좌우를 확인하고 방 번호가 다를 때, 방의 사이즈를 더한 값의 최대를 구하면, 벽을 뚫을 때의 최대..
-
BOJ 11726 [2xn 타일링]알고리즘 풀이/DP(동적계획법) 2018. 9. 25. 21:48
BOJ 2x 타일링 : https://www.acmicpc.net/problem/11726 안녕하세요. 이번 문제는 백준 온라인 저지의 "2xn 타일링" 입니다. (2 x 5 타일) (2 x 4 타일) (2 x 3 타일) 위 그림처럼, 2 x 5 타일을 만드는 방법은, 1. 2 x 4 타일에서 2 x 1 타일 하나를 붙이는 방법과, 2. 2 x 3 타일에서 1 x 2타일 두 개를 붙여서 만드는 방법 두가지 입니다. 즉, 두 경우 [i - 1] 과 [i - 2]의 경우의 수를 더해주면, 어렵지 않게 [i]를 구할 수 있습니다. 123456789101112131415#include using namespace std;int DP[1001];int main() { int N; cin >> N; DP[0] = ..
-
BOJ 1463 [1로 만들기]알고리즘 풀이/DP(동적계획법) 2018. 9. 25. 21:31
BOJ 1로 만들기 : https://www.acmicpc.net/problem/1463 안녕하세요. 이번 문제는 백준 온라인 저지의 "1로 만들기" 입니다. 우선, 정수 1에서 1로 가기위해 사용되는 연산 수는 0입니다. (arr[1] = 0) 그 다음, 2, 3에서 1로 가기위해 사용되는 연산 수는 1입니다. (2 / 2 or 2 - 1 = 1, 3 / 3 = 1 -> arr[2], arr[3] = 1) 4부턴 1로 가는 방법이 여러가지입니다. (4 / 2 = 2 / 2 = 1, 4 - 1 = 3 / 3 = 1 -> arr[4] = 2) 이제부터 N에 대해 보겠습니다. 총 세 가지 값을 비교하면 됩니다. 만약 N을 3으로 나눌 수 있으면, arr[N] = arr[N / 3] + 1이 됩니다. 또, 2..
-
SWEA 1949 [등산로 조성]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 9. 25. 21:14
SW Expert Academy 등산로 조성 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE //SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다. 가장 긴 등산로를 만들 수 있는 경우를 찾는 문제입니다. 문제를 풀 때, 가장 간과할 수 있는점은 바로, "최대 K만큼 깎을 수 있다" 입니다. 즉, 1~K까지 깎을 수 있습니다. 따라서 다음 위치를 최대 K만큼 깎을 수 있을 때, 최소한으로 깎아준 뒤 DFS를 진행해 줬습니다. (무작정 최대만큼 깎아놓으면, 깎인 좌표에서 다..