고민의 흔적

70번 트리 순회

내가 떠올린 풀이 해설

2차원 배열에 트리 데이터를 저장한다. 저장할 때 index화 하여 저장한다. 전위 순회 함수를 구현해 실행한다. 중위 순회, 후위 순회도 같은 과정으로 구현한다.

전위 순회 순서

현재 노드 -> 왼쪽 노드 -> 오른쪽 노드

중위 순회 순서

왼쪽 노드 -> 현재 노드 -> 오른쪽 노드

후위 순회 순서

왼쪽 노드 -> 오른쪽 노드 -> 현재 노드

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1991 {
	static int[][] tree;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		tree = new int[26][2];
		for(int i = 0; i < n; i++) {
			String[] str = br.readLine().split(" ");
			int node = str[0].charAt(0) - 'A';
			char left = str[1].charAt(0);
			char right = str[2].charAt(0);
			
			if(left == '.') {
				tree[node][0] = -1; 
			}
			else {
				tree[node][0] = left - 'A';
			}
			if(right == '.') {
				tree[node][1] = -1;
			}
			else {
				tree[node][1] = right - 'A';
			}
		}
		preOrder(0);
		System.out.println();
		inOrder(0);
		System.out.println();
		postOrder(0);
		System.out.println();
	}
	private static void postOrder(int now) {
		if(now == -1) {
			return;
		}
		postOrder(tree[now][0]);
		postOrder(tree[now][1]);
		System.out.print((char)(now + 'A'));
	}
	private static void inOrder(int now) {
		if(now == -1) {
			return;
		}
		inOrder(tree[now][0]);
		System.out.print((char)(now + 'A'));
		inOrder(tree[now][1]);
	}
	private static void preOrder(int now) {
		if(now == -1) {
			return;
		}
		System.out.print((char)(now + 'A'));
		preOrder(tree[now][0]);
		preOrder(tree[now][1]);
	}
}

오늘의 회고

오늘은 이진 트리 한 문제를 풀었습니다. 주어진 자료구조 형태만 충실히 구현하면 되는 문제라고 나와있었는데 많이 헤맸습니다. 이제 앞으로 배워야 할 알고리즘이 세그먼트 트리, 최소 공통 조상, 조합, 동적 계획법(DP) 4개가 남았는데 이 책을 끝내면 이제 단원별이 아닌 무작위로 문제를 뽑아서 풀 생각입니다. 그동안 배웠던 알고리즘으로 응용을 해서 풀어야 되는데 걱정이 되네요 꾸준히 하다 보면 목표에 도달할 것이라고 생각합니다. 꾸준히 열심히 하겠습니다.

최소 신장 트리

최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.

최소 신장 트리의 특징

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 수는 항상 N - 1개다.

최소 신장 트리 핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기

   최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다. edge class는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다. 사이클 처리를 위한 유니온 파인드 배열도 함께 초기화한다. 배열의 인덱스를 해당 자리의 값으로 초기화하면 된다.

2. 그래프 데이터를 가중치 기준으로 정렬하기

   에지 리스트의 담긴 그래프를 데이터를 가중치 기준으로 오름차순 정렬한다.

3. 가중치가 낮은 에지부터 연결 시도하기

   가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다. 이때 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union연산을 이용해 두 노드를 연결한다.

4. 과정 3 반복하기

   전체 노드의 개수가 N개이면 연결한 에지의 개수가 N - 1이 될 때까지 과정 3을 반복한다.

5. 총 에지 비용 출력하기

   에지의 개수가 N - 1이 되면 알고리즘을 종료하고, 완성된 최소 신장 트리의 총 에지 비용을 출력한다. 최소 신장 트리는 다른 그래프 알고리즘과 달리, 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있다. 그 이유는 에지를 기준으로 하는 알고리즘이기 때문이다. 또한 사이클이 존재하면 안 되는 특징을 지니고 있기 때문에 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 된다.

코드로 표현

static int[] parent;
static PriorityQueue<pEdge> que;

노드 수, 에지 수 입력
que = new PriorityQueue<>();  // 자동 정렬을 위해 우선순위 큐 자료구조 선택하기

parent = new int[n + 1];
parent배열 인덱스로 초기화

for(int i = 0; i < M; i++) {
	시작 노드 s, 끝 노드 e, 가중치 입력받기 v
    que.add(new pEdge(s,e, v));
}
int useEdge = 0;
int result = 0;
while(useEdge < N - 1) {
	pEdge now = que.poll();
    if(find(now.s) != find(now.e)) {  // 같은 부모가 아니라면 연결해도 사이클이 생기지 않음
    	union(now.s, now.e);
        result = result + now.v;
        useEdge++;
    }
}
Union 연산 : 대표 노드끼리 연결하기
a = find(a);
b = find(b);
if(a != b) {
	parent[b] = a;
}
Find 연산
if(a == parent[a]) {
	return a;
}
else {
	return parent[a] = find(parent[a]); // 경로압축
}

