Algorithm
-
위상정렬 정리Algorithm 2021. 6. 26. 20:47
위상정렬 (Topological Sort) 위상 정렬은 선행 조건들을 가진 일들의 수행 순서를 정한다. 이 순서는 일들의 선행 조건들을 만족시켜야 한다. 예시를 들어보자. 한 학과의 학생들이 수강해야만 하는 7개의 필수 과목들이 있다. (1~7) 어떤순서로 강의를 수강해도 상관이 없지만, 선후수 관계는 만족시켜야한다. 2의 선수과목은 1 4의 선수과목은 1, 2, 3 5의 선수과목은 3 6의 선수과목은 2, 4, 5 7의 선수과목은 5, 6 이 순서에서 그래프의 각 간선 (v, w) 에 대해 v가 w보다 먼저 나와야한다. 이와 같은 순서를 찾는것이 위상정렬 이다. 조건 주어진 방향 그래프에 순환이 없어야 한다. (directed acyclic graph, DAG) Queue를 이용한 방법 진입차수가 0인..
-
자료구조 정리Algorithm 2021. 1. 26. 22:55
전체적으로 크게 나누자면 단순구조, 선형구조, 비선형 구조로 볼 수 있다. 단순구조는 기본형 타입의 구조를 말하며 정수, 실수, 문자, Boolean 타입이 있다. 기본형 타입을 제외하면 선형 데이터 구조와 비선형 데이터 구조가 있는데 어떤 점이 다를까 ? 선형 데이터 구조와 비선형 데이터 구조의 차이 선형 데이터 구조 - 데이터 요소가 이전 및 다음 인접 요소에 연결되어있으며 순차적으로 또는 선형으로 배열되는 구조 - 단일 실행을 모든 요소를 횡단할 수 있다. - 구현하기 쉽다. - 예로는 Array, Stack, Queue, LinkedList 가 있다. 비선형 데이터 구조 - 반대로 데이터 요소가 순차적으로 또는 선형으로 배열되지 않은 구조를 비선형 데이터 구조라고 한다. - 단일 실행으로 모든 요..
-
비트마스크 (BitMask)Algorithm 2020. 12. 9. 10:17
비트 연산 (Bitwise operation) & (and) | (or) ~ (not) ^ (xor) not 연산의 경우에는 자료형에 따라 결과가 달라진다. A = 83 = 0101,0011(2) ~A = 1010,1100(2) / 8비트 자료형인 경우 ~A = 1111,1111 1111,1111 1111,1111 10101,100(2) / 32비트 자료형인 경우 Shift Operators 1. shift left (> 1 = 101(2) = 5 10 >> 2 = 10(2) = 2 10 >> 3 = 1(2) = 1 30 >> 1 = 1111(2) = 15 1024 >> 10 = 1(2) = 10 A > B 는 A / 2^B 와 같다. (A+B) / 2 는 (A+B) >> 1 로 쓸 수 있다. 비트 연산..
-
다이나믹 프로그래밍 정리Algorithm 2020. 9. 9. 16:36
다이나믹 프로그래밍 Dynamic Programming (DP) - 메모리를 적절히 사용하여 수행 시간을 비약적으로 증가시키는 방법 - 이미 계산된 결과 (작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식 (탑다운, 보텀업)으로 구성된다. 다이나믹 프로그래밍의 사용 조건을 만족하는지 먼저 확인 1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다. 2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결한다. 다이나믹 프로그래밍 vs 분할정복 - 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다. - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해..
-
트리 정리Algorithm 2020. 9. 7. 16:58
트리 (tree) 자료구조의 일종 사이클이 없는 연결 그래프 정점의 개수 : V 간선의 개수 : V-1 정점 V, 간선 V 개 라면 사이클이 1개 있다. 정점 V, 간선 V-1 개라면 트리라 할 수 있을까 ? 아니다. 왜냐면 연결이 되어있지 않다. 정점 V, 간선 V-1 개 라는것은 트리의 성질이다. 트리가 맞을려면 연결되어있다는 조건이 추가되어야 한다. 트리를 구성하는 요소 - node - edge root - 트리의 가장 윗부분에 위치하는 노드 - 하나의 트리에는 하나의 루트가 존재 reaf (terminal node, external node) - 트리의 가장 아랫부분에 위치하는 노드 - 더 이상 뻗어나갈 수 없는 마지막 노드 Parent - Parent가 없는 V를 Root라고 할 수 있다. Ch..
-
그리디&구현, DFS&BFSAlgorithm 2020. 9. 1. 21:52
그리디 & 구현 - 시각 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); /** * 구현 * 시각 * N시 59분 59초까지 3이 하나라도 포함되는 모든 경우의 수 */ int h = Integer.parseInt(br.readLine()); int cnt = 0; for (int i = 0; i n) continue; // 이동 수행 x = nx; y = ny; } System.out.println(x + " " + y); } } DFS & BFS..
-
LinkedListAlgorithm 2020. 8. 31. 16:36
public class Node { public T data; public Node next; public Node(T data) { this.data = data; this.next = null; } } public class MySingleLinkedList { public Node head = null; public int size = 0; public MySingleLinkedList() {} public void addFirst(T item) { Node newNode = new Node(item); newNode.next = head; head = newNode; size++; } public void addAfter(Node before, T item) { Node newNode = new ..
-
EOF (End of File)Algorithm 2020. 8. 29. 14:58
EOF ? - 데이터가 더 이상 존재하지 않을 때 우리는 EOF (End of Fil) 즉, 파일의 끝이라고 한다. 입력의 종료가 정해져 있지 않은 문제 ex) boj 10951 (A+B-4) https://www.acmicpc.net/problem/10951 1. 입력의 종료는 더 이상 읽을 수 있는 데이터 (EOF) 가 없을 때 종료한다. - Scanner에서 처리하는 방법 - BufferedReader에서 처리하는 방법 Scanner in=new Scanner(System.in); while(in.hasNextInt()){ int a=in.nextInt(); int b=in.nextInt(); System.out.println(a+b); } (1)Scanner BufferedReader br = n..