OSgood의 개발일기

https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개의 줄에는 1번 노선부터 순서대로 각 버스 노선 [a,b]를 나타내는 두 개의 정수 a와 b가 한 줄에 주어진다, 단, 0 ≤ a, b ≤ N-1이고 a≠b이며 동일한 버스 노선이 두 번 이상 입력으로 주어지는 경우는 없다. www.acmicpc.net 12345678910111213141516171819202122232425262728293031323334353637383940414..

https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지름이 2인 원 위에는 좌석이 2개, 이런 식으로 반지름이 D 인 원 위에는 좌석이 D 개가 있다. 또한, 무대에서 정확히 북쪽 방향에는 모든 원들에 좌석이 있으며, 하나의 원 위에 있는 좌석들은 동일한 간격을 두고 배치되어 있다. 이번 공연에 반지름이 D1보다 같 www.acmicpc.net 1234567891011121314151617181920212223242526272829303132333435363738394041424..

https://www.acmicpc.net/problem/10837 10837번: 동전 게임 첫 줄에 게임의 라운드 수를 나타내는 정수 K(1 ≤ K ≤ 1,000)가 주어진다. 두 번째 줄에는 입력의 개수를 나타내는 정수 C(1 ≤ C ≤ 100,000)가 주어진다. 다음 이어지는 C개의 줄 각각에는 하나의 입력을 나타내는 두 정수 M과 N(0 ≤ M, N ≤ K)이 주어진다. www.acmicpc.net 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061//백준 10837번 동전 게임#include #include using namespace std;..

전형적인 priority_queue(minheap)를 이용하는 문제이다. https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 www.acmicpc.net 123456789101112131415161718192021..

문제 링크 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net 전형적인 탐색 문제다. bfs를 해도 되고 dfs를 해도 상관 없다. 필자 같은 경우는 dfs가 좀 더 편하기 때문에 dfs로 코드를 작성..

전형적인 bfs 문제이다. 처음에 구조를 조금 잘 못 잡아서 코드자체가 굉장히 읽기 않좋아진 것 같다. 방문했던 노드들을 저장하면서 가는게 효율적인 것을 알면서도 조금 귀찮다고 방문했던 노드들을 저장하지 않고 단순 방문을 했을 때 시간초과가 나서 map을 이용해서 방문했던 노드들을 1로 표시해서 코드를 수정하였다. 처음에 조금 귀찮아서 코드를 막 짜다보니 오히려 굉장히 코드가 더러워진 것 같다. 이런 안 좋은 습관을 최대한 고쳐야겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808..

2016 천단위 구분기호 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace std;int main() { int a; char cs[1000]; stack st; vector result; cin >> a; cin >> cs; int i = 0; while (cs[i] != '\0') { st.push(cs[i]); i++; } char tmp; int cnt = 0; while (!st.empty()) { cnt++; if (cnt % 4 == 0) { result.push_back(','); } else { tmp = st.to..

이번 포스팅에서는 Dynamic Programming의 개념적인 내용을 살펴보겠다. 자세한 적용 예는 좀 더 공부한 후에 더 자세히 포스팅하도록 하겠다. Dynamic Programming는 간단히 말해 부분 문제의 해를 결합해 문제를 해결하는 것을 의미한다. 부분 문제가 서로 중복될 때,즉 부분 문제가 다시 자기 자신의 부분 문제를 공유할 때 적용할 수 있다. 부분문제를 푸는 것은 분할정복 기법(재귀방법)과 비슷하지만 다른 점이 있다. 분할 정복 기법 VS Dynamic Programming 분할 정복 기법(재귀적 방법) Dynamic Programming 부분 문제를 단순히 반복적으로 계산하여서 해결한다. 필요 이상의 계산이 필요하기 때문에 시간이 오래걸릴 수 있다. 부분 문제를 해결한다는 점은 분할..