Coding test
: 큰 문제를 나누어서 풀고, 그 결과를 조합해서 문제를 해결하는 알고리즘 기법. - 분할 (Divide) : 해결할 문제를 여러개의 작은 문제로 나눈다. - 정복 (Conquer) : 작은 단위의 문제를 해결한다. - 조합 (Merge or Combine) : 해결한 작은 단위 문제들을 합해 원래 문제의 답을 구한다. 1. 하노이의 탑 : 세 개의 기둥과 기둥에 꽂을 수 있는 서로 다른 크기의 원반이 있다. 전부 하나의 기둥에 큰 것이 아래에 있도록 꽂혀있다. - 한 번에 하나의 원반만 옮길 수 있다. - 가장 위의 원반만 옮길 수 있다. - 큰 원반이 작은 원반 위에 놓여서는 안된다. - 위의 규칙을 지키면서 하나의 기둥에서 다른 기둥으로 모든 원반을 옮긴다면? 1) 원반이 두 개인 경우 : 3회 2..
- 특수한 형태의 완전 이진 트리 1. Heap - 완전 이진 트리의 어떤 노드 C와 부모 노드 P가 있을 때 C의 값보다 P의 값이 항상 크거나 / C의 값보다 P의 값이 항상 작을 때. - 다양한 요소를 가지고 있는 집합에 대하여 가장 큰 값이나 가장 작은 값을 찾기 용이함. - 우선순위 큐를 만드는데 유용하게 사용됨. 1) 힙 삽입 연산 - 제일 오른쪽 아래에 원소를 삽입 - 새로 삽입한 원소를 부모 노드와 비교 (힙의 조건을 만족시키지 못하게 배치된 경우 서로 교환) - 새로 추가한 원소가 루트 원소가 되거나, 힙의 조건을 만족시킬 때까지 반복 2) 힙 삭제 연산 - 힙의 루트 원소를 제거 - 루트 원소의 위치에 힙의 마지막 원소를 배치 (완전 이진트리 조건) 2. Heap Sort : Heap의..
- 원소들 간에 1:N 관계를 가지는 비선형 자료구조 - 상위 원소와 하위 원소의 관계가 있는 계층적 자료구조 1. 정의 : 한 개 이상의 노드로 이루어진 유한 집합. - 노드/정점 : 각각 데이터를 담고 있는 원소 - 루트 노드 : 노드 중 최상위 노드 - 각 노드는 0개 이상의 자식 노드를 가질 수 있음. - 하나의 부모에 여러 자식이 연결 - 하나의 자식은 둘 이상의 부모 X - 노드의 갯수가 N개일 때, N-1개의 간선을 가지고 있음. -> 그래서 순환 구조가 생기지 않음. (cf. Graph는 순환 구조가 있음.) - 형제 노드 : 같은 부모 노드를 가진 자식 노드들 - 조상 노드 : 간선을 따라 루트 노드까지 가는 경로의 모든 노드들 - 차수 (Degree) : 노드에 연결된 자식 노드의 수 ..
* 시간 제한이 매우 짧다 0.5초 * M개 중에서 N개를 조합하는 문제 (nCr) * 조합의 경우의 수 구하기..! 오~~ 저번에 봤던 거 같은데 하면서 풀었다. 그런데 시간 초과가 계속 떴다. 이유가 있었지 암... 첫번째 풀이) (바보풀이임 따라하지 마셈) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; //다리 놓기 실버5 public class Main { public static void main(String[] args) throws IOException { //테스트 케이스의 수 T BufferedReader br..
다이나믹 프로그래밍이란? : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 > 여러 개의 하위 문제로 나누어 풀고 저장한다. 그것을 결합하여 최종적인 목적에 도달한다. > 나중에 같은 하위 문제가 나왔을 경우 간단히 해결 가능하고, 계산 횟수를 줄일 수 있다. 1) 최적 부분 구조 : 큰 문제의 최적해가 작은 문제의 최적해를 포함해야 한다. 그래야 작은 문제의 최적해를 구한다음 그것을 활용하여 큰 문제의 최적해를 구할 수 있으니까~~ 2) 중복 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다. ex. 피보나치 수열 ~> 0과 1로 시작하고 이전의 두수 합을 다음 항으로 하는 수열. (n은 자연수) fib(0) = 0, fib(1) = 1 ver 1. 재귀함수 public static..
정렬 문제여서 간단하게 생각했다. 간단하게 Arrays.sort()를 쓰면 되지 않을까 하고 풀어보았다. 고민했던 점은 1) 멘토-멘티 순서쌍을 어떤 식으로 표현할지 2) 비교를 어떤 방법으로 표현할지 였다. 첫번째 풀이는 1) String[][] 2차원 배열에 저장하는 것이었다. 2) 비교는 Arrays.sort(람다식) 사용. >> 코드는 이런식으로 나왔다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; // 멘토와 멘티 실버5 public class Main { public static void main(String[] args) thr..
머리가 안돌아가여.... 막 맵에다 넣고 난리난리 치다가... 왜그랬지 ㅠㅠ 그냥 이차원 배열에 넣으면 됐다. 그리고,,,,, 람다식을 사용하면 엄청 간단하게 해결이 된다. - 풀이 더보기 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 2차원 평면 위에 점 N개 int N = Integer.parseInt(br.readLine()); // N개의 줄에 i번점의 위치 Xi, Yi가 주어진다. // 그걸 2차원 배열로 표시하자. int[][] map = new int[N][2]..
1. Brute Force : 무작정 가능한 모든 경우를 다 검사하는 알고리즘. ex. 4자리의 숫자로 이뤄진 비밀번호를 구해야 한다.... > 0000~9999까지 모두 해본다...? 방법은 간단하다. 모든 경우의 수를 확인해 보는 것...! 그러나, 경우의 수가 늘어나기 시작하면 수행속도가 느려지기 시작한다... 그렇지만 해답을 못 찾은 가능성이 적으므로 절! 대! 모르겠으면 일단 접근해볼 수 있는 방법이다. 2. 순열 : 서로 다른 것들 중 몇 개를 뽑아서 한줄로 나열하는 것. 서로 다른 n개 중 r개를 꺼낼 때 만들 수 있는 순열의 갯수는.......? (n개 중에서 r개 고르기) - r = n인 경우 (n개 중에서 n개 고르기) > n 팩토리얼 (n!) - nPr을 팩토리얼을 이용해 표현 ~> ..
