소근소근

백준 3665 최종 순위 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬 문제이다. 2차원 배열에 edge를 저장하는 방식으로 풀었다. int nf, nt; cin >> nf >> nt; /*if (adj[nt][nf] == 1) { adj[nt][nf] = 0; indegree[nf]--; } adj[nf][nt] = 1; indegree[nt]++;*/ if (adj[nf][nt]) { adj[nf][nt] = 0; adj[..

백준 1516 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 어떤 건물을 짓기 전에 먼저 지어야 하는 건물이 있다는 조건에서 위상정렬을 떠올릴 수 있다. #include #include #include #include #include #include #include using namespace std; int N; int period[501]; vector adj[501]; int indegree[501]; int dab..

백준 문제집 1766 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1부터 N까지의 문제를 푸는 순서를 출력한다. 조건은 두가지다. 1. 되도록 쉬운 문제 먼저 푼다.(작은 숫자 문제 먼저 풀어야 한다) 2. 먼저 푸는 문제가 있으면 먼저 풀어야 한다. (두 문제 간에 우선순위가 있다.) 문제 간의 우선순위를 지키면서, 쉬운문제를 풀어야 한다. 1번조건을 충족하기 위해서 우선순위 큐를 사용하고, 2번 조건은 위상..

백준 1715 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 카드 묶음 A와 B를 묶기 위해서는 A+B만큼의 비교가 필요하다. 여러 묶음이 있을 때 다 하나의 묶음으로 만들기 위해 필요한 '최소' 비교 회수를 구해야 한다. 작은 것부터 묶었을 때가 최소가 되는 것을 예제를 보면 쉽게 알 수 있다. priority queue를 사용해서 작은 것부터 묶고, 묶고난 것을 다시 queue에 넣어주면서 반복한다. 처음에 q..

백준 11053 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 어떤 수열이 주어졌을 때, 가장 긴 증가하는 부분수열의 길이를 출력하는 문제이다. dp[N] 배열을 선언하고, dp[N]에는 N번째 수를 마지막 원소를 갖는 가장 긴 증가하는 부분수열(lis)의 길이를 저장한다. O(N^2)으로 푼다. 이중 포문을 돌면서, 현재 수보다 1 작..

백준 내려가기 gold 4 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net N*3 배열이 주어지고, 위에서부터 인접한 위치로 내려가며, 최댓값과 최솟값을 출력하는 문제이다. 평범한 dp로 풀면 될 것 같다. 그런데.. 메모리 제한이 4MB이다. 즉, 일반적으로 생각하는 dp배열을 만들어서 푸는 풀이는 메모리 초과가 나게 된다. sliding window기법을 사용한다. 전체 배열 크기만큼 dp배열을 만드는 게 아니라 실질적으로 필요한 데이터만 저장할 수 있게..

한동안 알고리즘에 손을 대지 못하다가 최근 다시 백준을 풀기 시작했다.. 백준을 풀다 보면 수많은 런타임 에러, 틀렸습니다, 시간 초과를 보게 된다. 내 코드를 보면서 아니 대체 왜? 맞는데? 예외처리 다 했는데 맞왜틀??!?! 을 정말 많이 외쳤었다. 하지만 컴퓨터는 거짓말을 하지 않지.. 내가 무조건 잘못한게 맞다 ^^ 그래서 오랜만에 알고리즘 공부를 하기 전에 알고리즘 풀 때 마주치는 에러에 대해 내가 보기 위해 정리하기로 했다. 1. 컴파일 에러(compile error) 보통 비주얼 스튜디오에서 예제 코드를 돌려보고 내기 때문에 주로 마주치는 에러는 아니다. 코드에 쓴 함수나 자료구조를 사용하기 위해 필요한 헤더를 모두 선언 해 주었는지 확인해보자. 그래서 보통 알고리즘을 풀때 자주 쓰는 헤더를..