algorithm

일반적으로 알고리즘을 공부 할 때 가장 쉽게 먼저 접하는 문제는 ‘정렬(Sort)’문제라고 할 수 있다. 본 포스팅에서는 정렬 알고리즘 중에서도 선택정렬 을 구현하고 시간 복잡도를 알아 보도록 하겠다.문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라1

앞선 포스팅에서는 선택정렬 , 버블정렬 에 대해 알아보았고, 이번 포스팅에서는 삽입정렬을 구현하고 시간 복잡도를 알아 보도록 하겠다.문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라1 10 5 8 7 6 4 3 2 9 문제를 해결하기 위해 “각 숫

저번 포스팅에서는 선택정렬 알고리즘에 대해 알아 보았고, 이번 포스팅에서는 버블정렬 을 구현하고 시간 복잡도를 알아 보도록 하겠다.문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라1 10 5 8 7 6 4 3 2 9 문제를 해결하기 위해 “옆에 있

이번 포스팅에선 힙 정렬 (Heap Sort)에 대해 알아볼 것이다. 힙 정렬은 이전 포스트에서 다뤘던 퀵 , 병합 정렬 과 마찬가지로 시간복잡도가 O(N \*log N) 인 빠른 정렬 알고리즘이다. 힙 정렬을 이해하기 위해선 이진트리, 힙을 이해해야 하기에 이번 포스

앞선 포스팅에서는 선택정렬 , 버블정렬 , 삽입정렬에 대해 알아보았다. 3개의, 정렬 알고리즘의 시간 복잡도는 주어진 데이터에 따라 달라지지만 보통 O(N^2) 의 형태를 띄고 있다. 하지만 이번 포스팅에서 설명할 퀵 정렬 의 시간복잡도는 O(N^2)가 아닌 O(N

이번 포스팅에선 계수정렬 (Counting Sort)에 대해 알아볼 것이다. 계수 정렬은 지난 정렬 알고리즘과 다르게 특정 조건에서 매우 빠르게 작동하는 정렬 알고리즘이다. 앞선 정렬 알고리즘의 시간 복잡도는 대개 O(N^2), O(N \* log N) 의 형태를 띄었

앞선 포스팅에서는 앞도적으로 빠른 속도를 자랑하는 퀵 정렬에 대해 알아보았다. 하지만 이런 퀵 정렬 또한 최악의 상황 (거의 정렬이 되어있는 데이터)에서의 시간복잡도가 O(N \* log N)을 보장하지 못한다는 단점을 가지고 있었다. 이런 단점을 보완하여 어떠한 경우

이번 포스팅에선 알고리즘의 탐욕법(greedy), 완전탐색(brute force)에 대해 알아보도록 하겠다. 문제 풀이를 위한 아이디어를 추출하고, 정당한지 확인하자.문제 풀이를 위한 아이디어를 추출한다.추출된 아이디어가 문제 상황에 적합한지 판단 후 적용한다. 558

DFS, 깊이우선탐색깊이 우선탐색은 그래프를 탐색할 때 쓰이는 알고리즘으로, 특정한 노드에서 가장 멀리 있는 노드를 우선적으로 탐색하는 알고리즘이다.주어진 맵 전체를 탐색하며, 한번 방문한 노드는 재 방문하지 않기에 인접한 리스트로 이루어진 맵이면O(V + E)인접 행

BFS 너비우선탐색BFS는 그래프를 탐색하는 알고리즘으로 노드에서 시작해 이웃한 노드들을 우선적으로 탐색하는 알고리즘 이다.같은 가중치를 가진 그래프에서 최단거리를 구할 때 사용되는 알고리즘이다. 시간 복잡도는 앞의 포스팅에서 소개한 DFS와 같으며 주어진 맵 전체를

트리순회 트리 순회는 2진트리에서 트리를 순회하는 것을 말한다. 총 4가지의 순회 알고리즘이 있고, 각각의 알고리즘을 알아보고자 한다.후위순회(postorder traversal)전위순회(preorder traversal)중위순회(inorder traversal)레벨순

12명이 서로(2명씩) 인사하면 66가지의 경우에 수가 나오게 된다. 이 경우의 수는 순열과 조합으로 구할 수 있는데 이번 포스팅에선 이 순열과 조합에 대해 알아 보고, 코드로 구현까지 해보도록 하겠다. 먼저 순열, permutation이란 순서가 정해진 임의의 집합을

이번 포스팅에선 기본적인 비트 연산을 알아보고 직접 구현해 보고, 이를 이용한 조합Combination을 함께 알아보도록 하겠다.먼저 비트연산에 대하여 알아 보도록 하겠다. 우선 왼쪽 시프트 연산자 << 는 수를 왼쪽으로 이동한다는 의미다.비트마스킹에서 보