Algorithm (12) 썸네일형 리스트형 [Algorithm] 서로소 집합 (Union-Find) 서로소 집합 표현 방법 1. Linked List - 같은 집합의 원소들은 하나의 연결 리스트로 관리한다. - 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. - 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다. 2. Tree 서로소 집합 연산 Make-Set(x) : 최소 단위 집합 생성 Make-Set(x) p[x] x가 속한 집합의 대표자 찾기 Find-Set(x): if x == p[x] : return x else : return Find_Set(p[x]) Union(x, y) : 두 집합을 합친다(서로 다른 집합일 경우만) Union(x,y): if Find-Set(y) == Find-Set(x) return; p[Find-Set(y)] 특정노드에서의 루트까지의 경로를 찾아 가면.. [Algorithm] 큐 활용 - 마이쮸 큐 java.util.Queue LinkedList 클래스를 Queue 인터페이스의 구현체로 많이 사용 offer poll isEmpty size 마이쮸 문제 import java.util.LinkedList; import java.util.Queue; public class Solution { public static void main(String[] args) { // 마이쮸 나눠주기 시뮬레이션 //1번이 줄을 선다 //1번이 한개의 마이쮸를 받는다 //1번이 다시 줄을 선다 //새로 2번이 줄을 선다 //1번이 두개의 마이쮸를 받는다 //1번이 다시 줄을 선다 //새로 3번이 들어와 줄을 선다 //2번이 한개의 마이쮸를 받는다 //2번이 다시 줄을 선다 //새로 4번이 들어와 줄을 선다 //1번이 .. [Algorithm] 스택 활용 - 계산기, 브라우저 스택 java.util.Stack push pop peek isEmpty size 계산기 문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다. 문자열 수식 계산의 일반적인 방법 중위 표기법의 수식을 후위 표기법으로 변경한다. (스택 이용) 후위 표기법의 수식을 스택을 이용하여 계산한다. 피연산자를 만나면 스택에 push. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산 결과를 다시 스택에 push. 수식이 끝나면, 마지막으로 스택을 pop하여 출력. e.g. (6 + ((5 * (2-8))/2)) -> 6528-*2/+ -> 65(-6)*2/+ -> 6(-30)2/+ -> 6(-15)+ -> -9 브라우저 웹 브라우저에서 앞으로가기, 뒤로가기를.. [Algorithm] 완전탐색 - 부분 집합 부분 집합 - 집합에 포함된 원소들을 선택하는 것 - 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다. - 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다. e.g. {1,2,3} 집합의 Power Set 생성 반복문 사용 // 1 : 선택 0 : 비선택 for i in 1 -> 0 selected[1] 0 selected[2] 0 selected[3] 3// 생성된 부분집합 출력 if selected[i 1 then print i 재귀 사용 input[]// 숫자 배열 isSelected[] // 부분집합에 속하는지 여부를 저장한 배열 // cnt : 현재까지 처리한 원소 갯수 generateSubSet(cnt) if (.. [Algorithm] 완전탐색 - 순열, 조합 활용 앞에서 배운 개념을 활용하여 주사위를 던졌을 때, 모드(순열, 조합, 중복순열, 중복조합) 선택으로 원하는 결과값을 도출해보는 코드를 작성해 보았다. import java.util.Arrays; import java.util.Scanner; public class Solution { static int N, totalCnt; static int[] numbers; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); numbers = new int[N]; // 던져진 주사위 눈의 수 int M = sc.nextInt(); // 던지기 모드(1~4) switch(M) { case 1: //.. [Algorithm] 완전탐색 - 순열, 조합 순열 e.g. {1,2,3}을 포함하는 모든 순열을 생성 방법 1) 반복문 이용 ⅰ) 1 ~ 3 까지의 수 선택 시도 ⅱ) 기존에 선택된 수 비교, 중복인 경우는 skip (처음엔 생략) ⅲ) ⅰ,ⅱ를 반복 for i from 1 to 3// 1 ~ 3 까지 수 선택 시도 for j from 1 to 3// 1 ~ 3 까지 수 선택 시도 if j!= i then// 기존에 선택된 수 비교, 중복인 경우 skip for k from 1 to 3 if k!= i and k != j then print i,j,k end if end for end if end for end for 주의) 크기가 가변적인 순열은 반복문으로 구현 불가능 (재귀로 구현) 방법 2) 재귀 이용 numbers[]// 순열 저장 배열 i.. Dynamic Programming 다이나믹 프로그래밍은 동적 계획법이라고 표현하기도 한다. 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다. 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법이다. 1. 재귀 함수 예시 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1 피보나치 함수를 구현하기 위해 가장 쉬운 방법으로 재귀 함수를 사용하면 된다. def fibo(x): if x == 1 or x == 2: return 1 return fibo(.. Binary Search 이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때, 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 이진 탐색은 위치를 나타내기 위해 시작점, 끝점, 중간점 변수를 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다. 1. 이진 탐색 방법 위에 정렬된 데이터 15개에서 76의 데이터를 찾는다고 해보자. step 1. 시작점은 [0], 끝점은 [14], 중간점은 [7]이다. 중간점에 위치한 데이터 47은 찾으려는 데이터 76보다 작으므로 47 이하의 데이터는 볼 필요가 없다. 따라서 시작점을 [8]로 변경한다. step 2. 시작점은 [8], 끝점은 [14], 중간점은 [11]이다. 중간점에 위치한 데이터 77은 찾으려는 데.. Sort (Selection, Insertion, Quick, Count) 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것을 말한다. 선택 정렬 (Selection Sort) 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정이다. 1. [7] 5 9 (0) 3 1 6 2 4 8 #가장 작은 0을 선택해 맨 앞에 있는 7과 바꾼다. 2. 0 [5] 9 7 3 (1) 6 2 4 8 #정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 1을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 5와 바꾼다. 3. 0 1 [9] 7 3 5 6 (2) 4 8 #정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 2을 .. Greedy Algorithm 그리디(Greedy) 알고리즘은 '당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘'이다. 그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. 또한 '특정한 상황'에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수도 있다. 그리디 알고리즘의 대표적인 예는 거스름 돈 문제이다. 853원의 거스름돈을 주어야 할 때 1원짜리 853개를 주는 것보다 500원 1개, 100원 3개, 50원 1개, 1원 3개를 주는 것이 더 효율적이다. 따라서 이런 경우 '무조건 더 큰 화폐 단위부터 거슬러 준다'는 알고리즘을 사용하면 최적의 해를 보장할 수 있다. 그리디 알고리즘은 무조건 큰 경우, 작은 경우, 긴 경우, 짧은 경우와 같이 극단.. 이전 1 2 다음
