목록PS/알고리즘 이론 (18)

한량처럼 살고 싶다

투 포인터

지금까지 아무 생각 없이 문제를 풀었는데 생각해보니 정리한 기억이 없어서 정리를 간단하게 해보려고 한다 ~ https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 ..
PS/알고리즘 이론 2024. 3. 14. 16:41
최단 경로: 다익스트라 알고리즘

01. 기본 개념 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 02. 조건 음의 간선이 없어야만 정상적으로 작동한다(0보다 작은 간선 값이 없어야 작동한다.) 03. 특징 1) 현실 세계의 길은 음의 간선으로 표현되지 않기 때문에 실제 GPS 소프트웨어 기본 알고리즘으로 채택되고는 함. 2) 기본적으로 그리디 알고리즘으로 분류되는데, 그 이유는 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 반복하기 때문이다. 04. 과정 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한..
PS/알고리즘 이론 2024. 2. 1. 16:18
그래프 이론: 위상 정렬

01. 정의 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 02. 과정 진입차수: 해당 노드로 진입하는 간선의 개수 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 03. 시간 복잡도 O(V+E) 위상 정렬을 수행할 때 차례대로 모든 노드를 확인하면서, 그 노드로부터 출발하는 간선을 제거하므로 노드와 간선을 모두 확인한다는 측면에서 O(V+E)의 시간이 걸린다. 공부하는 책 및 내용 출처 https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=247882118 이것이 취업을 위한 코딩 테스트..
PS/알고리즘 이론 2023. 2. 15. 09:16
그래프 이론: 신장 트리

01. 정의 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 (모든 노드를 포함되어 서로 연결되면서, 사이클이 존재하지 않는 그래프 == 트리) 02. 최소 신장 트리 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 03. 크루스칼 알고리즘 과정 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. 모든 간선에 대하여 2번의 과정을 반복한다. 특징 ▶ 크루스칼 알고리즘은 거리가 짧은 간선부터 취하는 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다. ▶ 최종..
PS/알고리즘 이론 2023. 2. 15. 09:09
그래프 이론: 서로소 집합

01. 그래프 복습 그래프의 정의 ▶ 노드와 노드 사이에 연결된 간선 정보를 가지고 있는 자료구조 그래프를 사용(의심)해야 하는 상황 ▶ 서로 다른 개체가 연결되어 있다 그래프에 속한 자료구조 트리 (퀵 정렬, 이진탐색 등) 힙 (다익스트라 알고리즘 등) 등등... 그래프의 구현 방법 인접 행렬: 2차원 배열을 사용하는 방식 인접 리스트: 리스트를 사용하는 방식 구현 방법에 따른 시간 복잡도 (노드개수V, 간선개수 E) 구현 방법 간선 정보 저장 간선 비용 정보 접근 설명 인접 행렬 O(V^2) O(1) 2차원 배열이므로 공간은 제곱, 인덱스로 간선비용 접근가능하므로 상수시간 인접 리스트 O(E) O(V) 간선 정보만 담을 E만큼의 공간 필요, 한 번 간선비용 찾을 때마다 선형탐색하므로 V 02. 서로소..
PS/알고리즘 이론 2023. 2. 15. 08:45
최단경로: 플로이드 워셜 알고리즘

01. 기본 개념 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘 -> 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용한다. 02. 과정 2차원 인접 행렬을 구성 한 단계마다 특정 노드를 중간 지점 노드로 선택하여 경로를 계산한다 예를 들어 노드가 5개가 있다면 1단계에서 고려할 루트는 213, 214, 215, 312, 314, 315, 412, 413, 415, 512, 513, 514 총 12개이다. 213 루트를 비교해본다고 한다면, min(2->3, 2->1+1->3)을 하면 된다(2에서 3으로 가는 것과, 2에서 1 + 1에서 3 중 더 짧은 것을 선택하여 갱신) 2,3,4 과정을 끝날때까지 반복한다. 03. 시간복잡도: O(N^..
PS/알고리즘 이론 2023. 2. 14. 09:36
최단 경로

정의 가장 짧은 경로를 찾는 알고리즘 특징 이미 상황에 맞는 효율적인 알고리즘들이 정립되어 있음. 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많음 컴퓨터공학 관련 학부 수준에서 사용하는 알고리즘은 다익스트라, 플로이드 워셜, 벨만 포드 3가지이다.
PS/알고리즘 이론 2023. 2. 14. 08:01
다이나믹 프로그래밍(DP)

01. 개념 ➡️메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다는 점에서 고안됨 02. 조건 다이나믹 프로그래밍을 사용하기 위한 조건이다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 정답이다. 1번 특징을 보면 다이나믹 프로그래밍(DP)과 퀵정렬에서 나온 분할정복이 헷갈릴 수 있다. 둘의 차이점은 DP는 작은 문제가 여러 문제에 영향을 끼친다는 것이고, 분할정복은 그렇지 않다는 것이다. 03. 탑다운(Top-Down) 방식과 보텀업(Bottom-Up) 방식 1️⃣탑다운 방식 (하향식) 큰 문제를 해결하기 위해 작은 문제를 호출함 * 메모제이션 방식: 이전에 계산된 결과를 일시적으로 기록해두고, 그것을 풀이할 때 다시 사용하는 ..
PS/알고리즘 이론 2023. 2. 10. 21:41
이전 Prev 1 2 3 Next 다음