Online Judge

https://www.acmicpc.net/problem/11286문제 힙에 넣고 빼는 간단한 문제인데, 힙에서 정렬 기준이 절댓값이다. 절댓값이 같다면 작은 순으로 정렬한다. 풀이 절댓값을 이용하기 위해 0보다 작은 경우 -1을 곱해 힙에 넣으면 원래 값을 알 수 없게 되기 때문에 절댓값을 구하여 힙에 넣는 것은 아니다.파이썬에는 heapq(참고링크)를 통해 편리하게 힙을 사용할 수 있는데, heapq의 heappop, heappush는 단일 값 뿐 아니라 리스트도 지원한다. 리스트의 정렬 기준은 리스트의 인덱스 순이다. 따라서 절댓값과 원래값을 리스트에 담아 힙에 넣으면 절댓값 순으로 정렬되면서 원래값도 보존할 수 있다.참고로 입력이 많으므로 sys를 사용하여 입력받아야 한다. 코드 import he..

https://www.acmicpc.net/problem/10164문제 오른쪽과 아래쪽으로밖에 이동하지 못하는 로봇이 제시된 공간에서 이동하는 경로의 경우의 수를 구하는 문제이다. 만약 동그라미가 표시된 공간이 있다면 반드시 지나야 한다. 풀이 고등학교 확률및통계에 나오는 최단거리 경우의 수를 활용하면 된다. 최단거리가 되는 이유는 로봇이 오른쪽과 아래쪽으로 밖에 못 움직이기 때문이다. 즉 로봇이 오른쪽으로 이동하거나 아래쪽으로 이동하는 두 개의 경우를 나열한 경우의 수를 확인하면 된다.최단거리 문제에서 $ n \times m $ 에서의 경우의 수는 $ C(n+m, n) $, 즉 $ \dfrac{(n+m)!}{n! \times m!} $ 이다. 그런데 이 경우는 선에서 움직이는 경우이고, 문제는 격자에서..

https://www.acmicpc.net/problem/11722문제 주어진 수열의 부분 수열 중 가장 긴 감소하는 수열을 찾는 문제이다. 풀이 각 인덱스에서 감소하는 수열의 최대 길이를 확인하고 그 중 가장 큰 값을 출력하면 된다.어떤 인덱스를 i라 하면 에서 감소하는 수열의 최대 길이는 i보다 앞 인덱스의 수 중 num[i]보다 큰 수를 찾고, 그 중 그 인덱스의 감소하는 수열의 최대 길이를 확인하여 1을 더하면 i에서의 감소하는 수열의 최대 길이가 된다.예제로 주어진 아래 수열을 확인해보자.10 30 10 20 20 1010은 자신보다 앞에 수가 없으므로 0에서의 감소하는 수열의 최대 길이는 1이다. 30 역시 자신보다 앞에 수 중 자신보다 큰 수가 없으므로 1이다. 10은 앞 수 중에 30이 자..

https://www.acmicpc.net/problem/27907문제 임의 길이의 소수 등차수열을 출력하는 문제이다. 풀이 여러 고민을 하면서 다양한 풀이방법을 시도했지만, 풀리지 않았는데, 풀이 방법을 찾아보니 공차에 대한 조건이 없으므로 그냥 임의의 소수를 주어진 길이만큼 출력하는 문제였다.즉 일반적인 답이 없다는 것을 빨리 알아차리고, 문제의 허점을 찾아야 하는 문제였다. 코드 print(*([2 for _ in range(int(input()))]))

https://www.acmicpc.net/problem/23886문제 주어진 수가 조건에 맞는 수인지 확인하는 문제이다.조건은 연속으로 오르거나 내릴 때 각이 같아야 하고, 시작은 증가, 끝은 감소이다. 풀이 먼저 주어진 수를 리스트 컴프리헨션을 이용해 리스트로 바꿔준다. 그냥 문자열로 처리하거나 숫자로 입력받고, 자릿수로 분해해주어도 되겠지만, 이 방법이 가장 편할 듯 하다.다른 조건을 검사하기 전에 시작과 끝의 각도를 확인하고, 시작이 감소이거나 끝이 증가이면 알프수가 아니므로 처리한다.그 후 각각의 각을 확인하면서 조건에 맞는지 확인한다.이전 각이 음수면서 지금 각도 음수인데 두 각이 다르면 알프수가 아니고, 이전 각이 양수면서 지금 각도 양수인데 두 각이 다르면 알프수가 아니다. 코드 num =..

