Algorithm/Algorithm
-
[Algorithm] - DPAlgorithm/Algorithm 2022. 9. 1. 22:30
DP(Dynamic Programming) 동적 프로그래밍으로, 큰문제를 작은 문제로 나누어 푸는 문제이다. Devide & Conquer과 비슷하지만, DP는 작은 문제로 나누어 반복되는 것을 이용해가면서 푸는 것이다. 반복되는 작업을 푸는 것은 Recursion으로 풀이가 가능하지만, 반복되는 작업을 또 하기보다 값을 저장하여 두고 다시 재사용하는 방식으로 푸는 것이 특징. ( Memoization) 대표 문제 Fibonacci / Knapsack problem 아래 그림과 같은 형태로 재귀로 풀이가 가능하지만, 매번 재귀로 풀이시 동일한 값을 또 사용할 수 있다. BOJ 2293번 각 Data에서 단계를 나누어 가능한 경우의 수를 늘려준다. idx 0 1 2 3 4 5 6 7 8 9 10 (k) d..
-
[Algorithm] - 위상 정렬Algorithm/Algorithm 2022. 9. 1. 22:26
위상 정렬 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬 싸이클이 존재하는 경우는 발생할 수 없다 일반적으로 방향그래프로 설정이 되어 있기 때문에 Indegree 값이 0인 Node들에서 먼저 시작하면서 VFS 처럼 구현하면 된다. 위상 정렬의 결과가 Node들의 수와 동일해야 한다! ( 동일하지 않는 경우는 Cycle이 발생된 경우 ) 알고리즘 시간 복잡도 : O( V+E ) 1. 처음 방향 그래프들의 Edge를 읽으며, Indegree Table을 설정 2. Indegree가 0인 Node들을 Queue에 넣는다. 3. Queue에 Node들을 꺼내며, 위상 정렬 값 추가 4. 연결된 Node들의 Indgree값을 줄여주고 , 0이면 Queue에 추가 5. 3~4..
-
[Algorithm] - HEAP(우선 순위 QUEUE)Algorithm/Algorithm 2022. 9. 1. 16:56
Heap - 우선 순위 Queue Pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 , 우선 순위가 가장 높은 원소가 나온다. 원소의 추가 O(LogN) 우선 순위 높은 ITEM 확인 O(1) 우선 순위 높은 순서 제거 O(LogN) 이진 검색 트리와 Heap 은 다른 자료 구조다. import heapq BOJ 1715번 - 카드 정렬하기 IDEA 1. 작은 값 2개 값을 더하는게 최소의 경우이다. ( GREEDY ) -> 작은 값을 더하지 말고 다른 값을 더하였을 경우보다 더 작은 경우가 발생 불가능! 2. 수의 범위가 1000일 때, 10만개인 경우에 INT형의 범위를 벗어나는가? -> INT형의 범위를 벗어나지 않아 별도로 생각하지 않아도 된다. 3. 예외 처리 1개만 들어온 경우는 최소..
-
[Algorithm] - 다익스트라Algorithm/Algorithm 2022. 8. 31. 00:51
다익스트라 방향, 무방향 그래프에서 하나의 시작점으로 부터 다른 Node까지의 최단 거리를 구하는 알고리즘 Edge에 음수인 가중치가 있다면 절대 사용 불가! 유사 알고리즘으로 A* 알고리즘이 존재하지만, 길찾기와 같이 Node가 엄청 많을 때 유사값을 찾는 용도이다. 거리가 확정되지 않은 Edge 중에서 가장 가까운 Edge를 선택한다는 그리디 알고리즘으로 부터 착안한다. O(V^2+E) => 갱신 가능 아래와 같은 그래프에서 1부터 시작한다면, 각 Node별로 최단 거리 값이 결과가 나타난다. 1에서는 갈 수 있는 Node가 2,3,4 총 3가지다. 이중에서 가장 작은 Edge는 Node 3과 연결된 2로 갱신 시키고 Node에 대해 확정을 시켜준다. 연결된 가장 작은 Edge는 Node 2와 연결된..
-
[Algorithm] - Graph( Node / Edge/ BFS / DFS )Algorithm/Algorithm 2022. 8. 30. 19:53
1. Graph Node와 Edge로 이루어진 자료구조 1-1) Direction fo Edge Degree = Node에 연결되어 있는 edge의 수 Indegree = Node로 들어오는 edge의 수 Outdegree = Node에서 나가는 edge의 수 Airflow의 기본 구조 1-2) 싸이클 임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로 순환 그래프(Cyclic graph) = 싸이클이 한개 이상 비순환 그래프(Acyclic graph) = 싸이클이 X 1-3) 연결 그래프 서로 다른 Node 연결되어 있는 Edge를 보고 완전 그래프 / 연결 그래프인지 확인 주의점 : 일반적인 코딩테스트에 나오는 그래프는 단순 그래프(정점 사이의 Edge는 한개이며, 루프가 존재하지 않는다 )..
-
이분 탐색Algorithm/Algorithm 2022. 8. 30. 19:44
Binary search(이분탐색) 정렬 되어 있는 리스트에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하게 되면 O(N) -> 범위를 줄반씩 줄여 O(logN)으로 탐색 일반적으로는 Start , End , Mid 를 사용하여 탐색 ( Merget Sort 처럼 ) Mid 값을 주의하여 무한루프 주의! bisect library를 사용하여도 된다. 1) Parametic search 최적화 문제를 결정 문제로 변형 이분탐색 수행 일반적으로 도출 되는 함수는 Linear 해야 한다! (증가 및 감소 함수) 2 ) BOJ 1654번 (최적화) N개를 만들 수 있는 랜선의 최대 길이? (결정)길이가 X인 경우에 랜선이 N개 이상인지 아닌지 여부 랜선의 길이를 이분탐색하여 N일 때의 최대값을 구할..
-
코딩 테스트 문자열 처리 시 주의점Algorithm/Algorithm 2022. 6. 22. 16:13
BOJ 13414번을 풀다가 쉽게 놓칠 수 있는 문자열 처리 경우의 수에 대해 정리하여 본다. https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 주의 점 1. 문자열 -> Int -> Key 접근 시 위 문제를 보면 일반적으로 아무 생각 없이 Dictionary에 Key로 구현하여 값을 넣는데, 이 때 Key에 관련된 문자열을 넣을 때 Int 형으로 바꾸어서 입력을 넣게 되면, 학번과 같은 경우는 앞이 0이 나올 수가 있어 예외가 발..
-
[Algorithm] - 문자열 매칭 ( 보이어무어 알고리즘 )Algorithm/Algorithm 2022. 4. 27. 02:20
보이어-무어 알고리즘 부르트포스, KMP 알고리즘보다 향상된 알고리즘이며 더 자주 사용된다고 한다. 보이어-무어 알고리즘의 작동은 KMP 알고리즘과 유사하게 불필요한 비교는 건너뛰고 유의미한 비교만 진행하겠다. 알고리즘 KMP 알고리즘의 개선이 된 알고리즘으로, 시간 복잡도는 최악의 경우 O(N) 평균적인 경우 O(N/M)입니다. 이전에 KMP 알고리즘이 O(N+M)이기 때문에 향상이 이루어졌습니다. KMP 알고리즘의 경우에는 접두사와 접미사가 같은 최대길이를 저장하는 배열을 만들어 앞에서부터 검사를 진행하였다면, 보이어-무어 알고리즘은 문자열을 검색할때 주로 뒤에서 부터 확인합니다. KMP 알고리즘과 같이 건너뛰는 경우를 저장하는 배열(skip_table)을 만들어야 합니다. 이때 배열은 본문 문자열이..