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와 연결된..
-
[BOJ] 1753번 - 최단경로Algorithm/BOJ 2022. 8. 31. 00:51
문제 BOJ 1753번 최단 경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 이해 더보기 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까..
-
[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일 때의 최대값을 구할..
-
[프로그래머스] - N으로 표현Algorithm/프로그래머스 2022. 8. 30. 15:58
문제 [프로그래머스] - N으로 표현 https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=python3# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가..