백준
-
BOJ) 뱀 (3190번)알고리즘/백준 2021. 1. 19. 00:03
뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 시뮬레이션 문제로 기억하는 사람이 있을지 모르지만, 피자를 먹으면 뱀의 꼬리가 늘어나는 게임이 있었다. 딱, 그 문제를 구현하는 문제였다. 아무튼, 행과 열을 오랜만에 이용하다보니 이에 대한 개념의 혼동으로 문제를 틀렸었다. 행은 가로에 대한 정보, 열은 세로에 대한 정보다. 따라서, 행은 y축의 index를 가지고 열은 x축의 index를 갖게된다. 풀이 문제의 조건에 머리가 뱀의 몸에 닿거나 벽에 닿으면 종료된다. 벽에 대한 정보를 저장해주려고 맵의 크기를 N+..
-
BOJ) 최소 스패닝 트리 (1197 번)알고리즘/백준 2021. 1. 7. 16:36
최소 스패닝 트리 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리 최소 신장 트리라고도 하며, Minimum Spanning Tree(MST) 로 많이 들어 봤을 것이다. MST는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 가중치의 합이 최소가 되는 트리이다. 즉, 최소 가중치를 가지며 그래프의 모든 정점을 연결하는 방법이다. 이 때, cycle이 생겨서는 안된다. 이 문제는 Prim과 Kruskal 알고리즘 두 개로 풀어봤다. ..
-
BOJ) 골드바흐의 추측 (9020 번)알고리즘/백준 2021. 1. 7. 16:18
골드바흐의 추측 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 소수는 에라토네스의 체를 이용하면 수월하게 소수를 구할 수 있다. 에라토네스의 체의 개념을 다시 환기하기 위해 작성한다. 추가적으로, 이 문제에서 출력 부분에 String.format을 이용해서 출력하는 방법과 띄워쓰기와 new line을 append 해주며 출력하는 방법을 이용해봤는데, 메모리와 속도 측면..
-
BOJ) 가장 긴 바이토닉 부분 수열 (11054 번)알고리즘/백준 2021. 1. 7. 16:11
가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 부분 수열은 요소들의 증감이 변곡점을 하나 이하로 가진 부분 수열이다. 즉, {1, 3, 5, 6, 4} 혹은 {1,2} 혹은 {7,3,5}와 같은 수열들이 바이토닉 수열이라 할 수 있다. 이 문제를 풀기 위해서는 LIS, LDS에 대한 개념이 있어야한다고 한다. LIS => Longest Increasing Subsequence (최장 증가 부분 수열) LDS => Longest Decreasing Subsequence (최장 감소 부분 수열)..
-
BOJ) 최솟값과 최댓값 (2357 번)알고리즘/백준 2021. 1. 5. 18:24
최솟값과 최댓값 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 앞서 포스팅한 세그먼트 트리를 활용하는 문제다. 위의 문제와 차이점이라면 구간 합을 구하는 대신, 최솟값과 최댓값을 저장한다는 점이다. 또한, 이 문제에서는 세그먼트 트리의 크기를 직접 구해서 초기화해줬다. 세그먼트 트리 초기화 private static class SegmentTree { int[] minTree, maxTree, numArr; private int size; public SegmentTre..
-
BOJ) 구간 합 구하기 (2042 번)알고리즘/백준 2021. 1. 5. 18:09
구간 합 구하기 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리를 이용해서 푸는 문제다. 우선, 이 문제를 풀기 위해서 세그먼트 트리에 대해서 공부해야했다. 백준 사이트에 블로그란에 기재되어있는 세그먼트 트리를 보고 풀었다. 세그먼트 트리란 무엇인가?? 먼저, 세그먼트 트리는 배열의 크기가 커질 경우, 연산 식에 유용하다. 공간 복잡도가 O(N^2)이고 시간 복잡도가 O(N^2)인 배열에 대한 연산이 있다면, 세그먼트 트리를 이용하여 O..
-
BOJ) 줄 세우기 (2252 번)알고리즘/백준 2021. 1. 2. 16:20
줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 오랜만에 포스팅을 하게 된 이유는 위상 정렬에 대한 정리를 하기 위해서이다. 위키에 따르면 위상 정렬(topological sorting)은 방향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 가장 대표적인 예로 대학의 선수과목(prerequisite) 구조를 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 ..
-
BOJ) 평범한 배낭알고리즘/백준 2020. 8. 28. 16:49
평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 짐의 개수 n, 버틸 수 있는 무게 k, n개 만큼의 짐의 정보 (무게 w, 가치 v)가 주어진다. 최대한 k에 맞추어, 최대 가치(max v)를 찾는 문제다. dp의 크기를 최대 가치 k까지 입력받을 수 있도록, k+1만큼 생성해준다. 짐의 정보를 순회하면서 w와 v를 가져온다. 그리고 k 부터 w까지 무게를 줄여나가면서, 현재 무게 ( i )의 dp값(가치) 과 dp[i-w] ..