NineTwo meet you

스택 Stack 먼저 넣은 데이터가 가장 나중에 나오는 형태의 자료구조를 의미한다. 스택은 Last In Frist Out의 LIFO 구조이다. 이는 First In First Out의 큐 Queue와 반대된다고 생각할 수 있다. 실생활에서 간단한 예시를 들자면 프링글스를 생각할 수 있다. 과자의 맨 밑에 들어있는 과자가 가장 먼저 들어갔지만 먹는 순서는 가장 나중에 들어간 과자부터 먹을 수 있다. 스택 선언 스택를 사용하기 위해서는 Stack을 import 해야 한다. import java.util.Stack; // Stack 이름 = new Stack(); // ex Stack st = new Stack(); push 스택에 자료를 집어넣을때 사용하는 메소드다. st.push(1); st.push(2..

큐 Queue 먼저 넣은 데이터가 먼저 나오는 형태의 자료구조를 의미한다. 이를 FIFO라고도 하는데 First In First Out의 의미를 지닌다. 실생활에서 간단한 예시를 들자면 지하철을 기다리는 사람들의 줄을 생각하면 쉽다. 지하철이 도착하면 가장 먼저 도착해서 맨 앞줄에 서있던 사람부터 지하철에 탑승하는 모습이 그 예시라고 볼 수 있다. 큐 선언 큐를 사용하기 위해서는 Queue와 LinkedList를 모두 import 해야 한다. import java.util.Queue; import java.util.LinkedList; // Queue 이름 = new LinkedList(); // ex Queue q = new LinkedList(); offer 큐에 자료를 집어넣을때 사용하는 메소드다...

배열 Array 같은 타입의 데이터들을 그룹핑해서 관리하기 위한 데이터 구조를 의미한다. 예를 들면 A반에 학생 30명이 존재한다고 가정하자. 김영희, 김철수, ..., 홍길동 각각의 학생 데이터들을 한번에 관리하면 쉽게 관리할 수 있지 않을까? 다음과 같이 index를 가진 한반이라는 배열을 통해 학생 데이터를 인덱스를 가지고 쉽게 관리할 수 있다는 생각을 할 수 있다. 이것이 배열이다. index 0 1 ... 29 김영희 김철수 ... 홍길동 배열 선언 배열을 기본적으로 하나의 값을 저장할 수 있다. 배열은 선언과 동시에 메모리를 할당할 수도 있고 선언을 하고 후에 메모리를 할당할 수도 있다. 데이터 순서에 따라 index가 부여되는데 index는 무조건 0부터 시작한다. 기본적으로 변수는 선언시 ..

중앙 처리 장치 Central Processing Unit CPU : Central Processing Unit 컴퓨터의 일종의 뇌 역할을 하는 마더보드로 데이터의 전달 통로가 디자인 되어있는 메인보드를 의미한다. 실행 프로그램의 명령 해석, 실행, 장치 제어, ALU, CU, 각종 레지스터로 구성되어 있다. MPU : Micro Processing Unit CPU를 고밀도 직접회로화 한 일종의 통합장치를 의미한다. 컴퓨터의 핵심 기능인 명령 해석 및 연산을 수행 기능에 중점을 두고 있습니다. 그렇기 때문에 MPU는 주변에 RAM, ROM , I/O 등의 장치를 추가해주지 않으면 작동이 불가하다. 헷갈릴만한 MCU도 있는데 이는 CPU의 기능을 하는 핵심 장치와 그 주변 장치들을 포함하고 있는 통합형 칩..

