1. 동적 계획법 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 1.1. 동적 계획법의 핵심 이론 1.1.1. 동적 계획법의 원리와 구현 방식 큰 문제를 작은 문제로 나눌 수 있어야 한다. 작은 문제들이 반복하여 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다. 모든 작은 문제들을 한번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 DP테이블을 이용한다. 이를 메모이제이션 기법이라고 한다. 동적 계획법은 top-down 방식과 bottom-up 방식으로 구현할 수 있다. 1.1.2. 동적 계획법 대표 예시 피보나치 D[N] = D[N-1] + D[N-2] 동적 계획법으로 풀수 있는지 확인하기 D[1] = 1 D..
ALGORITHM/알고리즘
1. 리스트 1.1 리스트란? 연결 리스트, 링크드 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄(선형)로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. (* wikipedia) 1.2. 리스트의 종류 1.2.1. 단일 연결리스트 각 노드가 앞에서 뒤로의 연결만을 가진 연결리스트 단일 연결이기에 각 노드의 포인터에는 후행 노드의 주소값이 저장되어 있다. -> 뒤에서 앞으로의 접근은 불가. public class Node { Node next = null; T data = null; } public class SinglyLinkedList { Node head = null; int length = 0; 이미 리스트가 구현되어 있으므로 구현법을 아는 것은 당장은 중요하지 않음 그러나 실력이 ..
1. 배열 1.1. 배열이란? 배열은 같은 자료형의 변수로 이루어진 구성 요소(component)가 모인 것. 1.1.1 배열의 선언법 int[] a; // 이 쪽을 더 선호함 int a[]; e.g.) 구성 요소의 자료형이 int형이고, 구성 요소의 개수가 5개인 배열 a = new int[5] 초기화 하지 않으면 0으로 초기화 1.1.2 배열 요소의 최댓값 구하기 max = a[0]; for(int i = 1; i max) max = a[i]; } 1.1.3 배열 요소를 역순으로 정렬하기 한번 고민해보세요 :) idx를 거꾸로 뒤집어도 될 것이고, 이분탐색 적으로 반으로 나누어서 각 요소를 치환해도 될 듯? 1.1.4 번외 -> 함수로 만들어 사용하는 방법 메서드를 쪼개서 사용하는 방법 1. 각 요소..
1. 완전 탐색 1.1. 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법 그 중에서도 Back-Tracking 을 통해야 하는 상황을 해결하기! 모든 코테 문제에서 기본적으로 접근해 봐야 한다. 많은 연습이 필요! 장점. 부분 점수 얻기 좋음. 어떻게든 해결하고자 하면 풀림 단점. 시간 복잡도가 좋지 않음 1.2. 완전 탐색 종류 완전 탐색은 함수 정의를 잘 하면 반 이상 해결 가능 1) N개 중 중복을 허용해서 순서 있게 나열 ex) N과M (3) 시간복잡도 : $O(N^M)$ 1초 안에 해결 가능 공간복잡도 : O(M) 2) N개 중 중복을 허용하지 않고 순서 있게 나열 ex) N과M (1) 시간복잡도 : $O(N!/(N-M)!)$ 공간복잡도 : O(M) 3) N개 중 중복을 허용..
1. 그리디 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 1. 1.그리디 알고리즘의 핵심이론 그리디 알고리즘 수행 과정 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다 1.2 그리디 문제 BOJ https://www.acmicpc.net/problem/11047
⌨️ 다익스트라 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하여 문제 해결 가능 기능 특징 시간 복잡도(노드 수: V, 에지 수 :E) 출발 노드와 모든 노드 간의 최단거리 탐색 에지는 모두 양수 O(ElogV) 1. 다익스트라 알고리즘의 핵심 이론 1.1. 인접 리스트로 그래프 구현하기 그림 자리 다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 더욱 좋다. 그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결 1.2. 최단 거리 배열 초기화하기 최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 In..
