algorithm
그래프 자료구조 정리 (프림, 크루스칼, 다익스트라)
Prim 알고리즘 프림 알고리즘은 무향 그래프에서 MST(최소 스패닝 트리)를 찾는 알고리즘이다. 시작점에서 정점을 추가해 가면서 트리를 확장한다. 동작 정점 탐색 시 인접 정점 중 비용이 가장 작은 간선으로 연결된 정점을 선택해 연결한다 시작 정점을 MST에 추가한다 MST 집합...
#algorithm
19개의 글
java
조합과 순열을 자바로 구현해 보자
조합(combination) 조합론에서 조합은 서로 다른 n개의 원소를 가지는 어떤 집합에서 순서에 상관없이 r개의 원소를 선택하는 것이며, 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것 혹은 찾는 것과 같다.(위키백과) 조합의 개수 공식: 위키...
algorithm
다이나믹 프로그래밍 (이것이 취업을 위한 코딩 테스트다)
이것이 취업을 위한 코딩 테스트다를 정리한 글입니다. 다이나믹 프로그래밍 메모리를 적절히 사용해서 수행 시간을 향상시키는 방법이다 한 번 계산한 문제는 다시 계산하지 않도록 구현된다. 완전 탐색보다 시간 복잡도를 줄일 수 있다. 탑 다운과 바텀 업 방식 두가지가 있다 동적 계획법이...
algorithm
그래프 (Python Algorithm interview 12장)
파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다. DFS(깊이 우선 탐색) BFS(너비 우선 탐색) def iter_BFS(start_v): discovered = [start_v] queue = [start_v] while queue: v = queue.pop(0) for w ...
algorithm
이진 탐색 (이것이 취업을 위한 코딩 테스트다)
이것이 취업을 위한 코딩 테스트다를 정리한 글입니다. 순차 탐색 순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 리스트를 단순히 for문으로 돌면서 원하는 값을 찾는 경우도 순차 탐색이라고 볼 수 있다. 이진 탐색 이...
algorithm
Hash map (Python Algorithm interview 11장)
파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다. 해시맵 디자인 다음의 기능을 제공하는 해시맵을 디자인하라. put(key, value): 키, 값을 해시맵에 삽입한다. 이미 존재하는 키라면 업데이트 한다. get(key): 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는...
algorithm
deque, 우선순위 큐 (Python Algorithm interview 10장)
파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다. K개 정렬 리스트 병합 k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라. 입력 [ 1->2->5, 1->3->4, 2->6 ] 이 문제에서는 우선순위 큐로 해결할 수 있으며 PriorityQueu...
algorithm
DFS/BFS (이것이 취업을 위한 코딩 테스트다)
이것이 취업을 위한 코딩 테스트다를 정리한 글입니다. 탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 탐색 알고리즘으로 DFS/BFS가 있으며 이번 포스팅에서 다뤄보려고 한다. DFS(Depth-First Search) 깊이 우선 탐색이라고 하며, 그래프에서 깊은 부...
algorithm
그리디 알고리즘 (이것이 취업을 위한 코딩 테스트다)
이것이 취업을 위한 코딩 테스트다를 정리한 글입니다. 그리디 알고리즘 그리디 알고리즘은 “현재 상황에서 지금 당장 좋은 것만 고르는 방법”이다. 매 순간 가장 좋은 선택을 하고, 현재의 선택이 나중에 미칠 영향은 고려하지 않는 방법이다. 거스름돈 거스름돈 문제는 그리디 알고리즘을 ...
algorithm
연결 리스트 (Python Algorithm interview 8장)
파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다. 페어의 노드 스왑 입력 1 -> 2 -> 3 -> 4 출력 2 -> 1 -> 4 -> 3 값만 교환 def swapPaire(self, head): cur = head while cur and cu...
algorithm
배열 (Python Algorithm interview 7장)
파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다. #12 주식을 사고팔기 가장 좋은 시점 한 번의 거래로 낼 수 있는 최대 이익을 산출하라 입력 prices = [7, 1, 5, 3, 6, 4] 출력 5 Brute Force 계산 def bruteForce(prices: list...
algorithm
문자열 조작 (Python Algorithm interview 6장)
파이썬 알고리즘 인터뷰 6장을 정리한 내용입니다. 문자열을 변경하거나 분리하는 등의 여러 과정을 말한다 문자열 조작은 코테에서 상당히 빈번하게 출제됨 사용되는 분야 정보처리분야 통신 시스템 분야 프로그래밍 시스템 분야 유효한 팰린드롬(p.139) 주어진 문자열이 팰린드롬인지 확인하...
algorithm
다이나믹 프로그래밍 (Python Algorithm interview 23장)
파이썬 알고리즘 인터뷰 23장을 정리한 내용입니다. 다이나믹프로그래밍 다이나믹프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다 다이나믹 프로그래밍을 이용해 문제의 최적 해결 방법이 부분 문제에 대...
algorithm
분할 정복 알고리즘 (Python Algorithm interview 22장)
분할정복 분할정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말함 분할 정복은 직접 해결 가능할 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다 분할 정복의 순서 분할: 문제를 동일한 ...
algorithm
Greedy Algorithm (Python Algorithm interview 21장)
그리디 알고리즘 p.585 그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다 합리적인 시간 내에 최적에 가까운 답을 찾을 수 있다 다이나믹 프로그래밍이 하위 문제에 대한 최적의 솔루션을 찾은 다음, 결과들을 결합한 정보...
algorithm
List, Dictionary (Python Algorithm interview 5장)
파이썬 알고리즘 인터뷰 5장을 정리한 내용입니다. List 순서대로 저장하는 시퀸스이자 변경 가능한 목록이다. 입력 순서가 유지되며 내부적으로는 동적 배열로 구현되어 있다 다양한 기능을 제공한다 스택과 큐 중 어떤걸 사용할지 고민하지 않아도 된다 리스트 주요 시간 복잡도 O(1) ...
algorithm
비트 조작, 해밍 거리 (Python Algorithm interview 19장)
파이썬 알고리즘 인터뷰 19장을 정리한 내용입니다. Hamming Distance 해밍거리는 같은 길이를 가진 두 개의 문자열에서 같은 위치에 있지만 서로 다른 문자의 개수이다 컴퓨터 통신에서 문자열 전송 시 에러 검출에 사용되는 방법 중 하나이다 비트 조작 부울 연산자 기본적인 ...
algorithm
이진 탐색 (Python Algorithm interview 18장)
파이썬 알고리즘 인터뷰 18장을 정리한 내용입니다. 이진 검색 Binary Search(이진 검색)이란 정렬된 배열에서 타겟을 찾는 검색 알고리즘이다. 이진 검색은 값을 찾아내는 시간 복잡도가 $O(\log n)$ 이라는 점에서 대표적인 로그 시간 알고리즘이며, 이진 탐색 트리와 ...
algorithm
병합 정렬, 삽입 정렬 (Python Algorithm interview 17장)
파이썬 알고리즘 인터뷰 17장을 정리한 내용입니다. 합병 정렬 출처: https://holypython.com/merge-sort-algorithm-python-code/ 비교 기반 정렬 알고리즘으로 분할 정복 알고리즘 중 하나이다 입력된 배열을 같은 길이의 2개 부분으로 분할한다...