Coding Test
-
[백준 7568번] 덩치Coding Test/백준 2021. 3. 19. 03:16
# 문제 내 풀이 n = int(input()) # 사람들의 덩치 정보 입력 받기 people = [tuple(map(int, input().split())) for _ in range(n)] # 현재 사람의 덩치를 다른 모든 사람들과 비교하여 for i in range(n): rank = 1 # 만일 현재 사람보다 덩치가 큰 사람이 있다면, rank를 1 증가시킴 for j in range(n): if people[i][0] < people[j][0] and people[i][1] < people[j][1]: rank += 1 # 현재 사람의 등수 출력 print(rank, end=' ') 생각해볼 점 처음엔 입력 수가 많지 않아 조건에 맞춰 bubble sort를 한 후, 정렬된 정보대로 차례차례 비..
-
[백준 1806번] 부분합Coding Test/백준 2021. 3. 16. 23:20
# 문제 내 풀이 n, s = map(int, input().split()) data = list(map(int, input().split())) min_len = int(1e5) # 구하고자 하는 부분 수열 중 가장 짧은 것의 길이 interval_sum = 0 # 현재 부분 수열의 부분합 end = 0 # 투 포인터 알고리즘 수행 # start를 차례대로 증가시키며 반복 for start in range(n): # end를 가능한 만큼 이동시키기 while interval_sum = s and end - star..
-
[백준 2470번] 두 용액Coding Test/백준 2021. 3. 13. 01:49
# 문제 내 풀이 n = int(input()) data = list(map(int, input().split())) min_val = 2 * int(10e9) # 혼합 용액의 최소 특성값 left = 0 right = n - 1 data.sort() # 오름차순 정렬 # 양 끝의 포인터가 엇갈리기 전까지 while left < right: # 현재 가리키는 두 용액의 특성값 합이 최소 특성값이라면 최솟값 갱신 if abs(data[left] + data[right]) < min_val: min_val = abs(data[left] + data[right]) min_pair = (data[left], data[right]) # right가 가리키는 특성값의 절대값이 더 크다면 right를 1 감소시킴 i..
-
[백준 3273] 두 수의 합Coding Test/백준 2021. 3. 10. 20:53
# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 n = int(input()) nums = list(map(int, input().split())) x = int(input()) cnt = 0 # (ai, aj) 쌍의 갯수 left = 0 # 왼쪽 인덱스 right = n - 1 # 오른쪽 인덱스 nums.sort() # 오름차순으로 정렬 수행 # 두 포인터가 교차할 때까지 while left x: right -= 1 continue l..
-
[백준 4948번] 베르트랑 공준Coding Test/백준 2021. 3. 6. 22:09
# 문제 내 풀이 - 시간 초과, 수정 답안 n = 123456 * 2 # 2부터 (2 * 123456)까지의 모든 수에 대하여 소수 판별 # 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외) array = [True for _ in range(2 * n + 1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 2n의 제곱근까지의 모든 수에 대하여 for i in range(2, int((2 * n) ** 0.5) + 1): if array[i] == True: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j 1 and array[i]: cnt += 1 # 개수 출력 print(cnt) 생각해볼 점 에라토스테네스의 체의 시간복잡도가 매우 빠르긴 하지만, 테스트..
-
[백준 1929번] 소수 구하기Coding Test/백준 2021. 3. 4. 23:43
# 문제 내 풀이 m, n = map(int, input().split()) # 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외) array = [True for i in range(n + 1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 n의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(n ** 0.5) + 1): if array[i] == True: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j 1 and array[i]: print(i) 생각해볼 점 마지막 출력에서 1을 거르는 조건을 생각하지 못해 오래 걸렸다. 예외 케이스를 항상 염두하자.
-
[백준 1018번] 체스판 다시 칠하기Coding Test/백준 2021. 2. 28. 19:29
# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 # 첫 칸을 검은색, 흰색 각각으로 칠할 때, 둘 중 다시 칠해야 하는 횟수가 최소인 값을 리턴하는 함수 정의 def paint_board(chess_board): # 첫 칸이 검은색일 경우와 흰색일 경우, 각각 다시 칠하는 횟수 start_b, start_w = 0, 0 for i in range(8): for j in range(8): if (i + j) % 2 == 0: if chess_board[i][j] != 'B': start_b += 1 if chess_board[i][j] != 'W': start_w += 1 else: if chess_board[i][j] != 'W': start_b += 1 if chess_board[i][j] != 'B..
-
[백준 2887번] 행성 터널Coding Test/백준 2021. 2. 26. 20:06
# 문제 내 풀이 - 수정 답안 import sys input = sys.stdin.readline # 특정 원소가 속한 집합을 찾기 (Find 연산) def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 (Union 연산) def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b n= int(input()) loc = [] # 좌표를 입력 받을 리스트 edges..