데이터의 표현 정보 Information 가공된 데이터를 의미하며 어떤 사물에 대한 소식이나 자료를 의미한다. 데이터 Data 정보의 원재료를 의미하며 정보를 작성하기 위해 필요한 자료나 정보를 처리하거나 전송할때 이진이나 디지털과 같은 편리한 형태로 바뀐 자료를 의미한다. 비트 Bit 0, 1 바이트 Byte 1 byte = 8 bit 워드 Word 1 Word = 32 bit or 64 bit 기계에 따라 상이함 킬로바이트 KB KiloByte 1 KB = 1024 byte = 2 ^ 10 byte 메가바이트 MB MegaByte 1 MB = 1024 Kbyte = 2 ^ 20 byte 기가바이트 GB GigaByte 1 GB = 1024 Mbyte = 2 ^ 30 byte 테라바이트 TB TeraB..

비트 마스크란? 정수의 이진표현을 자료구조로 쓰는 기법을 의미한다. 비트 연산자 & AND 두 비트가 모두 0이면 1 | OF 두 비트가 모두 1이면 1 ^ XOR 두 비트가 서로 반전되면 1 ~ NOT 비트의 반전 > y x의 각 비트를 y만큼 오른쪽으로 이동하고 왼쪽 빈자리는 최상위 부호 비트와 같은 값으로 채움 >>> x >>> y x의 각 비트를 y만큼 오른쪽으로 이동하고 왼쪽 빈자리는 0으로 채움 부분 집합 비트 마스크를 이용하여 공집합부터 꽉찬 집합까지 표현이 가능하다. 배열의 개수가 n인경우 (1 2 {2,1} -> 011 -> 3 {3} -> 100 -> 4 {3,1} -> 101 -> 5 {3,2} -> 110 -> 6 {3,2,1} -> 111 -> 7 원소 포함 여부 확인 k라는 수의..

// 최대 공약수 static int GCD(int a, int b) { while(b > 0) { int temp = a; a = b; b = temp%b; } return a; } // 최소 공배수 // a*b할때 int 범위 초과할 수 있으니 유의해야 한다. static int LCM(int a, int b) { return (a*b)/GCD(a, b); }

프림 (Prim) 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나 하나의 시작점으로 구성된 트리에 간선을 하나씩 추가하는 방식 동작 과정 1. 그래프를 확인하고 출발 노드를 우선순위 큐에 저장한다. (start, 0) 이때 저장되는 가중치는 자기 자신이므로 0이다. 우선순위 큐 : (0, 0) 2. 우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다. 이때 한번 지나갔던 정점은 추가하지 않는다. 우선순위 큐 : (2, 1), (1, 5) 3. 우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다. 이때 한번 지나갔던 정점은 추가하지 않는다. 우선순위 큐 ..

크루스칼 (Kruskal) 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나 간선이 하나도 없는 상태에서 시작해 하나씩 트리에 간선을 추가해 가는 탐욕적 알고리즘 간선을 오름차순으로 정렬하고 이미 트리에 추가된 간선과 사이클을 이루지 않을 때 간선을 추가 간선이 사이클이 되지 않는지 확인하기 위해 유니온 파인드를 사용 동작 과정 1. 가중치가 오름차순으로 정렬된 우선순위 큐에 모든 간선을 추가한다. 우선순위 큐 (노드 1, 노드 2, 두 노드 사이의 가중치) : (0,1,1), (1,3,1), (2,3,2), (5,6,2), (1,5,3), (1,6,3), (3,6,3), (0,1,5), (3,4,5) 2. poll 한 값의 두 노드의 부모가 같은지 판단(사이클 여부 확인)..

플로이드 와샬(Floyd Warshall) 모든 쌍의 최단 거리 알고리즘 두 정점 사이에 간선이 없는 경우 어떤 경로의 길이보다도 큰 값으로 처리 3중 for문 사용 자기 자신으로 가는 간선은 항상 0으로 초기화 int n; // 정점의 수 int m; // 간선의 수 int adj[][] = new int[n+1][n+1]; // 그래프의 인접행렬 // 간선이 없는 경우 어떤 경로의 길이보다 큰 값으로 초기화 // 자기 자신으로 가는 간선 0으로 초기화 for(int i = 0; i v 로 향하는 가중치 w를 가지는 간선 for(int i = 0; i < m; i++) { Str..