알고리즘

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net > 의식의 흐름 수열의 크기가 최대 1,000이니까 O(N^2) 가능하겠넹..? 그럼 전체 다 훑어봐야지~ > 풀이 과정 1. 수열의 크기(N)을 입력 받는다. 2. 수열을 배열(nums)에 입력받고 수열의 길이를 저장하는 배열(arrCnt)를 1로 초기화한다. 3. nums[i]와 뒤쪽 수(nums[j])를 비교한다 - 만약 nums[i] arrCnt[i]+1인 경우, 가장 긴 수열을..

2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net > 의식의 흐름 이전에 풀었던 행복 유치원이랑 비슷한 문제 같은데,, 센서 위치 정렬만 중간에 추가하면 될 것 같다. > 풀이 과정 1. 센서의 개수(N), 집중국의 개수(K)를 입력 받는다. 2. 센서의 위치를 배열(sensors)에 저장한다. 3. 센서의 위치를 오름차순으로 정렬한다. 행복 유치원에서는 학생의 키가 정렬된 순서로 주어졌기 때문에 따로 오름차순 정렬을 하지 않았다. 4. 옆 센서와의 거리를 배열(gap)에 저장한다. 5..

13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net > 의식의 흐름 dfs를 써서 모든 경우에 대해 비용을 구하고 그 중 최소를 뽑으면 되지 않을까? => 시간초과 옆 사람과의 키 차이가 얼마인지 구한 뒤에 차이가 큰 부분을 잘라서 조로 나눠버리면 될 것 같은데..? => 성공 > 풀이 과정 1. 원생의 수(N), 조의 개수(K)를 입력 받는다. 2. 모든 원생의 키를 배열(heights)에 저장한다. 3. 옆 원생과의 키 차이를 배열(gap)에 저장한다. 4. 배열 gap을 오름차순으로 정렬한 후 `N-K`..

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net > 의식의 흐름 연산자가 +, -만으로 이루어져 있으니까 -를 기준으로 각각의 합을 구해서 빼면 최소가 나오지 않을까.. > 풀이 과정 1. 식을 입력 받는다. 2. i번째 문자(ch)가 숫자인지 아닌지 판단한다. 숫자인 경우 num에 담아둔다. num *= 10; num += Integer.parseInt(Character.toString(ch)); 문자인 경우 '-' 전까지 나온 수들의 합을 구한 후 deque에 담아둔다. 3. 문자열 길이만큼 2번 반..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net > 의식의 흐름 트리 만들구 후위 순회하면 되겠징,,, > 풀이 과정 1. 첫번째 입력값을 루트노드로 지정한다. 2. 이후 입력값들에 대해 루트노드를 기준으로 트리를 생성한다. 왼쪽, 오른쪽 Node를 담는 Node 클래스 이용 3. 입력 없을 때까지 2번 과정 반복한다. while((input=br.readLine()) != null && !input.isEmpty()){ // 2번 과정 } 4. 후위 순회 후 결과 출력한다. 후위 순회 시, 왼쪽..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net > 의식의 흐름 > 풀이 과정 > 코드 import java.io.*; import java.util.StringTokenizer; public class Main { public static int N; // 노드의 개수 public static Node[] nodes; public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public stat..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net > 의식의 흐름 > 풀이 과정 1. 연결된 노드 담기 2. 1번 노트부터 시작 (트리의 루트를 1이라고 정했기 때문) 3. 현재 노드(nowIdx)와 연결된 노드들의 부모 설정하기 (parents[]) 4. 2번 노드부터 부모 출력 > 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; imp..

14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net > 의식의 흐름 간선은 끊으면 어떤 경우여도 그래프가 2개로 나뉘니까 yes일거고 정점은 다른 정점 한 개랑 연결된 애만 아니면 되겠지..? > 풀이 과정 1. 각 정점에 대해 연결된 정점 번호를 담을 ArrayList 생성 ArrayList links = new ArrayList(); for(int i=0;i 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import..

7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net > 의식의 흐름 시간 제한이 6초인 것을 보고 시간이 너무 널널한데? 생각했다가 T(테스트케이스의 수) 범위가 없는 것을 보고 PriorityQueue 2개를 쓰면 위험할 수도 있겠다는 생각을 했다. PriorityQueue 하나만 쓰는 방법을 생각하다가 TreeSet + PriorityQueue -> TreeMap 순으로 코드를 계속 수정했다,, > 시간복잡도 # PriorityQueue - 삽입, 삭제 : O(logN) # Treemap - 삽입, 삭제 ..