class pEdge implements Comparable<pEdge> {
	int s;
    int e;
    int v;
    pEdge(int s, int e, int v) {
    	this.s = s;
        this.e = e;
        this.v = v;
    }
    @Override
    public int compareTo(pEdge o) {
    	// 가중치를 기준으로 오름차순 정렬을 하기 위해 compareTo 재정의하기
    	return this.v - o.v;
    }
}

69번 문자열 집합

내가 떠올린 풀이 해설

집합 S에 속해있는 단어들을 이용해 트라이 구조를 생성하고, 트라이 검색을 이용해 문자열 M개의 포함 여부를 카운트하는 전형적인 트라이 자료구조 문제이다. 트라이 자료구조를 생성하고 현재 문자열을 가리키는 위치의 노드가 공백 상태라면 신규 노드를 생성하고 아니라면 이동한다. 문자열 마지막에 도달하면 리프 노드라고 표시한다. 트라이 자료구조 검색으로 집합 S에 포함된 문자열을 센다. 부모-자식 관계를 이용해 대상 문자열을 검색했을 때 문자열이 끝날 때까지 공백 상태가 없고, 현재 문자의 마지막 노드가 트라이의 리프 노드라면 이 문자를 집합 S에 포함된 문자열로 센다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek14425 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		dNode root = new dNode();
		while(n > 0) { // 트라이 자료구조 구축하기 
			String text = br.readLine();
			dNode now = root;
			for(int i = 0; i < text.length(); i++) {
				char c = text.charAt(i);
				// 26개 알파벳의 위치를 배열 index로 나타내기 위해 -'a' 수행하기 
				if(now.next[c - 'a'] == null) {
					now.next[c - 'a'] = new dNode();
 				}
				now = now.next[c - 'a'];
				if(i == text.length() - 1) {
					now.isEnd = true;
				}
			}
			n--;
		}
		int count = 0;
		while(m > 0) {    // 트라이 자료구조 검색하기 
			String text = br.readLine();
			dNode now = root;
			for(int i = 0; i < text.length(); i++) {
				char c = text.charAt(i);
				if(now.next[c - 'a'] == null) { // 공백 노드라면 이 문자열을 포함하지 않음 
					break;
				}
				now = now.next[c - 'a'];
				if(i == text.length() - 1 && now.isEnd) { // 문자열의 끝이고 현재까지 모두 일치하면 
					count++;   // S 집합에 포함되는 문자열 
				}
			}
			m--;
		}
		System.out.println(count);
	}

}
class dNode {
	dNode[] next = new dNode[26];
	boolean isEnd;  // 문자열의 마지막 유무를 표시하기 
}

오늘의 회고

오늘은 트라이 자료구조를 배우고 트라이 문제를 풀었습니다. 1문제 밖에 풀지 못했습니다. 장마라 밖에 비도 많이 오고 날씨도 우중충한데 퍼지지 않고 공부하겠습니다.

67번 트리의 부모 찾기

내가 떠올린 풀이 해설

인접 리스트 자료구조를 사용하면 간편하게 데이터를 저장할 수 있다. 트리의 루트가 1이라고 지정돼 있기 때문에 1번 노드부터 DFS로 탐색하면서 부모 노드를 찾아 주면 문제를 쉽게 풀 수 있다. 출력은 정답 배열의 2번 인덱스부터 값을 차례대로 출력한다.

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek11725 {
	static ArrayList<Integer>[] arr;
	static int[] answer;
	static boolean[] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n + 1];
		visit = new boolean[n + 1];
		answer = new int[n + 1];
		
		for(int i = 0; i <= n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		for(int i = 1; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			arr[s].add(e);
			arr[e].add(s);
		}
		DFS(1);
		for(int i = 2; i <= n; i++) {
			System.out.println(answer[i]);
		}
	}
	private static void DFS(int i) {
		visit[i] = true;
		for(int k : arr[i]) {
			if(!visit[k]) {
				answer[k] = i;
				DFS(k);
			}
		}
	}
}

68번 트리

내가 떠올린 풀이 해설

