본문 바로가기

알고리즘 (Python)

 (261)
[이진 탐색 알고리즘] 범위를 반씩 좁혀가는 탐색 순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위하여 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음 - 이름처럼 순차로 데이터를 탐색한다는 의미 - 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단 - 리스트에 특정 값의 원소가 있는지 체크할 때 사용 - 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간 복잡도는 O(N) 이진 탐색 - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 - 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데..
[정렬 알고리즘] 두 배열의 원소 교체 - 파이썬(python) 두 배열의 원소 교체 난이도 : 下 풀이 시간 : 20분 시간 제한 : 2초 메모리 제한 : 128 MB 해답 n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) a.sort() b.sort(reverse=True) for i in range(k): if a[i] > b[i]: a[i], b[i] = b[i], a[i] else: break print(sum(a)) 예시 n, k = map(int, input().split()) # N과 K를 입력 받기 a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기 b = list(m..
[정렬 알고리즘] 성적이 낮은 순서로 학생 출력하기 - 파이썬(python) 성적이 낮은 순서로 학생 출력하기 난이도 : 下 풀이 시간 : 20분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) array = [] for i in range(n): input_data = input().split() array.append((input_data[0], int(input_data[1]))) array = sorted(array, key = lambda x:x[1]) for x in array: print(x[0], end = ' ') 예시 # N 입력 받기 n = int(input()) # N명의 학생 정보를 입력 받아 리스트에 저장 array = [] for i in range(n): input_data = input().split() # 이름은..
[정렬 알고리즘] 위에서 아래로 - 파이썬(python) 위에서 아래로 난이도 : 下 풀이 시간 : 15분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) array = [] for i in range(n): array.append(int(input())) array.sort(reverse=True) for i in range(n): print(array[i], end=' ') 예시 # N 입력 받기 n = int(input()) # N개의 정수를 입력 받아 리스트에 저장 array = [] for i in range(n): array.append(int(input())) # 파이썬 정렬 라이브러리를 이용하여 내림차순 정렬 수행 array = sorted(array, reverse=True) # 정렬이 수행된 결과를 출력 f..
[정렬 알고리즘] 기준에 따라 데이터를 정렬 정렬 알고리즘 - 정렬 (Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 - 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐 - 내림차순 정렬은 오름차순 정렬을 수행하는 알고리즘에서 크기 비교를 반대로 수행하면 됨 정렬 라이브러리 - 현대의 정렬 알고리즘은 정립되어 있기 때문에 앞으로 큰 개선이 이루어질 것이라고 예상하기는 어려움 - 정렬 알고리즘 문제는 어느 정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제 - 정렬 알고리즘을 직접 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 많음 정렬 라이브러리의 시간 복잡도 - 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장 - 정렬 라이브러리는 이미 잘 작성된 함수이므로 ..
[DFS/BFS 알고리즘] 미로 탈출 - 파이썬(python) 미로 탈출 난이도 : 中下 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 from collections import deque n, m = map(int, input().split()) maze = [] for i in range(n): maze.append(list(map(int, input()))) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): queue = deque() queue.append((x, y)) while queue: x, y = queue.popleft() for i in range(4): nx, ny = x + dx[i], y + dy[i] if nx = n or ny ..
[DFS/BFS 알고리즘] 음료수 얼려 먹기 - 파이썬(python) 음료수 얼려 먹기 난이도 : 中下 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, m = map(int, input().split()) ice = [] for i in range(n): ice.append(list(map(int, input()))) def dfs(x, y): if x >= n or y >= m or x
[DFS/BFS 알고리즘] 탐색 알고리즘 DFS/BFS 탐색 (Search) - 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미 - 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸 그래프 (Graph) - 그래프는 노드와 간선으로 표현됨 - 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말함 - 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현 - 그래프는 크게 2가지 방식으로 표현할 수 있음 인접 행렬 (Adjacency Matrix) - 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 - 파이썬에서는 2차원 리스트로 인접 행렬을 구현할 수 있음 - 연결이 되어 있지 않은 노드끼리는 무한의 비용(INF)라고 작성 - 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요..
[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 = ..

티스토리툴바