Algorithm Cinema

이런 서로 다른 트리들을 비교할때 어케해야할까의 고민두 집합에 속한 원소들은 중복되지 않고, 순서도 특정된게 없으니 1차원배열에 싹 다 저장한다.모든 집합의 원소 즉, 서로 다른 트리들의 원소를 0,1,2…,n-1로 넣으면 이를 1차원배열의 인덱스로 활용한다.이런 서로 다른 트리들을 비교할때 어케해야할까의 고민두 집합에 속한 원소들은 중복되지 않고, 순서도 특정된게 없으니 1차원배열에 싹 다 저장한다.모든 집합의 원소 즉, 서로 다른 트리들의 원소를 0,1,2…,n-1로 넣으면 이를 1차원배열의 인덱스로 활용한다.트리의 루트는 각 집합의 대표이다.루트의 배열 원소에는 루트 자식을 넣는다. ( 루트와 루트 자식은 같은 인덱스값)루트가 아닌 노드의 원소는 그 원소의 부모노드( 루트 아래아래 자식의 인덱스값은..

Comparable인터페이스. 가지고 있는 메서드는 CompareTo()import 필요없다. java.lang에 위치해있기 때문.이러한 비교하는 인터페이스를 가져오는건 궁극적으로 비교도 있지만 정렬의 기준을 세우는 것이다.return 값은 0,1,-1이얌.class Student implements Comparable{..... 생성자, getter setter.... public int CompareTo(Student s){ return this.id-s.id; } //아니 그럼 이름과 같은 문자일땐 어떻게 비교하나요? //이런식으로 comapreTo내부에 compareTo를 써서 정렬의 기준을 잡아주면 됩니다. public int CompareTo(Student s){ return this...

차근차근 여러가지 자료 구조들을  하나씩 소개해볼까 한다. 우선순위 큐?우선순위 큐(priority queue)는 자료 구조의 한 종류로서, 큐(queue)와 트리(tree) 두 개념 모두와 관련이 있다. 구체적으로 설명하자면: 큐와의 관계큐(queue)는 FIFO(First In, First Out) 방식으로 작동하는 자료 구조다. 즉, 먼저 들어온 요소가 먼저 나가는 구조인데 .우선순위 큐는 큐의 특수한 형태로, 각 요소가 우선순위를 가지며, 요소가 들어온 순서가 아니라 우선순위에 따라 나가는 방식이다. ( 들어온 순서가 아닌 우선순위를 매기는 방식) 우선순위가 높은 요소가 먼저 나갑니다.따라서, 우선순위 큐는 큐의 개념을 확장한 것으로 볼 수 있다.트리와의 관계우선순위 큐는 내부적으로 다양한 자료 ..

6588번: 골드바흐의 추측 (acmicpc.net) 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 주어진 짝수를 소수의 합으로 표현하는 문제이다. 1. 시간 제한 0.5 매우빡시다. 일단 test case는 10만번 이하이고 짝수는 100만이하이다. 2. 가장 효율적인 알고리즘 > 에리토스테네스.. 이를 활용하고 플러스 메모이제이션을 활용해서 배열을 하나만 만들것이다. 즉, 짝수의 max범위가 100만이니 우리는 100만까지만 관찰하면 된다. 따라서 100만짜리의 크기의 소수판별 배..

1929번: 소수 구하기 (acmicpc.net) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net m 이상 n이하의 소수를 출력해야함 range는 100만 이하. 시간 제한은 2초이다. 1. 소수를 판별하는 알고리즘 뭐 냅다 i=2부터 몇까지 나머지 있으면 false이런식으로 하는것도 있지만 시간적으로 효율적이지 않아서 웬만하면 에라스토텔레스의 체라는 알고리즘을 활용한다. i=2부터 n까지가 아닌 n의 제곱근까지만 search 해도 괜찮다. public static boolean isPrime(int num) { if(num 제곱근까지만 검..

11656번: 접미사 배열 (acmicpc.net) 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다. 얘를 사전순으로. 1. 인덱싱으로 잘라서 배열에 넣은 다음 (ArrayList)활용 2. sort하면 끝날거같다. 3. 부분 문자열 >> 웬만하면 자바의 편한 substring 메소드를 활용하자 import java.io.*;..

11655번: ROT13 (acmicpc.net) 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. ROT13은 카이사르 암호의 일종으로 영어 알파벳을 13글자씩 밀어서 만든다. 1. 알파벳은 13개씩 밀어서 출력하고 나머지 알파벳이 아닌 녀석들은 그대로 출력 2. 아스키코드로 필터링하고 조건문으로 13개씩 미는것을 다뤄야한다. 당연하겠지만 알파벳은 26가지 인데, 만약 A라는 녀석은 13번째 뒤인 알파벳이 있지만 Z는 없고 그 전 껄로 돌아간다. 따라서 해당 문자..

10809번: 알파벳 찾기 (acmicpc.net) 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다. 알파벳이 나타남에 따라 문자열 내에서 처음 등장하는 위치(인덱스)를 a b c d e f .. 순으로 표기하는 알고리즘이다. ..

1918번: 후위 표기식 (acmicpc.net) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 1. 여러분의 마음을 읽어보자. A+B*C-D/E ABC*+DE/-​ 여기는 문자 뭉탱이 연산자 뭉탱이 문자 뭉탱이 연산자 뭉탱이 순으로 뭉탱이들이 다채로운 case. 아마 까다로워할 포인트는 A*(B+C) ABC+* 처럼 문자 한 뭉탱이가 나오고 연산자 뭉탱이가 나오는 case. 이 두 case가 달라서 구현을 어떻게 접근해야할지 조차 모르는 분들이 많을 것이다. 2. 문자는 그대로? 일단 문자의 순서는 변..

1935번: 후위 표기식2 (acmicpc.net) 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 후위표기식 관련 문제이다. 후위표기식은 한마디로 연산자가 뒤로 가는거다. ab+ 는 a+b abc*+de/- > (b*c)+a - (d/e) 뭐 이런느낌이다. 계산순서를 보면 알 수 있듯, 일단 스택을 활용하는게 상당히 적절해보인다. 일단 만약 알파벳이 5개의 종류대로 숫자가 순서대로 input된다는 점은 상당히 편하다. 5 ABC*+DE/- 1 2 3 4 5 이 예제를 들어 생각해보자. 1. 소수 ..