이 문제의 핵심은 리프 노드를 어떻게 제거하는지 이다. 리프 노드를 탐색하는 탐색 알고리즘을 수행할 때나 제거하는 노드가 나왔을 때 탐색을 종료하는 아이디어를 적용하면 실제 리프 노드를 제거하는 효과를 낼 수 있다. 인접 리스트로 트리 데이터를 구현한다. DFS를 탐색하면서 리프 노드의 개수를 센다. 제거 대상 노드를 만났을 때 그 아래 자식 노드들과 관련된 탐색은 중지한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1068 {
	static ArrayList<Integer>[] arr;
	static boolean[] visit;
	static int r;
	static int answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n];
		visit = new boolean[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = new ArrayList<>();
		}
		int root = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			int s = Integer.parseInt(st.nextToken());
			if(s != -1) {
				arr[s].add(i);
				arr[i].add(s);
			}
			else {
				root = i;
			}
		}
		r = Integer.parseInt(br.readLine());
		if(r == root) {
			System.out.println(0);
		}
		else {
			DFS(root);
			System.out.println(answer);
		}
	}
	private static void DFS(int root) {
		visit[root] = true;
		int c = 0;
		for(int v : arr[root]) {
			if(!visit[v] && v != r) { // 삭제 노드가 아닐 떼도 탐색 중지 
				c++;
				DFS(v);
			}
		}
		if(c == 0) {
			answer++; // 자식 노드가 아닐 때 리프 노드로 간주하고 정답값 증가 
		}
	}
}

오늘의 회고

오늘은 트리와 관련된 문제 2문제를 풀었습니다. 알고리즘 개념에 대해 복습하는 시간을 가지면서 초반보다 문제를 푸는 개수가 많이 줄어들어 시간도 부족하고 알고리즘을 끝낼 수 있을까란 조바심도 들지만 천천히 조바심 가지지 않고 완전히 내 것으로 만들면서 나아가겠습니다.

유니온 파인드

유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

유니온 파인드 핵심 이론

union, find 연산

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다.
• find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다.

유니온 파인드 원리 이해

유니온 파인드를 표현하는 일반적인 방식은 1차원 배열을 이용하는 것이다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화한다. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다. 배열을 보면 1, 4와 5, 6을 union연산으로 연결한다. 배열[4]은 1로, 배열[6]은 5로 업데이트한다. 1, 4의 연결을 예로 들어 1은 대표 노드, 4는 자식 노드로 union 연산을 하므로 배열[4]의 대표 노드를 1로 설정한 것이다. 다시 말해 자식 노드로 들어가는 노드 값 4를 대표 노드 값 1로 변경한 것이다. 그 결과 각각 집합이었던 1, 4는 하나로 합쳐진다. find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산이다. find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상한다.

find 연산의 작동 원리

1. 대상 노드 배열에 index값과 value값이 동일한지 확인
2. 동일하지 않으면 value값이 가리키는 index위치로 이동
3. 이동 위치의 index값과 value값이 같을 때까지 1, 2를 반복한다. 반복이므로 재귀 함수로 구현
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드 값을 루트 노드 값으로 변경한다.

코드로 표현

private static void union(int s, int e) {
	s = find(s);
	e = find(e);
    if(s != e) {
		parent[e] = s;
	}
}
private static int find(int s) {
	if(s == parent[s]) {
		return s;
	}
	else {
		return parent[s] = find(parent[s]);
	}
}

64번 최소 스패닝 트리

내가 떠올린 풀이 해설

에지 리스트에 에지 정보를 저장한 후 부모 노드를 초기화한다. 사이클 생성 유무를 판단하기 위한 파인드용 부모 노드도 초기화한다. 크루스칼 알고리즘을 수행한다. 현재 미사용 에지 중 가중치가 가장 작은 에지를 선택하고, 이 에지를 연결했을 때 사이클의 발생 유무를 판단한다. 사이클이 발생하면 생략하고, 발생하지 않으면 에지 값을 더한다. 에지를 더한 횟수가 V(노드 개수) - 1 이 될 때까지 반복하고, 반복이 끝나면 에지의 가중치를 모두 더한 값을 출력한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1197 {
	static PriorityQueue<pEdge> que;
	static int[] parent;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		parent = new int[n + 1];
		que = new PriorityQueue<>();
		for(int i = 0; i < n; i++) {
			parent[i] = i;
		}
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			que.add(new pEdge(a, b, c));
		}
		int useEdge = 0;
		int result = 0;
		while(useEdge < n - 1) {
			pEdge now = que.poll();
			if(find(now.a) != find(now.b)) {   // 같은 부모가 아니라면 연결해도 사이클이 생기지 않음 
				union(now.a, now.b);
				result = result + now.c;
				useEdge++;
			}
		}
		System.out.println(result);
	}
	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
		}
	}
	private static int find(int a) {
		if(a == parent[a]) {
			return a;
		}
		else {
			return parent[a] = find(parent[a]);
		}
	}
}
class pEdge implements Comparable<pEdge>{
	int a;
	int b;
	int c;
	public pEdge(int a, int b, int c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}
	@Override
	public int compareTo(pEdge o) {
		return this.c - o.c;
	}
}

