유제필의 개발 블로그

요약 해시란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값을 말함 해시 테이블이란, 키와 밸류를 한 쌍으로, 해싱 함수에 따라 효율이 달라짐 충돌이란 데이터를 넣어야 할 주소에 이미 다른 값이 저장되어 있는 현상을 말하며 충돌 시 체이닝 기법을 적용함 체이닝이란 해시 함수가 충돌이 발생하면, 각 데이터를 해당 주소에 있는 링크드 리스트로 삽입하여 문제를 해결하는 기법을 말함 체이닝의 성능 개선으로 선형 탐사, 제곱 탐사, 이중 해싱 등이 있음 제일 좋은 성능은 이중 해싱으로, 해싱 함수를 두 가지를 두고, 충돌 시 두 번째 해싱 함수를 사용 해시(Hash) 해시란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(Mapping)한 값이다. 즉, 해시는 데이터를 입력받아 ..

먼저 아래와 같은 큐 구조가 있다. 유선순위 큐의 각 요소는 우선순위를 가지고, 이들 요소의 우선순위 오름차순으로 연결된다. 이 예제에서는 낮은 값의 데이터들이 높은 우선순위를 가진다. 위 큐에서 20의 값을 넣는 과정을 살펴보면, 먼저 첫 요소부터 순서차적으로 우선순위를 비교한다. 20은 2와 17보다 크고 22보다 작으므로 17과 22사이에 삽입되어야 한다. 우선순위 큐의 제거 우선순위 큐의 제거 연산은 가장 앞 요소인 전단만 제거하면 되므로, 간단하다. 힙을 이용한 우선순위 큐 구현 방법 우선순위 큐를 구현하기 위해 힙을 이용한다. 여기서 힙(Heap)은 자유 저장소의 힙이 아닌, 힙 순서 속성(Heap Order Priority)을 만족하는 완전 이진트리를 말한다. 완전 이진 트리란 최고 깊이(잎..

2164번: 카드 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 (추가 시간 없음) 128 MB 65842 33911 27706 51.633% 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4..

요약 수식 계산을 위한 트리 구조로 후위 변환 표기식으로 트리를 구축하고, 중위 표기식으로 변환하여 사용 1개의 연산자와 2개의 피연산자를 요구함 피 연산자는 잎 노드임 연산자는 뿌리 또는 가지 노드임 뒤에서부터 역순으로 계산이 되어야 함 뒤에서부터 1개씩 토큰을 확인해 연산자인지 피연산자인지 확인 수식 트리(Experssion Tree) 수식 트리란 이름 그대로 수식을 표현하는 트리이며, 수식 이진 트리라고도 한다. 하나의 연산자가 2개의 피연산자를 취한다는 가정 아래, 수식 트리는 일반적으로 2가지의 규칙을 가진다. 피연산자는 잎 노드이다. 연산자는 뿌리 노드 또는 가지 노드이다. 예를 들어 아래와 같은 수식이 있다. (1 * 2) + (7 - 8) 피연산자 1, 2, 7, 8은 모두 잎 노드이고, ..

이진 탐색 트리 요약 시간 복잡도 : O(log(n)) ~ O(n) 왼쪽 하위 트리는 루트보다 작은 값이 위치함 오른쪽 하위 트리는 루트보다 큰 값이 위치함 정렬되어 있는 트리 구조에서 빠른 탐색 속도를 보임 한쪽으로 편향되어 있는 트리 구조에서 비효율적임 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리란 트리 내부에 있는 노드의 값을 찾는 방법으로 아래와 같이 3가지의 조건을 만족하면 된다. 각 노드는 왼쪽 자식 노드보다 큼 각 노드는 오른쪽 자식보다 작음 같은 키 값을 갖는 노드는 없음 위 그림은 이진 탐색 트리를 구현한 예이다. 여기서 노드 5를 보면 왼쪽 하위 트리 노드(4, 1)은 모두 5보다 작다. (조건 1번에 해당) 그리고 오른쪽 하위 트리 노드(7, 6, 9)는 모두 ..

요약 시간 복잡도 평균 : O(n / m) / 최악 : O(n) 검색하고자 하는 패턴의 마지막 문자부터 앞쪽으로 검사를 진행 일치하지 않는 문자가 있을 경우 Skip 표에 따라 패턴을 옮겨 가면서 검사 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표를 만들어야 함 문자열의 커서는 앞에서 뒤로, 패턴의 커서는 뒤에서 앞으로 역방향으로 검사 Boyer-Moore 알고리즘이란 Boyer-Moore 알고리즘이란 검색하고자 하는 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정하는 고리즘이다. Booyer-Moore 법은 Brute-Froce나 KMP 보다 효율이 더 우수하기 때문에 널리 사용되는 문자열 검색 알고리즘이다. R.S ..

요약 시간 복잡도 : 최상 O(mn) 문자열에서 특정 패턴을 미리 찾아내 검색하는 문자열 검색 알고리즘 문자열 검색 시 검사했던 위치 결과를 버러지 않아 효율적으로 검색할 수 있음 문자열 검색 시 불필요한 문자간 비교를 없애기 위해 실패 함수를 사용함 Boyer-Moore 법과 성능이 같거나 좋지 않아 실제로 많이 사용되지 않는 알고리즘 KMP(Knuth-Morris-Pratt Algorithm) 알고리즘이란 KMP 알고리즘이란 문자열 중에서 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 하나이다. 문자열 검색 시 검사했던 위치 결과를 버리지 않고 효율적으로 검색할 수 있는 특징이 있다. 문자열 검색 시 불필요한 문자간 비교를 없애기 위해서 실패 함수를 사용한다. 문자열 검색 방법 아래 예제는 "ZABC..

요약 시간 복잡도 : 최상 O(n) 최악 O(mn) 브루트 포스 알고리즘이란 완전탐색 알고리즘으로 문제에 나와있는 모든 경우의 수를 시험하는 방법 찾고 싶은 문자열이 있을 때 각각의 문자 하나하나 대조하며 찾아내는 방법 검색할 문자열의 커서와 찾을 문자열의 커서를 두고 한 문자씩 비교 구조가 간단하여 구현 및 이해가 쉽지만 비효율적 알고리즘 브루트-포스법(Brute force) 알고리즘 브루트 포스 알고리즘이란 완전탐색 알고리즘으로 문제에 나와있는 모든 경우의 수를 시험하는 방법이다. 문자열을 검색하는 가장 기초적인 알고리즘으로 꼽히며 찾고 싶은 문자열이 있을 때 하나하나 대조하며 찾아낸다. 브루트 포스 알고리즘은 구조가 간단하여 구현 및 이해가 쉽지만 비효율적 알고리즘이다. 아래 예제는 문자열 "ABA..

요약 시간 복잡도 : O(n log n) ~ O(n ^ 2) 정렬할 데이터에서 피벗을 기준으로 두 개의 비균등한 크기로 분할하는 작업을 반복 피벗 이하의 그룹과 이상의 그룹이 왼쪽, 오른쪽으로 분리되었을 경우 배열을 다시 분할 요소가 1개가 되었을 때 분할을 멈춤 퀵 정렬(Quick Sort) 퀵 정렬이란 정렬할 데이터에서 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬하는 알고리증믈 말한다. 퀵 정렬은 가장 빠른 정렬 알고리즘으로, 찰스 앤터니 리처드 호어(C. A. R. Hoare)가 붙인 이름으로, 속도가 빠른 만큼 많이 사용되는 정렬 알고리즘이다. 만약 어떤 학생 그룹이 있고, 수가 8명이며 키 순서대로 정렬해야 되는 구조가 있다. 먼저 임의의 학생 A를 ..

요약 시간 복잡도 : O(log N) 데이터의 중간 값을 확인해 검색 범위를 반씩 좁혀가는 검색하는 검색 알고리즘 오름차순 또는 내림차순으로 정렬된 데이터 구조에서만 사용할 수 있음 검색이 반복될 때마다 검색 범위가 반으로 좁혀지므로 검색 속도가 빠름 검색 범위를 맨 앞, 맨 끝, 중앙 요소로 두고 중앙 요소의 값으로 학인함 이진 탐색(Binary Search) 이진 탐색이란 데이터가 오름차순 또는 내림차순으로 정렬되어 있을 때 검색하는 정렬 알고리즘이다. 이진 탐색은 정렬되지 않은 데이터에서는 사용할 수 없으나, 선형 검색보다 빠르게 검색할 수 있는 장점이 있다. 데이터의 중간 값을 확인해 검색 범위를 반씩 좁혀가며 검색하는 구조를 가지고 있다. 먼저 정렬된 배열이 있다고 가정한다. [5, 7, 15,..