Baekjoon Online Judge

[BOJ] 16437 : 양 구출 작전 (C++)

https://www.acmicpc.net/problem/16437걸린 시간 : 24분골드3이 맞나... 싶은 문제.알고리즘루트(1번 섬)부터 시작해서 자식들로부터 오는 양의 수를 세면 된다.dfs(int k) 메소드는 k번째 섬에 오는 양의 수이다. 만약 늑대가 다 먹어서 다 못 온다면 0이 오게 될 것이다.정답 코드#include using namespace std;int N;long long island[123457];vector children[123457];bool kind[123457];long long dfs(int k) { if (kind[k]) { long long ret = island[k]; for (int c : children[k]) { ret += dfs(c); } r..

[BOJ] 20057 : 마법사 상어와 토네이도 (C++)

https://www.acmicpc.net/problem/20057걸린 시간 : 54분 26초삼성의 상어 시리즈 문제이다. 정말 구현! 이다.알고리즘모래밭을 주어진 형태로 계속 돌면서 흩뿌리면 된다. 움직이는 기능을 하는 함수인 move()와 흩뿌리는 기능을 하는 함수인 scatter()만 구현하면 된다.움직이기move(int ci, int cj, int dir, int leftcnt) 함수는 현재 위치에서 현재 방향으로 한 칸 움직이는 함수이다. 단, 남은 횟수가 더 이상 없다면 실행을 멈추거나 방향을 바꿔서 직진한다.여기서 방향은 di, dj 배열에 좌, 하, 우, 상 순으로 넣어놨다. 따라서 반시계 방향으로 회전하려면 단순히 dir = (dir + 1) % 4; 만 실행하면 된다.또한 남은 횟수 지..

[BOJ] 3190 : 뱀 (C++)

https://www.acmicpc.net/problem/3190걸린 시간 : 56분정말 그냥 구현 문제이다. 프로그램으로 상황을 잘 표현할 수 있다면 쉬운 문제이다.나는 정말 사소한 부분에서 막혔다. 다음 부분이다.if (find(apple.begin(), apple.end(), {ni, nj}))apple이라는 벡터에서 {ni, nj} pair를 찾아 bool로 반환하는 algorithm 헤더의 함수이다.하지만, pair는 기본 자료형이 아니므로 == operator가 정의되어 있지 않다. 즉, 애초에 같다는 것이 정의되어 있지 않아서 찾을 수가 없다는 것이다.이를 위한 방법으로는 find_if 함수가 있다. 하지만, 어차피 find_if 함수가 시간복잡도가 낮은 것도 아니므로 코딩 테스트 목적으로는..

[BOJ] 12015 : 가장 긴 증가하는 부분 수열 2 (C++)

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 꽤 유명하지만 약간은 마이너한 가장 긴 증가하는 부분 수열, LIS 알고리즘이다. 간단히 생각해보면 O(N^2) 알고리즘은 생각하지 쉽지만 이보다 더 줄일 수 있다. O(N^2) [6, 2, 5, 1, 7, 4, 8] 이라는 배열의 LIS 를 구하는 경우를 보자. 답은 [2, 5, 7, 8] 이다. length 라는 배열을 length[i] = (i 에서 끝나는 LIS의 길이) 로 생각해보자. 이..

[BOJ] 2805 : 나무 자르기 (C++)

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 걸린 시간 : 25분 2초 몇몇 Parametric Search 문제를 봤지만, 항상 어떤 알고리즘을 써야 할지 몰랐다. 하지만 이번 문제는 단번에 Parametric Search인 것을 알았다. 이 문제를 참고하자 자세한 매개 변수 탐색에 관한 이야기를 적어놨다. https://morenow.tistory.com/44 [BOJ] 2110 : 공유기 설치 (..

[BOJ] 9019 : DSLR (Java)

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 걸린 시간 : 1시간 4분 C++에서 Java로 옮기려고 하니까 쉬운 코드여도 실수가 엄청 잦고 코드도 깔끔하게 안 써진다... 처음엔 DP로 생각하고 풀려다가,, 그냥 BFS로 밀어버려도 되겠다고 생각해서 중간에 싹 바꿨다. 자료구조 memo배열 : 해당 인덱스까지 오려면 어떤 연산을 거쳐야 하는지에 대한 String형 배열이다. vis배열 : 해당 인덱스에 방문했다면 더 이상 방문..

[BOJ] 14940 : 쉬운 최단거리 (Java)

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 걸린 시간 : 34분 33초 알고리즘 최단 거리 알고리즘 중 어떤 알고리즘? 최단 거리를 구할 수 있는 알고리즘 중 4가지를 살펴보자. 어떤 한 시작점에서 출발할 경우 모든 시작점을 다 고려할 경우 가중치가 없는 경우 BFS 알고리즘 BFS or 플로이드 알고리즘 가중치가 있는 경우 다익스트라 알고리즘 플로이드 알고리즘 이렇게 4가지를 생각하면 어떤 문..

[BOJ] 2630 : 색종이 만들기 (Java) with 분할 정복

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 걸린 시간 : 19분 26초 기초적인 분할 정복 문제이다. 분할 정복은 재귀의 한 갈래이다. 재귀를 알 때 제일 중요한 것은 점화식이다. 점화식만 잘 파악하면 끝나는 문제. 알고리즘 색종이를 자를 cut() 메소드를 재귀호출한다. 재귀호출에 필요한 파라미터를 생각해보자. 파라미터의 조합으로 색종이를 자른 한 부분을 특정할 수 있으면 된다! 즉, 시작점이 필요하고, 색종이..

[BOJ] 1927 : 최소 힙 (Java)

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 걸린 시간 : 5분 18초 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; public class BOJ1927 { static PriorityQueue pq = new PriorityQueue..

[BOJ] 11444 : 피보나치 수 6 (Java)

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 걸린 시간 : 36분 32초 재밌을 것 같아서 도전! 했는데,, 숫자가 너무 크다. 이러면 무조건 O(logN) 알고리즘을 써야 하고, 그렇단 말은 F(2n) 과 F(n) 과의 관계를 알아내면 끝이다. ... ... 도대체 무슨 관계가 있는지 전혀 감도 안 오고 배운 적도 없는 것 같다.. 이런 너무 수학적인 주제를 공부할 시간에 코딩 공부를 좀 더 하자는 핑계 생각에 잠깐 검색을 해보았더니 이런 식이 나온다. 이걸 제가 어떻게 알아요 이 식의 m에 n, n+1 을 대입해 ..