취업을 준비하며 정리하는 컴퓨터 지식 (55) 썸네일형 리스트형 [Algorithm] 너비 우선 탐색(BFS)은 뭐야? 너비 우선 탐색 BFS는 Breadth First Search의 약자이고, 너비를 우선으로 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식이었다면 BFS는 가까운 노드를 우선으로 탐색한다. 블루투스나 와이파이 같은 원리랑 비슷하다. 다음은 너비 우선 탐색의 과정을 그림으로 나타낸 것이다. 시작 노드인 '1'을 큐에 넣어주고, 방문 처리를 한다. 초록색은 처리 중인 노드, 파란색은 방문 처리된 노드를 표현한다. 큐에서 '1'을 꺼내 주고 방문하지 않은 인접 노드 '3'을 큐에 넣어주고 방문 처리를 한다. 큐에서 '3'을 꺼내주고 방문하지 않은 인접 노드 '4', '5'를 큐에 넣어주고 방문 처리를 한다. 큐에서 '4'를 꺼내준다. 이때 방문하지 않은 인접 노드가 존재하지 않.. [Algorithm] 깊이 우선 탐색(DFS)은 뭐야? 깊이 우선 탐색 DFS는 Depth-First Search의 약자이고, 깊이를 우선으로 탐색하는 알고리즘이다. 또한 DFS는 하나의 노드를 시작으로 다수의 노드를 방문하는 그래프 탐색의 한 유형이다. 이때 그래프는 노드와 간선으로 표현되고 노드는 하나의 원소, 간선은 원소와 원소를 연결하는 선이다. 다음은 깊이 우선 탐색의 과정을 그림으로 나타낸 것이다. 초록색은 최상단 노드, 파란색은 방문 처리된 노드를 표현한다. 위의 그림에서는 시작 노드인 '1'을 스택에 삽입하고 방문 처리하고 최상단 노드 처리를 한다. 최상단 노드 '1'의 인접 노드인 '3'을 스택에 넣고 방문 처리를 하고 최상단 노드 처리를 한다. 최상단 노드인 '3'의 인접 노드 '4'와 '5' 중에 가장 작은 노드 '4'를 스택에 넣고 방문.. [Algorithm] 입력 받는 방법? 코딩테스트를 준비하다보면 제일 처음으로 하는 것이 주여진 정보를 입력받는 것이다. 따라서 이번에는 파이썬을 이용하여 정보를 입력받는 방법에 대해서 다뤄보겠다. 다음은 공백을 기준으로 2개의 변수를 입력 받는 방법이다. 1 n, m = map(int, input().split()) [3 5] 이렇게 정보가 입력된다면 n=3, m=5 정보가 저장되게 된다. 다음은 리스트를 입력 받는 방법이다. 1 data = list(map(int, input().split())) 1 2 3 4 5 를 입력하게 된다면 data에는 [1,2,3,4,5]가 저장되게 된다. 다음은 크기가 n인 배열을 입력 받는 방법이다. 1 2 3 4 5 n = int(input()) array = [] for i in range(n): arr.. [Algorithm] 계수 정렬은 뭐야? 계수 정렬의 다른 정렬 알고리즘들과는 다르게 숫자들을 비교하여 정렬하는 알고리즘이 아니다. 그렇다면 어떻게 동작할까? 우선 배열의 최대 숫자보다 1 큰 배열을 생성한다. 그리고 정렬할 배열에 있는 원소를 생성한 배열의 위치 값으로 사용하고, 해당 위치의 값을 1 증가시켜준다. 정렬할 배열의 모든 원소를 확인했다면 생성한 배열의 위치 값과 배열의 값(해당 원소의 개수)을 출력하는 것으로 정렬을 마친다. 위와 같이 계수 정렬은 배열을 한 번씩만 확인해주기 때문에 시간 복잡도가 O(N+K)이다. 빠른 시간 복잡도에는 그만큼 전제가 많이 붙는다. 계수 정렬을 사용하기 위한 조건은 다음과 같다. 배열의 모든 원소들은 0을 포함한 양의 정수여야 한다. 최솟값과 최댓값의 차이가 100만을 넘지 않는 것이 좋다. 다음.. [Algorithm] 쿽 정렬은 뭐야? 퀵 정렬은 기준값(처음에는 제일 첫 번째 원소)을 기준으로 다른 원소들의 값을 비교하는 것만으로 수를 정렬하는 방법이다. 쿽 정렬은 배열의 왼쪽에서 피벗값 기준 큰 값을 찾고, 배열의 오른쪽에서 피벗값 기준 작은 값을 찾아서 2가지 값을 비교하여 큰 값의 위치가 작은 값의 위치보다 오른쪽에 위치해 있다면 작은 값과 피벗값의 위치를 바꿔주고, 반대의 경우에는 작은 값과 큰 값의 위치를 바꿔주는 연산을 정렬이 완료될 때까지 반복하는 정렬 방식이다. 앞서 말한 삽입 정렬과 선택 정렬은 O(N^2)의 시간 복잡도를 가지는 알고리즘으로 데이터의 개수가 10만만 넘어도 사용하기 힘들다는 단점이 있었다. 그렇기 때문에 더욱 빠른 알고리즘이 필요하고 퀵 정렬이 이에 속한다. 퀵 정렬은 평균 속도 O(N*logN)이다... [Algorithm] 삽입 정렬은 뭐야? 삽입 정렬은 "정보를 하나하나 확인하면서 각 정보들을 적절한 위치에 삽입하면 어떨까?"라는 생각에서 출발하는 알고리즘으로 앞서 말했던 선택 정렬과 다른 점은 필요할 때만 위치를 바꾼다는 것이다. 따라서 삽입 정렬은 거의 정렬되어있는 정보를 정렬할 때는 연산의 수가 적고, 빠르게 연산된다는 특징이 있다. 삽입 정렬은 정렬된 숫자들의 왼쪽과 오른쪽의 숫자들을 비교하여 연산 중인 숫자가 들어갈 적절한 위치에 숫자를 넣어준다. 다음은 1부터 5까지의 숫자를 무작위로 배치한 정보를 삽입 정렬을 이용하여 정렬하는 방식이다. 일단 무작위로 받은 숫자들이다. 파란색 배경은 정렬된 숫자, 진한 회색 배경은 선택 정렬 중인 숫자라고 한다. 선택 정렬에서 첫번째 인덱스는 정렬되었다는 가정을 하기 때문에 두 번째 인덱스인 5.. [Algorithm] 선택 정렬은 뭐야? 선택 정렬이란 정렬되지 않은 정보들 중에서 가장 작은 값을 정렬되지 않은 순서 중 가장 앞에 있는 정보와 바꾸는 정렬 방식을 말한다. 선택 정렬은 입력받은 모든 정보를 모두 확인한다는 점에서 가장 원시적인 방법으로 그만큼 연산의 수가 많은 알고리즘이다. 다음은 1부터 5까지의 숫자를 무작위로 배치한 정보를 선택 정렬을 이용하여 정렬하는 방식이다. 무작위로 배치된 숫자들을 나타낸 것이다. 여기서 1은 정렬되지 않은 숫자들 중에서 가장 작은 숫자이면서 가장 앞에 있으므로 정렬할 필요 없이 가만히 있는다. (밑에서부터 정렬된 숫자들은 배경을 파란색으로 바꾸도록 하겠다.) 1은 이미 정렬이 되었고, 다음 순서에서는 나머지 숫자 5,3,2,4 중에 가장 작은 숫자를 찾고, 그 값을 정렬되지 않은 가장 앞의 순서와.. 이전 1 ··· 4 5 6 7 다음