66번 블우이웃 돕기

내가 떠올린 풀이 해설

인접 행렬의 형태로 데이터가 들어오기 때문에 이 부분을 최소 신장 트리가 가능한 형태로 변형하는 것이 이 문제의 핵심이다. 먼저 문자열로 주어진 랜선의 길이를 숫자로 변형해 랜선의 총합을 저장한다. 이때 i와 j가 같은 곳의 값은 같은 컴퓨터를 연결한다는 의미이므로 별도 에지로 저장하지 않고 나머지 위치의 값들을 i -> j로 가는 에지로 생성하고, 에지 리스트에 저장하면 최소 신장 트리로 변형할 수 있다.

입력 데이터의 정보를 배열에 저장한다. 먼저 입력으로 주어진 문자열을 숫자로 변환해 총합으로 저장한다. 소문자는 현재 문자 - 'a' + 1, 대문자는 현재 문자 - 'A' + 27 변환한다. i와 j가 다른 경우에는 다른 컴퓨터를 연결하는 랜선이므로 에지리스트에 저장한다. 저장된 에지 리스트를 바탕으로 최소 신장 트리 알고리즘을 수행한다. 최소 신장 트리의 결괏값이 다솜이가 최소한으로 필요한 렌선의 길이이므로 처음 저장해 둔 랜선의 총합에서 최소 신장 트리의 결괏값을 뺀 값을 정답으로 출력한다. 최소 신장 트리에서 사용한 에지 개수가 n - 1이 아닌 경우에는 모든 컴퓨터를 연결할 수 없다는 의미이므로 -1을 출력한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1414 {
	static int n, sum;
	static PriorityQueue<lEdge> que;
	static int[] parent;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		que = new PriorityQueue<>();
		
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			char[] tmpc = st.nextToken().toCharArray();
			for(int j = 0; j < n; j++) {
				int tmp = 0;
				if(tmpc[j] >= 'a' && tmpc[j] <= 'z') {
					tmp = tmpc[j] - 'a' + 1;
				}
				else if(tmpc[j] >= 'A' && tmpc[j] <= 'Z') {
					tmp = tmpc[j] - 'A' + 27;
				}
				sum = sum + tmp;
				if(i != j && tmp != 0) {
					que.add(new lEdge(i, j, tmp));
				}
			}
		}
		parent = new int[n];
		for(int i = 0; i < n; i++) {
			parent[i] = i;
		}
		int useEdge = 0;
		int result = 0;
		while(!que.isEmpty()) {
			lEdge now = que.poll();
			if(find(now.s) != find(now.e)) {
				union(now.s, now.e);
				result = result + now.v;
				useEdge++;
			}
		}
		if(useEdge == n - 1) {
			System.out.println(sum - result);
		}
		else {
			System.out.println(-1);
		}
	}
	private static void union(int s, int e) {
		s = find(s);
		e = find(e);
		if(s != e) {
			parent[e] = s;
		}
	}
	private static int find(int s) {
		if(s == parent[s]) {
			return s;
		}
		else {
			return parent[s] = find(parent[s]);
		}
	}
}
class lEdge implements Comparable<lEdge> {
	int s;
	int e;
	int v;
	public lEdge(int s, int e, int v) {
		this.s = s;
		this.e = e;
		this.v = v;
	}
	@Override
	public int compareTo(lEdge o) {
		return this.v - o.v;
	}
	
}

오늘의 회고

오늘은 최소 신장 트리 문제 2문제를 풀었습니다. 코드를 구현하는데 어려웠습니다. 반복해서 제가 직접 구현할 수 있게 만들겠습니다. 오늘 날씨가 너무 더운데 모든 취준생분들 화이팅입니다. 열심히 나아가겠습니다. 모두 화이팅입니다.

그리디

그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상 최적의 해를 보장하지 못한다는 단점도 있다.

그리디 알고리즘 핵심 이론

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

이진 탐색

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

이진 탐색 핵심 이론

1.  현재 데이터셋의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1 ~ 3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

시간복잡도

O(logN)

코드 예시

int start = 0;
int end = arr.length - 1;
while(start <= end) {
	int mid = (start + end) / 2;
    int midv = arr[mid];
    if(midv > target) {
    	end = mid - 1;   // 핵심 : 중간값이 찾고자하는 값보다 크면 end를 바꿈
    } 
    else if (midv < target) {
    	start = mid + 1;  // 핵심 : 중간값이 찾고자하는 값보다 작으면 start를 바꿈
    }
}