backjoon
-
10989 - 수 정렬하기Programming/BackJoon 2023. 4. 21. 14:37
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 천만개를 정렬하려면 어떤 수를 써야할까 dict에 갯수를 표시하고 그 값만 출력하면 어떨까? -> 아마 이 방법이 계수정렬하고 비슷할듯하다. import sys t_case = int(sys.stdin.readline()) counting_lst = [0] * (10000+1) for i in range(0, t_case): v1 = int(sys.stdin.readline()) counting_lst[v1] += ..
-
11650 - 좌표 정렬하기Programming/BackJoon 2023. 4. 21. 14:06
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 튜플로 받고, 정렬하면 쉽게 푸는 문제 t_case = int(input()) lst = [] for i in range(t_case): x, y = input().split(' ') lst.append((int(x), int(y))) lst.sort(key=lambda x: (x[0], x[1])) for item in lst: print(i..
-
10814 -나이순 정렬Programming/BackJoon 2023. 4. 21. 14:03
https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 받은 입력을 나이순, 이름순으로 정렬한다. 문제 조건에 가입일순도 있긴해서 가입일을 정렬하려고했는데, 풀어보니 가입일 없이도 풀린다. 튜플이용해서 풀고, 리스트안에 튜플을 정렬할때 lambda를 사용할 줄 알면 금방 풀겠다 t_case = int(input()) lst = [] for i in range(t_case): age, name = input().split(' ') lst.append((int..
-
1427 - 소트인사이트Programming/BackJoon 2023. 4. 21. 13:46
https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net int 한개를 받아서 그 안의 수를 내림차순으로 정렬하면 끝나는 문제 숫자를 list로 변환하고, sort하고, print문에서 end='' 옵션을 줘서 풀었다. import sys lst = list(map(int, sys.stdin.readline().rstrip())) lst.sort(reverse=True) for i in lst: print(i, end='') 다른 사람들의 풀이도 보면 간단히 푼다. array = input() for i in range(9, -1, -1)..
-
1699 - 제곱수의 합Programming/BackJoon 2023. 3. 17. 10:35
1) 문제 링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 2) 문제 설명 어떤 자연수를 제곱수로 나타낼 수 있다 ex ) 11 = 3^2 + 1^2 + 1^2 -> 3개로 가능 3) 문제 풀이 처음에는 받은 수 n 의 sqrt를 구해서 해볼 생각이었다. (수학 + 구현 문제인줄..) 예를 들어서 11이면 int(math.sqrt(11)) = 3 11 - 3^2 = 2 int(math.sqrt(2))..
-
2579 - 계단 오르기Programming/BackJoon 2023. 3. 16. 13:58
1) 문제 설명 계단을 오르는 데 조건이 있다 계단은 한번에 한 계단 혹은 두 계단씩 오를 수 있다. 한 계단을 밝으면 그 다음 혹은 그 다음 다음 계단을 밟을 수 있다 연속된 세개 계단은 밟을 수 없다 마지막 계단은 반드시 밟아야 한다 2) 문제 이해 조건에 왜 마지막 계단을 밟아야 되는지를 주었는지 모르겠다 일단 dp 문제라고 이해하고, 규칙을 찾아본다 첫번째 계단은 밟거나 밟지 않을 수 있다. (2 계단을 건너뛸 수도 있으므로..) 두번째 계단은 첫번째 계단을 밟고, 또 밟을 수 있다. 그리고 두번째 계단만 밟을 수도 있다. 세번째 계단은 첫번째 계단을 밟고, 2칸을 건너뛴 다음에 세번째를 밟을 수 있고 2번째 계단을 밟고, 3번째 계단을 밟는 경우가 있다. 네번째부터는 점화식을 세울 수 있다 경우..
-
1912 - 연속합Programming/BackJoon 2023. 3. 15. 14:48
1) 문제 설명 주어진 수들 가운데, 연속적으로 더했을때 가장 큰 수를 찾는 문제 전형적인 dp 문제 특정 위치에서 연속합은 내 앞에껄 가져와서 더하거나 혹은 나만 더하거나 이다. dp[0]은 list[0]과 같고 dp[1] = max(dp[0] + list[1] , list[1]) dp[2] = max(dp[1] + list[2] , list[2]) 점화식을 세워보면 dp[n] = max(dp[n-1] + list[n] , list[n]) 이다 2) 문제 풀이 import sys n = int(input()) lst = list(map(int, sys.stdin.readline().split())) dp = [0] * (n) dp[0] = lst[0] max_value = dp[0] for i in r..
-
1966 - 프린터 큐Programming/BackJoon 2023. 3. 15. 08:43
1) 문제 설명 프린터 작업을 하는데, 우선순위를 두고 해야한다. 주어진 프린터 작업 리스트 중에서 우선순위가 가장 높은것부터 출력하고, 내 뒤에 나보다 우선순위가 높은게 있으면 출력하지 않는다. 2) 문제 분석 Queue를 사용해서 푸는 문제 우선순위까지는 알겠는데, index를 어떻게 같이 저장할 것인지 고민 필요 -> 튜플형태로 (value, idx)로 저장 enumerate를 사용해서 idx와 우선순위를 쉽게 저장할 수 있다. lst = [1,2,3,4] for idx, value in enumerate(lst): print(idx, value) 우선순위를 튜플에 먼저 저장한 이유는 max값을 찾을때 쉽게 하려고 그랬다 import sys t = int(input()) while t > 0: n,..