본문 바로가기

전체 글

 (104)
선택 정렬 (Selection sort) 선택 정렬 (Selection Sort)대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법.선택 정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않는다. 원리만 간단히 알아보고 넘어가도록 한다.   선택 정렬은 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 핵심이다.  선택 정렬 과정1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.3. 가장 앞에 있는 데이터의 위치를 변경해 (index++) 남은 정렬 부분의 범위를 축소한다.4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 ..
버블 정렬 (Bubble sort) 버블 정렬 (Bubble Sort)두 인접한 데이터의 크기를 비교해 정렬하는 방법. 간단하게 구현할 수 있지만 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편이다. 다음 그림과 같이 루프(loop)를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다. 버블 정렬 과정1. 비교 연산이 필요한 루프 범위를 설정한다.2. 인접한 데이터 값을 비교한다.3. swap 조건에 부합하면 swap 연산을 수행한다.4. 루프 범위가 끝날 때까지 2~3을 반복한다.5. 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.6. 비교 대상이 없을 때까지 1~5를 반복한다. 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다..
스택과 큐 스택 : 깊이 우선 탐색 (DFS:Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적. 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통. 큐 : 너비 우선 탐색 (BFS:Breadth First Search)에서 자주 사용 [백준 1874번] 스택 수열https://www.acmicpc.net/problem/1874 스택 연산 수행 방법1. 현재 수열 값 >= 자연수현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push한다. 그리고 push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다.예를 들어 현재 수열 값이 4면 스택에는 1, 2, 3, 4를 push하고 마지막에 1회만 pop하여 4를 출력한 뒤 조건문을 빠져나온다..
슬라이딩 윈도우 슬라이딩 윈도우 알고리즘2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다.   [백준 12891번] DNA 비밀번호https://www.acmicpc.net/problem/12891 P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다. 이때 부분 문자열의 길이가 P 이므로 슬라이딩 윈도우 개념을 이용하면 문제를 쉽게 해결할 수 있다.    그림을 보면 마치 창틀에 창문을 놓고 이동하듯이 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 놓은 후 같은 길이 그대로 오른쪽으로 밀고 있다. 배열 S의 길이만큼만 탐색을 진행하면 되므로 O(n)의 시간 복잡도로 문제를 해결할 수 있다. 문제..
투 포인터 투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. [백준 2018번] 수들의 합 5https://www.acmicpc.net/problem/2018 이 문제는 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 문제에 주어진 시간 제한은 2초인데 N의 최댓값은 10,000,000으로 매우 크게 잡혀 있다. 여기서 O(nlongn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 방법이 투 포인터이다. 연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현하겠다. 시작 인덱스와 종료 인덱스를 투 포인터로 지정한다. start_index를 오른쪽으로 한 ..
구간 합 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의한다.합 배열 S의 정의S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]       // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열로, 이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다. 합 배열은 다음과 같은 간단한 공식으로 만들 수 있다.합 배열 S를 만드는 공식S[i] = S[i-1] + A[i] 이렇게 구현된 합 배열을 이용하여 구간 합 역시 쉽게 구할 수 있다..
배열과 리스트 배열의 특징인덱스를 사용하여 값에 바로 접근할 수 있다.새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.구조가 간단하므로 코딩 테스트에서 많이 사용한다. 리스트의 특징인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 다시 말해 값에 접근하는 속도가 느리다.포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.선언할 때 크기를 별도로 지정하지 않아도 된다. 다시 말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.포인터를 저장할 ..
트리 시각적으로 볼 때, 리스트, 스택, 큐 등의 추상 자료형이 데이터를 한 줄로 나열한 선형구조(Linear Structure)라면, 추상 자료형 트리는 데이터를 여러 줄로 나열했다는 점에서 비선형 구조(Non-Linear Structure)다. 이러한 비선형 구조를 사용하는 가장 큰 이유는 탐색 시간을 단축하는 데 있다. 트리 (Tree) 계층적인 관계(Hierarchical Relationship)를 나타내는 데 편리한 것. ex) 족보, 기업의 조직도, 컴퓨터 디렉터리 ... 결정 트리(Decision Tree) : 어떤 결정 과정을 나타낸 트리 용어 정리 - 노드(Node) : 트리의 구성 요소(Element)에 해당하는 A, B, C, ... L - 자식 노드(Child Node) : B의 바로 아..

티스토리툴바