NEVER·THE·LESS

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net A가 루트인 이진 트리가 주어집니다. 이 트리를 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 문제입니다. 💎 트리 표현 방법 static class Node를 선언했습니다. 현재 노트의 알파벳 값인 value, 왼쪽, 오른쪽 노드인 left, right를 멤버 변수로 가지..

Thread 생성하기 Thread를 생성하는 방법에는 크게 두가지가 있습니다. Thread 클래스를 상속받는 것과, Runnable 인터페이스를 구현하는 것입니다. 1. Thread 클래스 class MyThread extends Thread { int num; MyThread(int num) { this.num = num; } @Override public void run() { System.out.println("# "+ num + " thread is running"); } } public static void main(String[] args) throws InterruptedException { for(int i=0; i

https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 자연수로 이루어진 집합에서 세 수 a, b, c, d를 뽑았을 때, a+b+c=d를 만족하는 최대 d를 구하는 문제입니다. 모든 경우의 수를 따져서 풀 수 있는데, 이럴 경우 N이 최대 1,000이기 때문에 N^3은 1,000,000,000으로 시간초과가 될 것입니다. 💎 풀이 a+b+c=d 우리가 성립시켜야 할 식입니다. 이 식을 이항해보면 a+b..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int n, m; static ArrayList q = new ArrayList(); public static void main(String[] ..

투 포인터 (Two Pointers) 투 포인터 알고리즘은 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻어내는 알고리즘입니다. 🎈 예제 길이가 n인 1차원 배열이 있을 때, 그 부분 배열의 원소의 합이 m이 되는 경우의 수를 알고 싶습니다. 모든 부분 배열을 탐색한다면 시간복잡도는 O(n^2)이 되겠습니다. 그러나 투 포인터를 사용하면 O(n) 에 문제를 해결할 수 있습니다. 포인터 2개를 만듭니다. start, end라고 하겠습니다. 처음 시작할 때는 start, end = 0 입니다. start = m) { start++; // start를 오른쪽으로 옮김 sum -= arr[start]; } else if (end == n) { break; } else { end++; // end를 ..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; static int maxLength = 0; static int[] check = new int[26]; // 알파벳 몇번 나왔는지 기록 public static void main..

https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1

Next Permutation 시간 복잡도 O(n) 어떠한 순열의 다음 순열을 구하는 알고리즘입니다. 예제로 알아봅시다. 이 수열의 다음 수열을 구하려고 합니다. 처음 떠오르는 방법은 2, 3, 4, 5, 7을 나열해서 만들 수 있는 순열을 모두 구해서 2, 5, 7, 4, 3의 다음 순열을 알아내는 방법입니다. 이 방법은 너무 비효율적일 것입니다.. next permutation 알고리즘으로 O(n)의 시간복잡도로 다음 순열을 구할 수 있습니다. 1) 뒤에서부터 탐색하면서, 처음으로 *감소하는* 부분의 인덱스를 구합니다. 예제에서는 array[1] == 5 입니다. 이 인덱스를 편의상 i라고 칭하겠습니다. 2) 다시 뒤에서부터 탐색하면서, '감소하는 부분'보다 큰 값을 가진 인덱스를 구합니다. 예제에서..