https://www.acmicpc.net/problem/20436문제 주어진 키보드 조건에서 주어진 문자열을 타이핑하는 데에 걸리는 시간의 최솟값을 구하는 문제이다. 풀이 키보드 좌표를 구하는 부분과 키보드 타이핑 시간을 구하는 부분이 필요하다.키보드 좌표를 구하는 부분은 아래와 같이 리스트 속 문자열을 만들고, 여기서 해당 문자를 탐색하는 방식으로 만들어도 된다.keyboard = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']그러나 오른손과 왼손을 구분하는 것 때문에 각 문자에 좌표를 설정해서 딕셔너리로 찾는 것이 더 직관적이고 좋은 것 같아 아래 코드와 같이 구현했다.타이핑 시간 계산은 문제에서 제시한 방식을 그대로 사용하였다. 코드 lkeyboard = {'z':(0,0),..

https://www.acmicpc.net/problem/31418문제 정해진 스펀지 내에서 일정 시간이 흘렀을 때 바이러스들의 분포의 수를 구하는 문제이다. 바이러스들은 1초에 대각선, 상하좌우 중 한 방향으로 한 칸 이동하거나 움직이지 않을 수 있다. 풀이 바이러스가 어디에 있을 수 있냐를 구하는 문제이다. 바이러스는 좌우로는 최대 $ T $ 만큼 이동할 수 있고, 상하로도 최대 $ T $ 만큼 이동할 수 있다. 대각선도 마찬가지이니 바이러스 위치는 $ (2 \times T + 1) \times (2 \times T + 1) $ 개의 가능성을 가진다.그런데 바이러스는 스펀지에서 벗어나진 못하므로 바이러스가 이동하다가 좌우측, 상하측으로 스펀지에 막힐 가능성을 생각해야 한다. 만약 바이러스가 이동할 수..

https://www.acmicpc.net/problem/9414문제 각 테스트 케이스에 따라 규칙적으로 증가하는 땅값을 확인하고, 구매할 수 있다면 구매하는데 필요한 비용을, 구매할 수 없다면 "Too expensive"를 출력하는 문제이다. 풀이 파이썬은 데이터의 크기에 따라 메모리를 동적으로 할당하기 때문에 큰 수를 다루기 용이하다. 따라서 문제 그대로 모든 땅값을 구하고, 상근이 가진 돈과 비교해서 너무 비싸면 "Too expensive"를 출력하면 된다. 만약 C++, Java 와 같이 데이터 타입에 따라 범위가 정해져 있는 언어를 사용한다면 땅값을 더해주면서 상근이 가진 돈과 비교하면 되겠다.땅값을 구하는 공식은 $ 2 \times (L_i)^t $ 인데, 해가 지날수록 기하습수적으로 증가한다..

https://www.acmicpc.net/problem/14381문제 각 테스트 케이스에 대해 입력을 받고, 주어진 규칙에 따라 숫자를 기록한 후, 조건에 부합하면 해당 숫자를 출력하는 문제이다.주어진 규칙은 주어진 수를 1, 2, 3 으로 곱해나가면서 각 자리 수에 있는 숫자를 기록하는 것이고, 조건은 그렇게 기록된 숫자가 0 부터 9 까지 있을 때 이다.  풀이 입력을 받고, 1 부터 시작해서 계속 곱해나가며 각 자리 수에 있는 숫자를 기록하면 된다. 단 입력으로 0 이 들어오게 되면 무엇을 곱해도 0 이 되어 0 부터 9 까지 수를 기록할 수 없으므로 조건에 따라 INSOMNIA 을 출력한다.기록할 때는 set 을 이용하여 집계하면 편할 것 같아 set 을 사용하면 좋을 듯 하다. 0 부터 9 까..

https://www.acmicpc.net/problem/10816문제 상근이가 가지고 있는 숫자 카드 묶음에서 주어진 숫자 카드들을 몇 개씩 가지고 있는지 구하는 문제이다. 풀이 상근이가 가지고 있는 숫자 카드 묶음은 입력받아 리스트로 만들어 주면 된다.이 문제의 핵심은 많은 카드 가운데 해당 숫자가 적혀있는 카드를 얼마나 빨리 찾느냐는 것이다. 일반적으로 count 함수를 사용하거나, in 함수를 사용하면 리스트에서 하나 하나 탐색하기 때문에 시간 복잡도가 $ O(n) $ 이 되고, 탐색을 모든 카드에 대해 해야하기 때문에 전체 탐색 알고리즘의 시간 복잡도가 $ O(n^2 ) $ 이 되게 된다. 따라서 탐색을 빠르게 하는 것이 중요하다.C 와 같은 언어에서는 카드 묶음을 정렬하고 이분 탐색을 이용하여..