이 글은 이것이 취업을 위한 코딩테스트다를 읽고 개인적으로 공부한 내용을 정리한 글입니다 :> with .. 내가 만든 그림 👻 정렬 알고리즘이란? 정렬 알고리즘 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 (ex 오름차순 정렬, 내림차순 정렬 : 이진 탐색의 전처리 과정 -> 정렬 알고리즘으로 데이터를 정렬해야 이진탐색이 가능 ! 정렬 알고리즘 종류 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 위 카드를 오름차순으로 정렬할 것이다 컴퓨터가 어떻게 정렬할 수 있을까 ?! 1️⃣ 선택 정렬 : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두번째 데이터와 바꾸는 과정을 반복하는 것 ! 🧩 선택 정렬 진행 과정 1) 첫번째 단계 전체 데이터 중 가장 작은 0..
🧩 문제 : 2251번 💪🏻 해결 방법 1️⃣ BFS 이용 1. 물의 총량은 c 이기 때문에, 물병 z에 담긴 물의 양은 c - 물병 x에 담긴 물 - 물병 y에 담긴 물 2. visited[x][y]로 경우의 수 중복 방지 3. 물의 양이 x = 0, y = 0 일 때 부터 경우의 수를 토대로 BFS를 한다. (1) 물병 x에 담긴 물이 0이라면 물병 z에 담긴 물의 양을 result에 담는다. (2) x -> y, x -> z, y -> x, y -> z, z -> x, z -> y 총 6가지를 모두 탐색한다. (3) 각각의 경우에 따라 옮길 수 있는 물의 양 파악 후, 물을 옮긴다. water = min(x, b - y) : x에서 y로 옮길 물. x 물통에서 y 물통으로 들어 갈 수 있는 물의 양..
🧩 문제 : 3020번 💪🏻 해결 방법 1️⃣ 석순과 종유석의 높이를 나누어 이분 탐색하자! 1. 석순과 종유석의 높이를 나누어 정렬 2. 개똥벌레가 나는 높이에 따라 파괴하는 장애물 개수 구하기 💥충돌 발생 조건 3. 최소 장애물 개수를 구하고, 그 구간의 개수 구하기 정답 코드 # 입력 N, H = map(int, input().split()) # 동굴 길이, 높이 down = [] # 석순의 높이 up = [] # 종유석의 높이 for i in range(N): if i % 2 == 0: down.append(int(input())) else: up.append(int(input())) count = 0 # 최소 충돌 구간 개수 min_crash = N # 최소 장애물 충돌 개수 # 정렬 down...
🧩 문제 : 1541번 💪🏻 해결 방법 1️⃣ 그리디 알고리즘 이용 1. 마이너스 기준으로 split 2. 플러스 기준으로 split 후 연산 3. 연산 완료된 수를 모두 마이너스 연산 정답 코드 # 입력 data = input().split('-') # input을 마이너스 기준으로 split num = [] for d in data: plus = d.split("+") # data의 원소를 플러스 기준으로 split sum = 0 # 더하기 연산을 계산할 변수 for i in plus: sum += int(i) num.append(sum) # 연산 완료 후 num에 저장 result = num[0] # 첫번째 수 for i in range(1, len(num)): result -= num[i] # 차..
🧩 문제 : 1931번 💪🏻 해결 방법 1️⃣ 그리디 알고리즘 이용 1. 시작 시간, 종료 시간을 기준으로 회의 시간 정렬 2. 회의 종료 시간과 같거나 큰 회의 시작 시간이 있다면 회의 종료 시간 갱신 + 회의 개수 증가 첫번째 코드 - 틀렸습니다 import sys # 입력 n = int(sys.stdin.readline()) # 회의의 수 N for _ in range(n): # 회의 시간 입력 start, end = map(int, input().split()) time.append([start, end]) time = [] # 회의 시간 count = 1 # 회의의 개수 time.sort(key=lambda x: (x[1], x[0])) # 시작시간, 종료시간을 기준으로 회의 시간 정렬 end_..
🧩 문제 : 5904번 💪🏻 해결 방법 1️⃣ 재귀로 풀기 1. 입력 받은 N으로 K구하기 2. Moo 수열 S(K) 만들기 3. S(K)의 N번째 글자 출력하기 전체 코드 - 메모리 초과 import sys # 입력 n = int(sys.stdin.readline()) # 출력할 n번째 자리수 result = [] # Moo 수열 S(k) size = 0 # Moo 수열의 크기 k = 0 # Moo 수열에 사용될 변수 # moo 수열 S(k)를 만드는 함수 def moo(x): if x < 0: return "" mid = "m" + ("o" * (x + 2)) result.append(moo(x - 1)) result.append(mid) result.append(moo(x - 1)) # moo 수열..
