본문 바로가기

전체 글

 (84)
백준 2473 - 세 용액 www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 이 문제는 알고리즘 & 자료구조를 공부한다면, 반드시 한 번쯤은 거쳐가고, 거쳐야만 하는 기본적(?)이면서도 중요한 문제라고 생각한다. 그리고 다양한 풀이가 있을 수 있어서 좋다. 위의 그림은 문제에서 주어진 예제를 다루고 있다. 항상 그렇듯이 이 문제에서도 정렬의 힘을 다시 느낄 수 있다. 입력을 받은 후 정렬하고, 총 3개의 수를 뽑아야 하므로 루프 2개로 2개를 뽑아준다 (여기까지 O..
AtCoder : ABC 178 D - Redistribution atcoder.jp/contests/abc178/tasks/abc178_d D - Redistribution AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 이 문제 역시 대표적인 형식의 DP문제이다. 앞선 포스팅에서 살펴본 간단한 DP문제들은 이전 히스토리에서 한 개나 두 개 정도를 참조하여 현재의 값을 구하였다 (기본 피보나치 수열은 이전 값 2개를 참조하여 현재의 값을 구한다). 하지만 이번에는 꽤나 많은 값을 가져와야 한다. 수열의 합이 S가 되고, 각 수는 3이상이므로 첫 수는 항상 3부터 시작해서 따져봐도 좋다..
AtCoder : ABC 178 C - Ubiquity atcoder.jp/contests/abc178/tasks/abc178_c C - Ubiquity AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp DP문제이다. 점화식을 파악할 수 있다면 쉽고 간단한 문제겠지만, 그게 떠오르지 않는다면 역시 어렵다... 이러한 문제에 대해 어떻게 접근해야 할까? 이전 포스팅들에서 꾸준히 얘기하고 있지만, 필자가 이해하는 동적계획법(DP) 적용의 근거는 어떠한 정점(상황)에서 일정한 규칙을 적용하여 일정한 간격만큼 떨어진 다음 정점으로 넘어갈 때에 있다. 어떠한 정점에서 연결된 정점이 한 ..
Codeforces Round #667 (Div.3) Problem - D codeforces.com/contest/1409/problem/D Problem - D - Codeforces codeforces.com 이 문제는 숫자가 매번 증가하기만 할 뿐이라는 점에 착안해야 한다. 27이라는 숫자가 있을 때, 각 자리에 있는 숫자들은 2와 7이다. 그리고 그들의 합은 9. 지금부터 편의상 9를 27의 '숫자합'이라고 부르겠다. 7이라는 숫자가 있다고 한다면, 7에서 1을 증가시키면 8이 된다. 8은 7보다 숫자합이 크다. 8에서 또 1을 증가시키면 9가 되고. 9의 숫자합은 8의 그것보다 크다. 여기까지 보면, 숫자를 1씩 증가시키기 때문에 숫자합은 점점 커질 뿐이다. 하지만! 수가 길어질 때 (자릿수가 하나 더 생겼을 때) 드디어 숫자합은 작아질 수 있다. 방금 전 예시의 9..
백준 2075 N번째 큰 수 www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 이 문제는 정렬 또는 우선순위 큐를 통해 해결할 수 있다. 문제의 메모리 제한을 눈여겨 보자. 12MB로 평소와 다르다. int형 정수 1개는 4byte를 갖는다고 한다. 1천개면 4kb이고, 1백만개면 4MB이니 12메가 바이트는 겨우 3백만개의 정수만 담을 수 있는 것이다. 문제의 조건에서 N이 1500이므로 1500 x 1500 = 2,250,000 (225만)개의 정수가 필요하므로 다 담을 수 있을 것 같지만,..

티스토리툴바