![]()
정렬 알고리즘은 값들을 특정 조건에 따라 정렬하기 위해 사용되는 알고리즘이다. ex) 오름차순, 내림차순 대부분의 언어들에서는 원소들을 정렬하는 내장함수들이 존재하기 때문에 자연스럽게 그 함수들을 사용하지만, 당연히 이 과정은 자동으로 이루어지는 것이 아니라 내부적으로는 일련의 과정들을 거친다. 선택 정렬 알고리즘 선택 정렬 알고리즘은 수 많은 정렬 알고리즘 중 하나이다. 선택 정렬 알고리즘의 아이디어는 그림과 같이, 첫 번째 값부터 맨 마지막 값까지 쭉 돌면서 가장 작은 값들을 하나씩 배열의 맨 앞으로 가져오는 것이다. 파이썬을 통해 구현한 선택 정렬은 다음과 같다. arr = [5, 10, 9, 33, 21, 7, 2, 3, 0] # 정렬되지 않은 array for i in range(len(arr)..
문제 (링크) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 나의 풀이 from collections import deque n, m = map(int, input().split()) graph = [] # 상 하 좌 우 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] for _ in range(n): graph.append(list(map(int, input()))) def bfs(x, y): queue = deque() queue.append((x, ..
문제 (링크) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 나의 풀이 from collections import deque n, m, v = map(int, input().split()) matrix = [[0] * (n+1) for _ in range(n+1)] visited = [False] * (n+1) for _ in range(m): a, b = map(int, input().split()) m..
![]()
문제 (링크) https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 나의 풀이 from itertools import combinations n, m = map(int, input().split()) items = list(map(int, input().split())) comb = list(combinations(items, 3)) # combinations를 이용해 나열 가능한 조합 만들기 sum_value = [..
문제 (링크) https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 나의 풀이 n = int(input()) s = [] # 스택 for _ in range(n): x = int(input()) if x != 0: s.append(x) else: s.pop() print(sum(s)) 문제에 나오는대로 append와 pop만 사용하면 되는 문제
![]()
트리 자료구는 이전에 살펴봤던 링크드 리스트, 해시테이블과는 다르게 데이터들을 계층적으로 저장하여 관리한다. 이말은 즉, 삽입된 데이터 간에 높낮이 혹은 서열이 있다는 뜻으로 이해할 수 있겠다. 링크드 리스트의 노드를 정의할 때 데이터 값과 다음 노드에 대한 레퍼런스를 next 라는 이름으로 저장한 것과 반대로, 트리의 경우 노드에 데이터값과 자신의 윗 노드, 아랫 노드에 대한 레퍼런스를 저장하고 이를 각각 부모노드, 자식노드라 칭한다. root 노드 트리의 맨 시작점이 되는 노드이다. 링크드 리스트에서 head 노드를 따로 관리해줬던 것처럼 트리에서는 제일 윗 노드를 root라는 이름으로 따로 관리해준다. 형제노드(자매노드) Siblings 동일한 부모를 공유하는 다른 노드들을 말한다. 위 트리에선 F..
![]()
큐와 유사한 자료구조 중 스택 자료구조가 있다. 스택은 큐와 다르게 LIFO (Last-in First-out) 의 방식으로 데이터를 관리한다. 즉, 마지막에 들어온 데이터가 먼저 아웃된다. 이러한 방식의 데이터 관리는 여러 방식에서 다양하게 쓰일 수 있는데, 우리가 흔히 컴퓨터 작업에서 사용하는 실행취소 및 복원 잡업 등에서 사용할 수 있다. 스택을 통해 구현할 수 있는 작업은 다음과 같다. 1) 맨 뒤에 새로운 데이터 추가 - append 2) 맨 뒤의 데이터 삭제 후 삭제된 데이터 리턴 - pop 3) 맨 뒤의 데이터에 접근 - stack[-1] 스택 또한 collections의 deque를 이용할 수 있다. 그러나, 큐의 경우와는 다르게 맨 뒤의 값에 접근하는 연산은 동적배열과 링크드 리스트 모두..
![]()
큐는 데이터를 FIFO (First-in First-out) 방식으로 관리하는 자료구조이다. FIFO라는 말 그대로 처음 들어온 데이터를 먼저 나가는, 우리가 아는 마트 계산대나 은행 창구에서 고객을 처리하는 방식과 동일하게 작동한다. 실제로 대기줄 자체를 영어로 큐 (Queue)라고 부르기도 하며, 이 특성 덕분에 서로 다른 데이터 간의 순서를 유지할 수 있다. 큐에 구현되어 있는 대표적 기능은 다음과 같다. 1) 맨 뒤에 데이터를 추가 - append 2) 맨 앞 데이터에 접근 - deque[0] 2) 맨 앞 데이터를 삭제 후 삭제한 값을 리턴- popleft 파이썬에서는 collections에서 제공하는 deque를 이용해 큐를 이용할 수 있다. from collections import deque..
