선호:하다

비트마스크(BitMask) 비트마스크(BitMask)는 정수의 이진수 표현을 자료구조 처럼 사용하는 기법이다. 0과 1을 이용하여 비트를 표현하며 해당 비트가 0인 경우 "꺼져있다", 1인 경우 "켜져있다" 라고 말한다. 비트마스크의 장점 수행 시간이 빠르다 - 비트 연산이므로 O(1)에 구현되는 연산들이 많다 메모리 효율성 - 하나의 정수는 32비트기 때문에 2^32 가지의 표현이 가능하다. 코드의 간결성 비트마스크를 이용한 집합 구현 집합 구현은 비트마스크의 가장 대표적이고 중요한 사례이다. 하나의 비트는 원소 하나를 의미하게 되며 비트가 켜진 경우 포함, 꺼진 경우 미포함을 의미한다. 즉, N비트 정수 변수는 N개의 원소를 가지는 집합의 부분집합들을 모두 표현할 수 있다. 이는 N개의 bool형 원..

최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 문제의 상황은 다음과 같이 다양하다. 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 또한 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 더 많이 출제된다. 따라서 포스팅에서도 최단 경로가 아닌 최단 거리를 출력하는 코드를 구현할 것이다. 컴퓨터공학과 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드..

최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 문제의 상황은 다음과 같이 다양하다. 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 또한 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 더 많이 출제된다. 따라서 포스팅에서도 최단 경로가 아닌 최단 거리를 출력하는 코드를 구현할 것이다. 컴퓨터공학과 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드..

다이나믹 프로그래밍(Dynamic Programming) 동적 계획법이라고도 불리는 다이나믹 프로그래밍은 메모리를 약간 더 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 다이나믹 프로그래밍에서는 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 최적 부분 구조(Optimal Substructure)- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 문제 중복되는 부분 문제(Overlapping Subproblem)- 동일한 작은 문제를 반복적으로 해결해..

순차 탐색(Sequential Search) 이진 탐색을 알아보기 전에, 가장 기본적인 탐색 방법으로 데이터를 차례대로 하나씩 확인하며 탐색하는 순차 탐색이 있다. 순차 탐색은 구현이 매우 쉽고 리스트에서 특정한 값의 원소의 개수를 세는 count() 메서드도 내부적으로 순차 탐색을 이용한다. 순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인하는 것이 특징이다. 따라서 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 시간 복잡도는 O(N)이다. 이진 탐색(Binary Search) 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위 일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 ..

복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도(Time Complexity)는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미 공간 복잡도(Space Complexity)는 특정한 크기의 입력해 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 같은 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립하여 메모리를 더 많이 사용하는 대신 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 ..

정렬이란, 섞여 있는 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 정렬 알고리즘은 일반적으로 O(N^2)과 O(NlogN) 사이의 시간 복잡도를 가지며 특수한 경우 O(N)인 경우도 있다. 다양한 정렬 알고리즘에 대해서 정리해보자. (모든 예시는 오름차순 정렬을 기준으로 한다) 평균적으로 O(N^2)의 시간 복잡도를 갖는 정렬 알고리즘 1. 선택 정렬(Selection Sort) - 현재 정렬되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 가장 왼쪽의 데이터와 바꾼다. - 맨 왼쪽 데이터를 제외한 데이터에 대해서 선택 정렬을 반복한다. (하나의 원소만 남을 때까지) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): m..

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있다. 깊이 우선 탐색(DFS, Depth - First Search) DFS는 Depth - First Search, 깊이 우선 탐색이라고도 부르며, 그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그림에서와 같이 갈 수 있는 한 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길로 돌아와 선택하지 않았던 노드를 방문하는 식으로 탐색한다. DFS는 스택(Stack) 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 ..