kingsubin

위상정렬 (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인..

전체적으로 크게 나누자면 단순구조, 선형구조, 비선형 구조로 볼 수 있다. 단순구조는 기본형 타입의 구조를 말하며 정수, 실수, 문자, Boolean 타입이 있다. 기본형 타입을 제외하면 선형 데이터 구조와 비선형 데이터 구조가 있는데 어떤 점이 다를까 ? 선형 데이터 구조와 비선형 데이터 구조의 차이 선형 데이터 구조 - 데이터 요소가 이전 및 다음 인접 요소에 연결되어있으며 순차적으로 또는 선형으로 배열되는 구조 - 단일 실행을 모든 요소를 횡단할 수 있다. - 구현하기 쉽다. - 예로는 Array, Stack, Queue, LinkedList 가 있다. 비선형 데이터 구조 - 반대로 데이터 요소가 순차적으로 또는 선형으로 배열되지 않은 구조를 비선형 데이터 구조라고 한다. - 단일 실행으로 모든 요..

비트 연산 (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 로 쓸 수 있다. 비트 연산..

다이나믹 프로그래밍 Dynamic Programming (DP) - 메모리를 적절히 사용하여 수행 시간을 비약적으로 증가시키는 방법 - 이미 계산된 결과 (작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식 (탑다운, 보텀업)으로 구성된다. 다이나믹 프로그래밍의 사용 조건을 만족하는지 먼저 확인 1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다. 2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결한다. 다이나믹 프로그래밍 vs 분할정복 - 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다. - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해..

트리 (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..

그리디 & 구현 - 시각 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..

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 ? - 데이터가 더 이상 존재하지 않을 때 우리는 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..