buzz

문제 https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 숫자를 리스트로 받아 정렬한 후 리스트의 인덱스는 0부터 시작하므로 k-1번째 숫자를 출력하면 된다. 코드 -파이썬 #백준 11004(K번째 수) n, k = map(int, input().split()) num = list(map(int, input().split())) num.sort() print(num[k-1])

문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 해설 이 문제는 정렬이라고 해서 정렬 내장 함수를 사용하면 메모리 초과가 발생한다. 10,000까지 입력 가능하기 때문에 이를 리스트로 먼저 만들어 놓고 각 숫자별로 입력받은 횟수만큼 1을 더해주면 된다. 그리고 나서 10001번 만큼 반복문을 돌며 리스트의 i값이 0이 아닐 경우 i를 횟수만큼 출력하면 된다. 코드 -파이썬 #백준 10989(수 정렬하기 3) import sys n = int(sys.stdin..

문제 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 해설 이 문제는 y좌표가 증가하는 순으로, y좌표가 같다면 x좌표가 증가하는 순으로 정렬하는 문제이다. 파이썬 내장 함수를 사용한다면, 정렬은 어렵지 않다. 나는 입력받은 좌표 값을 temp를 이용해 y, x로 뒤바꿔 정렬했다. 다른 분들은 람다를 이용해 한두줄로 끝내던데 난 아직 람다가 익숙하지 않아서 어렵다.. 람다를 이용하면 시간..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 해설 방법의 수를 계산해보면 1, 2, 4, 7, 13, 24가 나오는데 이걸 보면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]인 것을 알 수 있다. 처음엔 5까지만 방법의 수를 세보고 dp[i]의 방법의 수는 그 이전 수들의 방법의 수의 총합이라고 생각했는데 6까지 세어보니 완전 아니었다.. 완전 헛짓거리 하고 있었다. 코드 -파이썬 #백준 9095(1, 2, 3 더하기) t = int(input()) dp = [0] * 11 dp[1] = 1 dp[2] = 2 dp[..

문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 해설 이 문제는 dp문제로 규칙만 찾으면 쉽게 풀 수 있다. 처음엔 2*5까지 직접 정리해보고 dp[i] = dp[i-1] + dp[i-2] + (2*(i-2)-1) 인 줄 알았다. 그러나 백준 예제입력2만 해봐도 이게 아니란 걸 알 수 있다. 규칙 찾는데 약간 헤맸지만 자세히 보면 dp[i] = dp[i-1] + (dp[i-2]*2)규칙을 찾을 수 있다. dp[i-1]과 dp[i-2]를 알아내려면 최소한 dp[1], d..

문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 해설 이 문제는 dp 문제이다. 위 그림을 보면 n = (n-1) + (n-2) 임을 알 수 있다. 결국 dp[1]과 dp[2]의 개수만 미리 넣어놓는다면 그 후 dp[n]의 개수들은 쉽게 구할 수 있다. 다만, dp 배열을 초기화할 때 dp = [0] * (1001)이 아니라 dp = [0] * (n + 1)을 해주면 런타임 에러가 뜨는데 왜 뜨는지 모르겠다.. 코드 -파이썬 #백준 11726(2*n 타일링) ..

문제 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 해설 시간 제한이 0.5초인 만큼 input() 대신 sys.stdin.readline()을 써줘야 한다. push 처리는 입력을 받을 때 split()을 통해 공백으로 나눠서 받고 x[0], x[1]로 값을 처리해주면 된다. 코드 -파이썬 #백준 10845(큐) import sys n = int(sys.stdin.readline()) queue = [] for _ in ra..

문제 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 해설 이 문제는 단어를 리스트로 입력받고 set()으로 중복 제거 후 알파벳 순 정렬, 길이 순 정렬을 해주면 된다. 알파벳 순 정렬은 누구나 다 알듯이 sorted()를 쓰면 되고 길이 순 정렬은 sort() 함수에 key로 길이를 넣어주면 된다. 코드 -파이썬 #백준 1181(단어 정렬) n = int(input()) word = [] for _ in range(n): a = ..

문제 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 해설 list로 입력받아서 정렬해주기만 하면 끝난다. 그러나 실행 시간은 많이 걸린다. input()으로 입력받으면 시간 초과로 실패한다. 코드 -파이썬 #백준 11650(좌표 정렬하기) import sys n = int(sys.stdin.readline()) y = [] for i in range(n): x = list(map(int, ..

문제 www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 해설 이 문제는 가장 많이 팔린 책의 제목을 출력하는 문제인데, 베스트셀러가 여러권일 경우, 사전상 가장 먼저 오는 책을 출력해야 한다. 이런 경우엔 리스트를 오름차순으로 배열해놓기만 하면 쉽게 풀 수 있다. 베스트셀러를 구하는 것은 collections 모듈을 사용한다면 두 줄이면 가능하다. 코드 -파이썬 #백준 1302(베스트셀러) import collections n = int(input())..