본문 바로가기

알고리즘/백준

 (89)
백준 11437 LCA https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA라는 새로운 알고리즘을 도입했다. Segtree를 이용해서 풀었는데 코드가 좀 지저분하다. LCA 알고리즘에 대한 공부를 하고, 그것을 연습하기에 좋은 문제라 생각한다. /* LCA */ #include #include #include #include #define pp pair #define MAX_NODE 50000 + 1 using namespace std; int N, max_..
백준 2493 탑 C++ https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net DP로 풀 수 있고 Stack으로도 풀 수 있다. 둘 다 어렵지 않은 풀이지만, Stack 풀이가 뇌용량을 덜 쓴다. 우선 Dp로 풀었다. 만약 탑이 6 4 5 7 3 순으로 배치되어있다면 답은 "0 1 1 0 4" 이다. 여기서 '5'를 잘 봐야하는데, 5는 일단 바로 앞의 값을 본다. '4'다. 본인보다 높이가 낮으므로 전파가 닿지않는다. 무식하게 할 경우 여기서 6을 보게 된다. 운 ..
백준 10868 최솟값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 세그먼트 트리를 활용하는 문제다. 문제를 읽다보면 대놓고 세그먼트 트리를 활용하라는 것 같다... /* 최솟값 */ #include #include #include #include using namespace std; void solve(); int seg_init(int s, int e, int node); int seg_find(int s, int e, in..
백준 2104 부분배열 고르기 https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 문제 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 �� www.acmicpc.net 세그먼트 트리를 활용한 문제다. 그냥 재귀를 활용할 수도 있지만 만약 가장 작은 수가 배열의 양 끝일 경우 O(N^2)가 되기 때문에 시간초과에 걸린다. 그리고 자료형도 신경써야한다. pair를 활용한 세그먼트 트리로 해결했다 /* 부분 배열 고르기 */ #include #include #include #include ..
백준 2014 소수의 곱 https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 �� www.acmicpc.net 우선순위 큐를 이용하는 문제다. 코드는 간단하다 아이디어도 간단하다. 자료형 실수만 하지 않으면 금방 풀 수 있을 것 같다. /* 소수의 곱 */ #include #include #include #include #include #define INTMAX 2147483647 using namespace std; int n_of_decimal, target; int d..
백준 10159 저울 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 백준의 '여행 가자'라는 문제랑 흡사하다. 이 문제도 두 가지 버전으로 풀 수 있다. 첫 번째가 BFS, 두 번째가 플로이드 와샬 이다. 우선 BFS부터 살펴보자. 이 그래프는 단방향 그래프이고 양방향이 절대 될 수 없을 뿐더러 사이클도 생길 수 없기 때문에 트리구조다. 그래서 한 정점에서 BFS를 돌릴 때 접근되는 모든 점은 시작 정점보다 가볍다. 이 때 주의할 건 'A..
백준 1976 여행가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행가고싶다... 이 문제는 두 가지 방법으로 풀 수 있다. 첫번째는 BFS, 두번쨰는 Union-Find이다 두 코드 다 수록했다. BFS로 푸는 건 각 정점간의 연결관계를 확인하는 방법이다. 예를 들어서 A - B, B - C가 연결되어 있을 때 A를 시작점으로 BFS를 돌리면 당연히 C까지 연결된다. A를 시작으로 하는 BFS를 돌리면서 도착하는 정점마다 A와 연결되어있다고 표시해두면 문제를..
백준 15684 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 구현을 하면 되는데... 그 구현이... 너무 빡세다.... 가능한 모든 케이스를 대입하면 된다. 즉, 일일이 사다리를 넣어보고 주어진 조건을 만족하는 지 체크한다(이걸 무한반복...) /* 사다리 조작 */ #include #include #include using namespace std; void input(); void solve(); int N, M, H; bool ghost_leg[3..
백준 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 문제 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 www.acmicpc.net 이분탐색과 BFS(혹은 DFS)를 활용한 문제. 이분탐색은 '가능한 최대'라거나 '가능한 최소' 등의 키워드에 맞춰 사용하면 될 것 같다. /* 배열에서 이동 */ #include #include #include #include using namespace std; int n, small, large; int map[100 + 1][100 + 1]; bool is_visit..
백준 2629 양팔 저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 백 트랙킹과 DP를 활용하는 문제다. 적은 N과 상대적으로 널럴한 시간 제한을 보자마자 백트랙킹 감이 오긴했으나... 아직 recursion 알고리즘을 짜는 게 미흡한 것 같다. 이렇게 ''완전탐색''을 하면 반드시 풀 수 있는 문제를 백트랙킹과 DP로 구현할때는 각 케이스에서 발생 가능한 모든 사례를 Recursion으로 처리하는 연습을 해야겠다. ㅠㅠ /* 양팔 저울 */ #include #in..

티스토리툴바