본문 바로가기

알고리즘 (Python)/이것이 코딩 테스트다 with 파이썬

 (50)
[DFS/BFS 알고리즘] 꼭 필요한 자료구조 기초 자료구조 (Data Structure) - 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미 - 스택과 큐는 자료구조의 기초 개념으로 Push (삽입)과 Pop (삭제) 두 핵심적인 함수로 구성 스택 (Stack) - 스택은 박스 쌓기에 비유할 수 있음 (흔히 박스는 아래에서부터 위로 차곡차곡 쌓음) - 이러한 구조를 선입후출 (FILO) 또는 후입선출 (LIFO)라고 함 - 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없음 - 기본 리스트에서 append(), pop() 함수를 사용하면 스택 자료구조와 동일하게 동작 큐 (Queue) - 큐는 대기줄에 비유할 수 있음 (흔히 놀이공원에서 줄을 설 때 먼저 온 사람이 먼저 들어감) - 나중에 온 사람일수록 나중에 들..
[구현 알고리즘] 게임 개발 - 파이썬(python) 게임 개발 난이도 : 中 풀이 시간 : 40분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, m = map(int, input().split()) x, y, direction = map(int, input().split()) array = [] for i in range(n): array.append(list(map(int, input().split()))) darray = [[0] * m for _ in range(n)] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] darray[x][y] = 1 count = 1 turned_count = 0 while True: direction = direction - 1 if direction == -1: direction = ..
[구현 알고리즘] 왕실의 나이트 - 파이썬(python) 왕실의 나이트 난이도 : 下 풀이 시간 : 20분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 location = input() count = 0 x = ord(location[0]) - 96 y = int(location[1]) steps = [ (-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1) ] for step in steps: nx = x + step[0] ny = y + step[1] if 1
[구현 알고리즘] 아이디어를 코드로 바꾸는 구현 구현 알고리즘 - 코딩테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' - 흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미 - 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다로움 - 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미 - 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 의미 - 일반적으로 알고리즘 문제를 풀 때는 탐색해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용
[그리디 알고리즘] 1이 될 때까지 - 파이썬(python) 1이 될 때까지 난이도 : 下 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, k = map(int, input().split()) count = 0 while (n > 1): if (n % k == 0): n = n / k count = count + 1 else: n = n - 1 count = count + 1 print(count) 예시 # N, K을 공백을 기준으로 구분하여 입력 받기 n, k = map(int, input().split()) result = 0 // N이 K 이상이라면 K로 계속 나누기 while n >= k: # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기 while n % k != 0: n -= 1 result += 1 # K로 나누기 n //= k re..
[그리디 알고리즘] 숫자 카드 게임 - 파이썬(python) 숫자 카드 게임 난이도 : 下 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, m = map(int, input().split()) result = [] for i in range(n): array = list(map(int, input().split())) result.append(min(array)) print(max(result)) 예시 # N, M을 공백을 기준으로 구분하여 입력 받기 n, m = map(int, input().split()) result = 0 # 한 줄씩 입력 받아 확인하기 for i in range(n): data = list(map(int, input().split())) # 현재 줄에서 '가장 작은 수' 찾기 min_value = min(data) # '가장 작..
[그리디 알고리즘] 큰 수의 법칙 - 파이썬(python) 큰 수의 법칙 (11399번) 난이도 : 下 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, m, k = map(int, input().split()) array = list(map(int, input().split())) count = 0 array.sort(reverse=True) first = array[0] second = array[1] while True: if (m == 0): break else: for i in range(k): count = count + first if (m == 0): break m = m - 1 count = count + second m = m - 1 print(count) 예시 # N, M, K를 공백을 기준으로 구분하여 입력 받..
[그리디 알고리즘] 당장 좋은 것만 선택하는 그리디 그리디 알고리즘 (탐욕법) - 어떠한 문제가 있을 때 단순 무식하게, 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 문제를 푸는 알고리즘 - 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음 - 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 - 유형이 다양하기 때문에 암기가 아닌 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 함 - 보통 코딩 테스트에서는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 - 문제에서 '가장 큰 순서대로'와 같은 기준을 알게 모르게 제시 - 대체로 위 기준은 정렬 알고리즘을 사용하여 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이뤄 출제 - '가장 큰 화폐 단위부터'와 같이 탐욕적으로 문제에 접근했을 때 정..
[그리디 알고리즘] 모험가 길드 - 파이썬(python) 모험가 길드 난이도 : 下 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) gongpo = list(map(int, input().split())) gongpo.sort() group, count = 0, 0 for i in gongpo: count = count + 1 if i = i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성 result += 1 # 총 그룹의 수 증가시키기 count = 0 # 현재 그룹에 포함된 모험가의 수 초기화 print(result) # 총 그룹의 수 출력 해설 입력 n과 공포도 리스트 gongpo를 입력받습니다. 그리고 for 반복문으로 gongpo 리스트의 원소들을 하나하나 선택하고..
[다이나믹 프로그래밍 알고리즘] 효율적인 화폐 구성 - 파이썬(python) 효율적인 화폐 구성 난이도 : 中 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, m = map(int, input().split()) coins = [] for i in range(n): coins.append(int(input())) dp_table = [10001] * (m + 1) dp_table[0] = 0 for i in range(n): for j in range(coins[i], m+1): if dp_table[j - coins[i]] != 10001: dp_table[j] = min(dp_table[j], dp_table[j - coins[i]] + 1) if dp_table[m] == 10001: print(-1) else: print(dp_table[m..

티스토리툴바