알고리즘 (100) 썸네일형 리스트형 백준 7579 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활�� www.acmicpc.net DP와 Knapsack이 결합된 문제이다. 이 문제가 Knapsack 문제라는 걸 파악하기만 한다면, 푸는 거 자체는 그리 어렵지 않다고 생각한다. 보통 최대 Cost를 Column으로 하고 각각의 배낭(여기서는 앱)을 Row로 하기때문에 이 문제의 최대 M이 1,000,000 이므로 KnapSack 문제가 아니라고 생각했었다. KnapSack의 시간복잡도는 O(N * M) 즉 100 * 1,000,.. 백준 2352 반도체 설계 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net LIS 알고리즘 문제다. 밑의 알고리즘에서 이진탐색을 이용해서 idx 값을 구했기 때문에 탐색에 O(logN)이고 N개의 숫자에 대해 이 탐색을 실행하기 때문에 O(NlogN)이다. 이 문제는 LIS를 구할 때 "어떤 수열이 LIS인가?"를 묻지 않았기 때문에 그냥 개수만 찾았다. 그러면 arr에 들어있는 수열은 실제 LIS와 다를 확률이 아주아주 높다. 추적을 할 때는 ind.. 백준 1918 후위 표기식 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식�� www.acmicpc.net 후위 표기식을 하는 것 주의할 점은 우선순위가 낮은 연산자일수록 Stack에 오래 남아있어야 한다. 그래야 나ㅏㅏㅏ중에 나오게 된다. 코드를 보면 무슨 말인지 확 이해될 것이다. *나 /가 등장하면 stack에서 *나 / 이외의 연산자를 만날 때까지 pop을 하고 결과 문자열에 더해준다. 그 결과 '(' 와 '+' '-'는 stack에서 pop 되지 않는다. /* 후위 표기식 */ #.. 백준 10217 KCM Travel https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net 다익스트라 알고리즘...으로 풀면되는데 변수명을 막 지었다가 시간만 엄청 날린 문제다... K와 M을 헷갈리다니...후... /* KCM Travel */ #include #include #include #include #define MAX_N 2100000000 #define pp pair class node { public: int cost, time,.. 백준 1202 보석 도둑 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 우선순위 큐를 이용하는 문제인데... 이런게 정말 창의력 문제라고 생각한다. 어떻게 이런 풀이를 생각하는건지... 결국 풀지 못하고 다른 사람의 답을 봤다. 그리고 30분동안 감탄했다. 이 문제를 내는 사람이나, 푸는 사람이나... 대단해 이 문제에서 중요한 점은 가방에 들어갈 수 있는 보석의 무게가 '최대'라는 점이다. 즉 10kg을 넣을 수 있는 가방이라도 3kg만 넣어도 된다. 이게 .. 백준 1517 버블 소트 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 머지 소트를 이용하는 문제다. 제일 처음에 한 숫자를 기준으로 오른쪽에 본인보다 작은 숫자가 많은 개수만큼 sorting을 해야한다는 점에 착안해서 문제를 풀려고 했는데 잘 되지 않았다. Merge Sort로 푸는 방법이 신박하다. 결국 정렬된 형태의 배열과 원래 배열 사이에 얼마나 많은 Cross 가 생기는가! 이걸 센다. /* 버블 소트 */ #include #include #defi.. 백준 1516 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬 문제다. 차이가 있다면 '시간'이라는 변수가 추가된 것! 보통은 'C건물이 완성되려면 A건물과 B건물이 완성되어야 합니다' 라는 문제조건에 따라 inedge의 개수만 세면 되는데 이 문제는 '시간'이 기준이어서 A건물과 B건물이 완성되는 시간 모두를 고려하는 게 아니라 둘 중 더 늦게 완성되는 건물의 완성 시간을 기준으로 잡아야 한다. 즉 Queue가 아니라 priority Q.. 백준 9935 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 www.acmicpc.net Stack을 활용하는 문제다. 정확히 말하면 STL이나 여타 라이브러리가 아니라 Stack의 LIFO을 이용한다. 백만이나 되는 Input과 2초 밖에 안되는 시간제한을 고려했을 때 별다른 선택지가 없었다. 비교 연산을 1억번 할 때 1초 정도가 들기 때문에 2초면 비교 연산만 고려해도 2억번 이내로 해결해야한다. 하지만 Input이 100만 이기 때문에 N^2는 최악의 경우 100 0000 * 100 .. 백준 9019 DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스� www.acmicpc.net 간단한 구현 문제인데 시간초과가 빡세다... 완전 탐색으로 풀면된다. 처음엔 map 자료형과 bfs를 혼합해서 풀었는데 시간초과가 떳다. map 자료형이 시간이 꽤 드는 듯... 역시 임의 접근만큼 빠른게 없다. 방문 체크를 할 bool array를 하나 만들어서 작업을 했다. /* DSLR */ #include #include #include #include using names.. 백준 5214 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 문제 아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입 www.acmicpc.net BFS를 쓰면 되는 문제이지만 메모리 초과가 문제가 된다 . Edge를 연결하는 과정에서 브루트포스를 적용하면 무려 10 ^ 9가 된다. 일일히 두 개를 연결하지 않고 Hub처럼 동작할 dummy 노드를 하나 만들면 공간복잡도를 크게 줄일 수 있다. 앞으로도 유용하게 쓸 수 있는 스킬인 것 같다. /* 환승 */ #include #include #include #define MAX 100000 + 1 us.. 이전 1 ··· 5 6 7 8 9 10 다음
