본문 바로가기

알고리즘

 (100)
백준 14725 개미굴 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 � www.acmicpc.net 트라이 문제다. 기존의 struct에서 alphabet 개수만큼 배열을 할당한 대신 map으로 바꾼것 말고는 동일하다 . /* 개미굴 */ #include #include #include #include using namespace std; void input(); void solve(); int N; struct trieNode { bool is_terminal; map tri..
백준 10165 버스 노선 https://www.acmicpc.net/status?user_id=museum114&problem_id=10165&from_mine=1 채점 현황 www.acmicpc.net 이런 문제는 경우의 수를 잘 쪼개는 게 중요한 것 같다. 이 문제를 어렵게 만드는 요인은 바로 '원형'이라는 점이다. 우리가 보기에는 원형이든 선형이든 상관없지만 컴퓨터에게 이 문제는 꽤 중요하다. 인덱스가 달라지기 때문이다. 그래서 0(중심점)을 넘어서는 버스 노선은 특별한 연산을 거친 후 vector에 넣었다. 자세한 건 코드로 확인하시라~ /* 버스 노선 */ #include #include #include #include #define ll long long int #define pp pair using namespace..
백준 1256 사전 https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍을 사용하는 문제다. k-th lexicographical string 문제는 문자열 DP 문제에 자주나오는데 이 참에 정리를 해야겠다. /* 사전 */ #include #include #define ll long long int using namespace std; void input(); void solve(); int N, M, K; /* 사실 j에 해당하는 오른쪽 배열은 201로 할 필요가 없지만 연산 코드를 줄이기위해..
백준 17140 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 구현..구현 문제다... 아 힘들어... /* 이차원 배열과 연산 */ #include #include #include #include #define pp pair using namespace std; void input(); void solve(); inline bool comp(pp& a, pp& b) { if (a.second == b.second) { return a.first..
백준 5719 거의 최단 경로 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 다익스트라 한 번 돌리고 최적경로 지우고 다익스트라 한 번 돌리면 풀 수 있는 문제다. 아이디어가 직관적으로 떠오르는데, 구현이 까다로운 문제 edge는 점과 Weight를 동시에 저장한다. trace에 최적 경로를 저장한다. dist는 S로부터 모든 점까지의 최단 거리를 계산한다. /* 거의 최단 경로 */ #include #include #include #de..
백준 5557 1학년 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀�� www.acmicpc.net 다이나믹 프로그래밍. 중요한 건 시작할 때 (0,0)으로 시작하면 안된다는 점이다. 이럴 경우 4 0 0 0 0 같은 반례에 걸린다. 무조건 첫 값을 지정해줘야한다. /* 1학년 */ #include #include #include #include #define ll long long int using namespace std; void input(); void solve(); int ..
백준 1162 도로포장 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포�� www.acmicpc.net 양수 weight의 간선으로 이루어진 그래프에서 한 점으로부터 다른 점까지의 최단거리를 구하는 알고리즘은 다익스트라알고리즘이다. 이 문제는 여기서 한 술 더 뜬다. 내가 원하는 간선의 weight를 0으로 만들 수 있다! 이것만 잘 생각하면 일반적인 다익스트라 문제와 똑같다. N개 중에 K개를 고르는 문제는 어떻게 풀어야할까? N개 중에 K개를 고르는 모든 경우의 수를 구할 수도 있다. 즉 next_p..
백준 1701 Cubeditor https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고�� www.acmicpc.net KMP 알고리즘...? 을 활용하는 문제다. 시작점을 하나씩 옮겨가면서 failed 배열을 채운다 이 failed 배열은 보통 'pi' 로 표현하는 그 배열이다. 이 배열에서 가장 큰 값이, 가장 긴 문자열의 길이라는 걸 활용하면 문제를 풀 수 있다. /* Cubeditor */ #include #include #include #include using ..
백준 14425 문자열 집합 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어� www.acmicpc.net 문자 prefix, suffix 어느 문자 집합에 넣는다는 류의 문제는 트라이를 생각해봄직하다(+ 공간복잡도가 널럴할 때) 이 문제도 트라이를 이용해서 풀 수 있다. /* 문자열 집합 */ #include #include using namespace std; struct trieNode { bool is_terminal; trieNode* trie[26]; tri..
백준 2437 저울 https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 그리디 알고리즘을 이용한 문제다. 부분합을 이용할 생각을 하다가 '에이 아니겠지' 했는데 부분합을 이용하는 문제여서 반성하게 된다. 수학 문제를 풀 때도 그랬지만 Try가 중요한 것 같다. 내 생각에 대해서도 자비의 원칙을 적용했다면, 이 문제를 수월하게 풀수도 있지 않았을까. /* 저울 */ #include #include #include using namespace std; vector chu; int..

티스토리툴바