Python

문제 링크 https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 문제 문제 풀이 딕셔너리를 이용해 풀이를 하였다. key값에 숫자를 저장하고, value에 해당 숫자의 개수를 저장한다. 딕셔너리 를 정렬할 때, 1) 개수가 큰 것 2) 개수가 같을 경우, 숫자가 작은 것 이 기준이 되므로, value값에 대해 먼저 내림차순 정렬을 해주고, key값에 대해 오름차순 정렬을 해준다. import sys input = sys.stdin.readlin..

문제 링크 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 문제 풀이 문제만 봐서는 너무 간단해서 단순하게 접근했다가 메모리 초과가 나왔다. 처음 제출했던 코드는 import sys input = sys.stdin.readline n = int(input()) array = [] for i in range(n): array.append(int(input())) array.sort() for i in range(len(array)): print(array[i]..

문제 링크 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 문제 풀이 lambda를 통해 정렬 조건을 정할 때 -를 붙이면 내림차순 정렬이 된다. n = int(input()) array = [] for i in range(n): name, korean, english, math = map(str, input().split()) korean = int(korean) english = int(english) math =..

문제 링크 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 문제 문제 풀이 배열 내 어떠한 기준을 정해 정렬을 하기 위해서 lambda를 사용한다. 2차원 배열 내 두번째 원소를 첫 번째 기준으로, 첫 번째 원소를 두 번째 기준으로 하였다. import sys input = sys.stdin.readline n = int(input()) array = [] for i in range(n)..

문제 링크 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 문제 문제 풀이 import sys input = sys.stdin.readline n = int(input()) array = [] for i in range(n): [x, y] = list(map(int, input().split())) array.append([x, y]) array.sort() for i in range(len..

문제 링크 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 문제 풀이 문제에서 주어진 예제만으로 점화식이 쉽게 구해진 문제였다. P[1], P[2], P[3]까지는 모두 1의 값을 가지고 n이 4부터 100까지의 값일 경우 P[n] = p[n - 3] + p[n - 2] 의 점화식을 가진다. 즉, 수열에서 2개 전, 3개 전 숫자끼리 더한 값이 현재 값이다. p = [0 for i in range(101)] p[1] = 1 p[2] = 1 p[..

문제 링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 문제 풀이 i가 현재 숫자, j가 i보다 작은 제곱수들일 때, dp[i - j] 중 가장 최소항의 개수가 작은 것을 찾아낸다. 이 값에 1을 더해주면 i의 최소항의 개수가 나타난다. (1을 더해주는 이유는 제곱수에 대한 항의 수를 추가하기 위해서이다.) 점화식 => dp[i] = min(dp[i - j]) + 1 n = int(input())..

문제 링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 문제 풀이 전형적인 DP 방식으로 풀리는 문제이다. 주의해야 할 점은 현재 계단(i), 바로 아래 계단을 오를 경우 두 계단을 연속으로 올랐기 때문에 i - 3까지의 최댓값에 두 계단의 값을 더해야 한다는 점이다! n = int(input()) array = [0] * 300 for i in range(n): array[i] = int(input()) dp = [0] * 300 dp[0] = ..