개미의 개열시미 프로그래밍

백준 단계별 풀기 이분 탐색 파트의 첫 번째 문제입니다. https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net [풀이 코드] from bisect import bisect_left, bisect_right from sys import stdin n = int(input()) n_list = list(map(int, stdin.readline().split())) n_list.sort() m = int(..

오늘은 이코테 강의를 보면서 정리한 이진 탐색 개념을 정리해보려 한다. https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 - 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 logN에 비례하다. 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남습니다. --> 2단계를 거치면 8개 가량의 데이..

좌표 정렬하기 2라고 해서 좀 더 어렵거나 제약조건이 추가된 건 줄 알았는데 그냥 y기준을 우선으로 정렬해주면 끝났던 문제였다ㅋㅋ 어쩐지 정답률이 60%가 넘더니.. 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 [풀이 코드] from sys import stdin n = int(input()) a = [] for _ in range(n): x, y = map(int, stdin.rea..

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 [풀이 코드] from sys import stdin n = int(input()) a = [] for _ in range(n): x, y = map(int, stdin.readline().split()) a.append((x,y)) a.sort(key=lambda x: (x[0], x[1])) for i in a: print(i[0], i[1..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net [나의 풀이 코드] from sys import stdin n = int(input()) a = [] b = [] for _ in range(n): a.append(stdin.readline().split()[0]) a = sorted(set(a)) # 중복제거 for i in a: # 길이를 추가해서 b에 붙이기 b.append([i, len(i)]) # 알파벳순으로 정렬 후 길이순으..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net [풀이 코드] from sys import stdin n = int(input()) a = [] for i in range(n): a.append(list(stdin.readline().split())) a.sort(key=lambda i : int(i[0])) # 나이를 기준으로 정렬 for x in a: print(x[0], x[1]) [코드 풀이] 처음에 딕셔너리를 활용해서 풀어야 하나 고민 많이..

오늘은 백준 단계별 풀기이고 뒤에서부터 풀어보려고 한다. https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net [풀이 코드] - 첫번째 풀이 from sys import stdin n = int(input()) a = list(map(int, stdin.readline().split())) b = sorted(set(a)) # set으로 중복을 제거 # print(a) # print(b) for i ..

단계별 풀기 '그리디 파트'의 마지막 문제를 풀어보았습니다. 이번 문제는 특이하게 서브 태스크가 있었는데 제약조건에 따라 부분점수를 주는 것 같습니다. 만점을 받지는 못했지만 예제 입력에 따른 답은 잘 나오는 편이었습니다. [나의 풀이] from sys import stdin n = int(input()) km_list = stdin.readline().split() # 거리입력 price_list = stdin.readline().split() # 주요소 가격 result = 0 for i in range(len(km_list)): a = [] for j in range(i+1): k_p = int(km_list[i]) * int(price_list[j]) a.append(int(k_p)) result..