목록알고리즘 (20)
DOing
💡 정렬 알고리즘 정렬이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘은 굉장히 다양한데 이번 포스팅에서는 가장 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 다뤄보려고 한다. 정렬 수행시에는 상황에 맞는 알고리즘을 선택해야 효율적으로 작동할 수 있다. 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 시간 복잡도 O(N^2) O(N^2) O(NlogN) O(N+K) 공간 복잡도 O(N) O(N) O(N) O(N+K) 추천 상황 간단 거의 정렬되어 있는 경우 일반적인 경우 데이터 크기 범위가 작은 경우 (N : 데이터의 갯수, K : 데이터 최대값의 크기) * 현 포스팅에서는 오름차순만 다루고 있다. 내림차순 정렬은 알고리즘에서 크기 비교를 반대로 수행하거나 리스..
💡 BFS 알고리즘 Breath-First Search, 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘이다. 너비 우선 탐색이라고도 한다. 데이터가 N개 있을때 O(N)시간 복잡도를 가진다. 일반적인 경우 실제 수행시간은 DFS보다 좋은편이다. [DFS vs BFS] 동작 방식 동작 원리 구현 인접한 노드가 여러개라면? DFS 멀리 있는(깊게 있는)노드 부터 탐색 스택 재귀 함수 이용 한개씩 넣음 BFS 가까운 노드부터 탐색 큐 큐 자료구조 이용 한번에 다 넣음 💡 BFS 동작과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다, 3. 2번과정을 더이상 수행할 수 없을 때까지 반..
💡 DFS 알고리즘 Depth-First Search, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 데이터의 갯수가 N개인 경우, O(N)의 시간복잡도를 가진다. 💡 DFS 동작과정 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그 인접노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접노드가 없으면, 스택에서 최상단 노드를 꺼낸다. 3. 2번과정을 더이상 수행할 수 없을 때까지 반복한다. [참고] 그래프의 두 노드가 가나선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현한다. DFS에서 인접한 노드가 여러개 일 수 있다. 그래서 스택에 어떠한 노드부터 방문할 것인지에 대한 기준이 필요하다. 이는 문제마다 다..
💡 구현 구현이란 '알고리즘을 소스코드로 바꾸는 과정'이라고 할 수 있다. 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않지만, 코딩테스트에서는 구현이 중심으로 되는 문제가 자주 출제되기 때문에 다뤄보기로 한다. 보통 구현문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 예를 들어서 완전 탐색, 시뮬레이션 문제 유형이 있다. 완전 탐색은 모든 경우의 수를 계산하는 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한단계씩 차례대로 직접 수행해야하는 문제유형을 의미한다. 💡 주의점 완전 탐색처럼 많은 경우의 수를 계산할때 주의해할 점은 일반 코딩 테스트환경에서는 파이썬으로 제출한 코드가 1초에 2000만번(2*10^7)의 연산을 수행하는 것이다. 대부분의..
💡 그리디 알고리즘 "지금 당장 좋은 것만 고르는 방법" 한국어로 번역하면 탐욕법이라고 할 수 있는데, 이름 그대로 어떠한 문제가 생겼을 때 단순 무식하게 탐욕적으로 문제를 해결하는 알고리즘이다. 단순하지만 강력한 문제 해결방법이다. 💡 그리디 알고리즘 사용시 주의점 그리디 알고리즘의 해가 '최적 해'를 항상 보장하는 것은 아니다. 때문에 그리디 알고리즘을 적용할 때 주의해야할 것은 "해당 방법이 정당성을 가지고 있는가?"이다. 💡 그리디 알고리즘 대표적 예시 Q1. 거스름돈 구하기 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재한다. 손님에게 거슬러 줘야할 돈이 N원일때 거슬러 줘야할 동전의 최소개수를 구하라. [문..
정규 표현식을 이용하게되면 원하는 문자열을 간단하게 검색할 수 있습니다. 원하는 문자열이 복잡하더라도 짧고 간결한 코드로 검색할 수 있다는 것이 장점입니다. 💡 정규표현식? 특정한 규칙을 가진 문자열의 집합을 표현하는데 사용되는 형식언어입니다. 주로 문자열 검색과 치환에 쓰입니다. 정규표현식은 표준인 POSIX의 정규표현식과 POSIX에서 확장된 perl방식의 PCRE가 대표적입니다. 이외에도 수많은 정규표현식이 존재합니다. 약간의 차이점은 있지만 거의 비슷합니다. 💡 정규표현식의 기초, 메타 문자 정규표현식에 사용하는 기호를 메타 문자라고 합니다. 메타문자는 표현식 내부에서 특정한 의미를 가지는 문자를 말합니다. 지금부터 메타문자의 종류에 대해서 알아보겠습니다. . ^ $ * + ? { } [ ] \ ..
💡 우선순위 큐? 일반적인 큐는 First-In-First-Out구조이지만, 우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저나오는 구조이다. 우선순위 큐를 배열이나 연결리스트로 구현할 시에는 우선순위에 맞게 데이터를 삽입하는 시간이 오래걸리게 된다. 때문에 우선순위 큐는 힙을 이용해서 구현한다. 💡 힙? 힙은 최대값과 최소값을 빠르게 찾기 위해 고안된 완전이진트리이다. (=변형된 트리의 형태) [ 힙의 구조 ] : 최대값을 구하기 위한 구조인 최대힙과 최소값을 구하기 위한 구조인 최소힙이 있다. 힙은 다음과 같이 두가지 조건을 가지고 있는 자료구조이다. (최대힙 기준) 1) 부모노드는 자식노드의 값보다 크거나 같다. 2) 완전 이진 트리형태 [ 힙과 이진 탐색 트리 비교 ] * ..
💡 트리 : 트리는 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다. Level : 루트노드부터 현재 노드까지의 깊이 Height(높이) : 트리에서 노드가 가질 수 있는 최대 Level : 해당 트리의 높이는 3이다. 💡 이진트리(Binary Tree) : 이진트리는 노드의 최대 브랜치가 2인 트리이다. Q1. 이진트리에 있는 각 레벨의 최대 노드의 개수는? 레벨이 k일때, 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k 개이다. 1 Level 0 -> 1개 2 3 Level 1 -> 2개 4 5 6 7 Level 2 -> 4개 8 9....... 14 15 Level 3 -> 8개 Level k -> 2^k 개 Q2. 높이가 h이고 꽉 차있는 이진 트리라면, ..