알고리즘 (100) 썸네일형 리스트형 백준 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.. 백준 1613 역사 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. �� www.acmicpc.net 플로이드 워셜 알고리즘을 활용하는 문제다. N이 400밖에 안되므로 O(N^3)을 해도 6400만이라서 시간초과에 걸리지 않는다. /* 역사 */ #include #define MAX_N 400 + 1 #define MAX_EDGE 50000 + 1 using namespace std; int n, k, s; int order[MAX_N][MAX_N]; int main(void) { .. 백준 5427 불 https://www.acmicpc.net/problem/5427 5427번: 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. www.acmicpc.net BFS를 이용한 간단한 구현문제이다. /* 불 */ #include #include #include #include #include #define EMPTY '.' #define WALL '#' #define SANGEUN '@' #define FIRE '*' using namespace std; int W, H; int dr[4] = { -1,0,1,0 }; int dc[4] = { 0,1,0,-1 }; v.. 백준 17144 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 간단하진 않은 구현문제다. 문제에 주어진 조건대로 구현하면 된다... /* 미세먼지 안녕! */ #include #include #define MAX_N 50 + 1 using namespace std; void input(); void solve(); int R, C, T; int A[50 + 1][50 + 1]; int dr[4] = { -1,0,1,0 }; int dc[4] = { 0,1,.. 백준 2213 트리의 독립집합 https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 �� www.acmicpc.net 너무 어려웠다... 트리 DP를 쓰는 문제였다. 트리 DP의 기본 구조는 이렇게 생겼다. int treeDp(int curr, int before){ for(int i = 0; i < edge[curr].size(); i++){ int nxt = edge[curr][i]; if(nxt == before) continue; treeDp(nxt, curr); dp.. 이전 1 ··· 4 5 6 7 8 9 10 다음