문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

https://www.acmicpc.net/problem/10610

 

10610번: 30

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한

www.acmicpc.net



1. 이해 (5분) - 1분

문제에서 제시하는 조건은 30의 배수이지만, 사실상 3의 배수라고 생각을 해도 무방합니다.

3의 배수가 갖는 특징은 자릿수의 숫자를 모두 더하면 3의 배수가 나온다는 점입니다.

3, 6, 9, 12(3), 15(6)... 10진법에서 올림연산이 발생할때 3의 경우는 무조건 1만큼이 부족하기 때문에 앞의 자릿수는 1이 오르고 자기 자릿수에선 1만큼이 부족해지면서 합이 유지되는겁니다.

  

2. 계획 (5분) - 1분

문제에선 3의 배수가 아닌 30의 배수를 요구했으므로, 최소한 한개의 0이 필요합니다.

또한 가장 큰 수를 출력하라고 했으니 각 자리의 숫자들을 내림차순으로 정렬해 출력할 필요도 있겠네요.

다만 이 모든 계산은 이렇게 만들어진 수가 30의 배수일 경우, 즉 각 자릿수의 합이 3의 배수일 때만 해주면 됩니다.


3. 검증 (5분) - 1분

예외가 발생할 경우는 0 같은 특이한 수가 입력될때일텐데요, 조건에서 숫자가 0으로 시작하지 않는다고 하니 문제되지 않을것 같습니다.

각 자리의 숫자들을 내림차순으로 정렬한 수(만들 수 있는 가장 큰 수)도 3의 배수가 맞을까요?

예시를 떠올려보면 12345이나 54321이나 전부 3의 배수입니다! 각 자릿수의 합이 3의 배수기만 하면 전부 3의 배수인게 확실합니다.


4. 풀이 (30분) - 10분

오랜만에 Python을 사용하다보니 살짝 버벅였지만 작성에 크게 어려운 부분은 없었습니다.

짧은 코드인데도 시간이 꽤 걸렸네요.


5. 채점, 디버깅 (+@)

3의 배수가 갖는 특징을 알고 Python 언어를 알면 쉽게 풀 수 있는 문제여서 한번에 통과했습니다.

문제 풀이에는 총 15분 가량이 걸렸습니다.

 

정답코드입니다.

N = list(input())
N = sorted(N, reverse=True)

if N[-1] != '0' :
    print(-1)
else:
    sum = 0
    for i in N:
        sum += int(i)
    if sum % 3 != 0 :
        print(-1)
    else :
        print(''.join(N))
728x90

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

 

 

https://www.acmicpc.net/problem/18858

 

18858번: 훈련소로 가는 날

1 이상 M 이하의 정수로 이루어진 길이 N의 수열 중 논산인 것의 개수를 998,244,353으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

1. 이해 (5분) - 3분

문제 자체는 길지 않았지만, 이해하는데는 시간이 필요했습니다.

non-산 이라는 처음 보는 단어가 있어 머릿속으로 그려보는데 조금 어려움이 있었습니다.

몇 번을 다시 읽고 문제에서 주어진 '산'이라는 개념이 잡혀 풀이를 구상했습니다.


2. 계획 (5분) - 1분

풀이방법은 간단했습니다. non-산 이 되려면, 즉 산이 없으려면 문제에서 설명하듯 A1<A2>A3 형태의 부분수열이 없어야합니다. 이 말은 즉 A1 -> A2로 갈때 가능한 3가지 경우 (A2가 A1보다 크거나, 같거나 작거나)를 두번 거치며 생기는 9가지 경우의 수 중에서 하나의 경우가 막힌다는 뜻입니다.

가능한 방법의 갯수를 구해야하므로 DP형태로 이전 단계에서 가능한 방법의 수를 가지고 다음 단계를 구합니다.

이때 초기 데이터는 이전 턴에서 변화가 없었다를 1씩 넣어주고 이 후 상승이 가능한 경우, 하강이 가능한 경우를 계산해서 다음 데이터에 넣어주는 식으로 구현했습니다.


3. 검증 (5분) - 1분

제가 구상한 풀이방법에서는 가능한 이전 상태의 수 M개의 데이터를 기억하고 이를 토대로 N번 가능한 경우의 수를 계산합니다. 따라서 연산은 대력 MN번 일어날 것이고, 문제에서 입력의 범위가 100과 1000으로 주어졌기때문에 10만번이면 충분히 시간안에 정답이 나올것이라고 생각했습니다.

메모리적인 측면에서도 딱히 문제가 생길 부분이 보이지 않았습니다.


4. 풀이 (30분) - 19분

구상한 풀이방법을 토대로 코드를 작성했습니다.

 


5. 채점, 디버깅 (+30여분)

풀이자체는 시간이 많이 걸리지 않았지만... 

구현 과정에서 반대방향으로 돌아가는 반복문과 입력 데이터가 1,2인 경우 등의 예외처리 그리고 초기 구상에서 잘못생각한 부분등을 고치면서 디버깅에 시간이 꽤나 걸렸습니다.

다행히 예제로 주어진 데이터에서 오류를 발견할 수 있어서 수정해 제출했지만 예제 데이터로 알 수 없는 오류였다면 오답인지도 모른채로 제출할 뻔 했습니다...

 

추가로 디버깅을 통해 코드를 수정하다보니 + 초기에 풀이 형태를 대충 구상

이 두가지 허술함의 콤보로 코드가 상당히 난해하고 더러워졌습니다.

추후 수정하게되면 재업로드하겠습니다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;
	static final long div = 998_244_353;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		long[][] before = new long[M + 1][3];
		long[][] now = new long[M + 1][3];

		for (int m = 1; m <= M; m++) {
			before[m][1] = 1;
		}

		long sum = 0;

		for (int n = 1; n < N; n++) {
			
			sum = 0;
			for (int m = M; m > 0; m--) {
				sum = (sum + before[m][0] + before[m][1]) % div;
				now[m-1][0] = sum;
			}
			
			sum = 0;
			now[1][1] = (before[1][0] + before[1][1] + before[1][2]) % div;
			sum = (sum + now[1][1]) % div;
			for (int m = 2; m <= M; m++) {
				now[m][2] = sum;
				now[m][1] = (before[m][0] + before[m][1] + before[m][2]) % div;
				sum = (sum + now[m][1]) % div;
			}
			
			before = now.clone();
			now = new long[M+1][3];
		}

		long answer = 0;

		for (int m = 1; m <= M; m++) {
			answer = (answer + before[m][0] + before[m][1] + before[m][2]) % div;
		}

		System.out.println(answer);
	}
}

 

 

 

 

728x90

 

오늘 싸피 5기 수료식을 진행했다!

1년간 정들었던 싸피 과정이 공식적으로 끝이 났다.

그리고 내 커리어엔 'SSAFY 5기 수료'라는 문구가 영원히 남을 것이다.

노트북과 한 번도 못써본 출입증을 반납하고서도 실감이 나지 않았는데, 수료식까지 마치니 정말로 실감이 난다.

 

수료식엔 화상회의로 참석했고, 중간중간 나와 팀원들의 모습이 보여서 반가웠다.

익숙한 프로님들, 컨설턴트님들의 얼굴도 다시 보니 감회가 새로웠다.

 

코로나로 인해 수업이 1년 내내 온라인으로 진행되어 편한 점도 있었지만, 여러모로 아쉬움이 진하게 남는다.

부디 코로나가 진정되어 6기, 7기 친구들은 오프라인에서도 수업과 팀 프로젝트를 진행할 수 있길 바란다!

 

 

 

 

 

1학기엔 12반에서 같이 수업을 듣고, 2학기엔 같이 팀프로젝트를 진행한 팀원 여러분, 즐거웠고 고마웠어! 

 

 

PS.

싸피 수료하면 갤럭시 플립을 준다는 헛소문이 인터넷에서 돌던데...

수료식에서 우수학생들에게 장관상, 삼성 대표이사상이 수여되고 부상으로 삼성의 고가 노트북이 수여되었습니다.

(대략 10명 정도 받으셨습니다. 고생 많으셨고 축하드려요!)

일반 수료생들은 외장 SSD와 여러 상품이 오고 있다고 하네요! 

728x90

루틴에 맞춰 풀어본 첫 문제입니다.

몸풀기를 할 생각으로 실버 문제를 골랐는데... 너무 빨리 끝나서 생각처럼 잘 되진 않았습니다 ㅋㅋ

문제풀이 루틴에 관한 글은

https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

 

https://www.acmicpc.net/problem/12849

 

12849번: 본대 산책

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.

www.acmicpc.net

 

숭실대학교 교내 대회에서 사용된 문제입니다.

설명도 직관적이고 DP의 개념을 잡기 좋은 문제인 것 같습니다. 

제가 짜 놓은 루틴대로 문제를 풀어보도록 하겠습니다.

 

1. 이해 (5분) - 1분

설명이 워낙 간단명료한 터라 이해에는 긴 시간이 걸리지 않았습니다. 

캠퍼스를 산책하고 주어진 시간에 시작점인 정보과학관에 도착하는 경로가 몇 개인지 알아내면 됩니다.

 

2. 계획 (5분) - 1분

우선 문제의 캠퍼스는 생긴 것 부터 그래프와 유사합니다. 시간이 정해져 있고 경로의 개수를 찾는 것이니 BFS를 생각해 볼만도 하지만 10만 분이라는 시간 후에 무시무시하게 많은 경로를 고려하면 안 될 것 같습니다.

대신 우리는 경로의 갯수만을 구하면 되고, 경로를 알 필요는 없다는 점에 착안해서 DP를 사용해 간단하게 구현이 가능할 것 같습니다. 

비슷한 느낌의 DP 문제로는 https://www.acmicpc.net/problem/2579  [계단오르기 (실버 3)]가 있을 것 같네요.

DP가 진행되는 기준이 시간과 계단으로 다르고 이 문제 같은 경우는 순환이 가능하단 차이가 있지만... 느낌이 비슷하다고 봐주시면 될 것 같습니다. 

특정 시간에 8개의 건물에 위치하는 경로의 갯수를 각각 저장하도록 [입력받은 시간][8]의 2차원 배열을 선언해 앞 시간의 정보를 토대로 풀이해보겠습니다.

그림처럼 건물들에 번호를 매기고

처음 시간 D=0일때 가능한 경로는 0번 건물이 1

D=1일 때 가능한 경로는 1,2번 건물이 각각 1

... 이런식으로 진행해나가려고 합니다.

3. 검증 (5분) - 1분

시간의 최대치는 10만, 제 계획에선 시간 1 당 8번의 덧셈 연산만 진행되면 되니 주어진 시간 1 초안에 무난하게 통과할 것 같습니다. (시간제한 1초를 대략 1억 번의 연산으로 생각하면 됩니다.)

문제에선 정답을 10억7로 나눈 나머지를 출력하라고 했는데, 풀이 도중에 int의 크기를 넘어서는 오버플로우가 발생하기 때문입니다.

매 연산마다 나누기를 진행해주면 되지만, 제가 구상한 풀이에선 신양관, 한경직기념관이 각각 4개의 값이 더해집니다.

그럼 최대 40억의 값이 나오므로 오버플로우를 방지하기 위해 아예 long 타입으로 배열을 선언해줍시다.

 

주어지는 입력으로 가능한 최대 80만개의 long타입 배열이 있다면 long타입의 크기는 16Byte로 사용하는 메모리는 1280만 Byte입니다.

1MB가 약 100만 Byte이므로 12MB가량의 메모리가 필요하고, JVM을 감안해도 문제에서 주어진 512MB의 메모리 안에서 충분히 동작할 것 같습니다.

 

 

4. 풀이 (30분) - 8분

여기까지 구상한 내용으로 풀어봅니다!

 

코드를 작성 한 뒤 주어진 예제를 넣어 확인합니다.

입력의 최솟값인 1과 10만을 넣어 출력이 정상적으로 되는 것을 확인합니다.

(움직이지 않고 머무르는 것이 불가능하므로 입력이 1인 경우 0이 나오는 것이 당연합니다. 10만을 입력한 경우의 정답은 지금 상황에서 확신할 수 없으므로 에러가 발생하지 않는지만 확인했습니다. )

 

5. 채점, 디버깅 (+@)

다행히 한번에 정답으로 통과되었습니다. 

이 문제를 푸는데는 총 11분이 걸렸습니다. 

실버 1의 난이도면 코딩 테스트에서 1,2번의 앞 순위로 나오는 문제니 스타트로 나쁘지 않았습니다!

DP를 구상하고 정답이 자료형의 크기를 넘치는것만 주의하면 크게 어려울 것이 없는 문제였습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static final long div = 1_000_000_007;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int D = Integer.parseInt(br.readLine());
		long[][] map = new long[D + 1][8];
		map[0][0] = 1;

		for (int d = 0; d < D; d++) {
			map[d + 1][0] = (map[d][1] + map[d][2]) % div;
			map[d + 1][1] = (map[d][0] + map[d][2] + map[d][3]) % div;
			map[d + 1][2] = (map[d][0] + map[d][1] + map[d][3] + map[d][5]) % div;
			map[d + 1][3] = (map[d][1] + map[d][2] + map[d][4] + map[d][5]) % div;
			map[d + 1][4] = (map[d][3] + map[d][5] + map[d][6]) % div;
			map[d + 1][5] = (map[d][2] + map[d][3] + map[d][4] + map[d][7]) % div;
			map[d + 1][6] = (map[d][4] + map[d][7]) % div;
			map[d + 1][7] = (map[d][5] + map[d][6]) % div;
		}

		System.out.println(map[D][0]);
	}
}

 

감사합니다!

728x90

저는 코딩 테스트를 그럭저럭 잘 푸는 편입니다.

어... 자뻑이 아니라, 객관적으로 그럴 겁니다!! 아마!

올해 치른 코테에서 대부분 합격했으니까요.

 

1차를 기껏 통과해놓고 2차 코딩 테스트나 면접에서 잘렸습니다만...

 

 

아무튼, 여태까지는 그냥 코테 문제를 보고 생각 없이 열심히 풀면 풀렸습니다.

하지만 실력면에서나 프로그래머로서의 커리어에 있어서나 좋지 않은 습관이 생기고 있는 것 같아
문제풀이 루틴을 정리하고 습관화해보려고 합니다.

코딩 테스트는 작게는 취직을 위한 테스트일 뿐이지만 문제풀이 루틴은 앞으로의 어떤 문제에도 적용 가능하니까요.

 

 

45분에 하나의 문제를 푼다고 가정해 보겠습니다.

보통 코딩 테스트가 4~7문제를 2~4시간 동안 풀고

앞의 몇 개의 문제는 비교적 쉽기 때문에 시간을 절약할 수 있으니

이 시간에 페이스를 맞추어 풀면 1,2개의 킬러 문제를 제외하면 대부분 풀 수 있는 시간입니다.

그리고 제 경험에 의하면 킬러 문제의 풀이는 합격에 크게 영향을 끼치지 않습니다.

(코딩 테스트가 4문제로 이루어진 경우 합격 라인은 2.5~3문제, 7문제의 경우 4.5~6문제 정도였습니다.)

 

1. 이해 (5분)

문제에 대한 이해를 진행합니다. 

 

2. 계획 (5분)

문제의 내용을 토대로 어떤 알고리즘을 써서 풀이하거나 구현할지 생각합니다.

- 간단한구현/복잡한구현(시뮬레이션)/DFS/BFS/DP/브루트포스/그리디/기타 알고리즘 (다익스트라,MST 등등) 

 

3. 검증 (5분)

내가 떠올린 알고리즘이나 풀이가 문제를 풀 수 있는지를 생각해 봅니다.

- 내가 구상한 방법을 사용하면 실행시간 안에 답을 구할 수 있을지 생각합니다.

 

풀이에 적합한 자료구조를 떠올립니다.

- Array/ArrayList/LinkedList/Queue/PriorityQueue/Stack/Map/Set

 

시간이나 메모리를 줄일 방법이나 풀이를 좀 더 수월하게 할 수 있는 기법이 있는지 확인합니다.

- 정렬/비트마스킹/가지치기/메모이제이션/투포인터/슬라이딩윈도우/기타 등등

 

또 문제의 입력, 조건, 범위 등을 체크합니다.

- 테스트 케이스의 갯수 -> 테스트케이스의 형태 -> 입력의 범위 -> 출력의 범위 -> 자료구조의 크기

 

4. 풀이 (30분)

그리고 대망의 풀이!입니다.

가능하면 여유 부리지 않고 빠르게 풀이하는 게 좋습니다.

풀이가 틀릴 수도 있고, 디버깅 등을 통해 예외를 체크할 시간이 필요하기 때문입니다.

음... 여기는 딱히 드릴 팁이 없습니다.

풀이 시간이 부족하시다면 더 많은 노력과 연습!! 을 하셔야 합니다. 

코딩은 운동처럼 머슬 메모리로 하는 겁니다.

 

5. 채점, 디버깅 (+@)

코딩 테스트에서 주어진 예제를 모두 맞추더라도 내부 채점에선 틀리는 경우가 생깁니다.

제가 겪은 자주 발생하는 예외는 다음과 같았습니다.

 

- 입력이 0개, 혹은 1개인 경우

- 특정 상황에서 답이 없는 경우 (정답 변수의 초기화를 체크)

- 정답의 형식이 맞지 않는 경우 (대소문자, 개행 문자, 띄어쓰기 예외적인 경우 등 체크)

 

- 변수의 표현 범위를 넘어서는 경우, 시간 초과 (앞에서 체크했지만 혹시 모르니!)

 

 

다음 알고리즘 풀이부턴 이 5단계에 따라 걸린 시간을 체크하면서 작성해보도록 하겠습니다.

감사합니다!

728x90

표준 함수형 interface

Runnable

입력 X, 출력 X
입력도 출력도 없이 함수 내의 동작만 수행 가능하다.

ex)

void hello(){
    System.out.println("Hello World!");
}

Consummer

입력 O, 출력 X
입력은 있지만 출력이 존재하지 않는다.

ex)

void hello(String msg){
    System.out.println("msg: " + msg);
}

Operation

입력 O, 출력 입력과 같은 Type
입력을 받아 함수가 동작한 뒤 입력과 같은 타입을 return 한다.

ex)

int plus(int a, int b){
    return a+b;
}

Function

입력 O, 출력 anyType
입력의 타입과 상관 없이 return한다. 같은 타입을 return 해도 Function이다. (Operation < Function)

ex)

String plusOperation(int a, int b){
    StringBuilder answer = new StringBuilder();
    answer.append("answer is ").append(a+b);
    return answer.toString();
}

Supplier

입력 X, 출력 O
입력 없이 출력만 존재한다. 정해진 data등을 return 한다.

ex)

String[] getDayArr(){
    String[] dayArray = {"Sun","Mon","Tue","Wed","Thu","Fri","Sat"};
    return dayArray;
}

Predicate

입력 O, 출력 Boolean
입력에 따라 적절한 Boolean값을 return 한다.

ex)

Boolean isSmall(int a, int b){
    if(a < b){
        return true;
    }
    return false;
}
728x90

https://www.acmicpc.net/problem/1202

 

1202번: 보석 도둑

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci

www.acmicpc.net

 

 

보석도둑 문제입니다.

핵심 아이디어는, 가방에 담을 수 있는 가장 비싼 보석을 담자! (Greedy)입니다.

다만 고려해야할 상황이 몇 개 있습니다.

 

우선 큰 가방에 비싼 보석을 담는다면 작은 가방에 아무것도 담지 못하는 비효율적인 상황이 생길 수 있습니다.

그러니 작은 가방을 먼저 채우는것이 좋습니다.

 

둘째, 가방의 갯수가 30만개, 보석의 가격이 100만까지 가능하므로 최대 3000억의 값이 정답으로 나올 수 있습니다.

정답을 long (C계열의 경우 longlong) 타입으로 선언해 주어야 오버플로우가 발생하지 않을 것 같습니다.

 

셋째, 보석과 가방의 갯수를 자세히 보시면... 둘 사이에는 부등호가 없습니다.

즉 가방이 보석보다 많을 수도 있다는 뜻입니다.

저는 이 부분을 놓쳐서 NullPoint Exception을 한 번 보았네요.

 

 

풀이로 들어가겠습니다.

작은 가방부터 넣을 수 있는 최대의 보석을 담습니다. 

저는 그래서 보석과 가방의 정보를 모두 받고, 둘을 모두 오름차순으로 정렬해 주었습니다.

 

그리고 정렬된 가장 가벼운 가방부터 담을 수 있는 가장 비싼 보석을 찾는데,

보석의 정보가 이미 정렬되어 있으므로 한 번 순회하며 자기가 담을 수 있는 보석까지만 PriorityQueue에 넣었습니다.

PriorityQueue의 Comparator를 람다식으로 설정해서 가치가 높은 보석이 위로 올라오게 했으므로 이 PriorityQueue안에는 내가 담을 수 있고 가장 비싼 보석이 위에 존재하게 됩니다.

PriorityQueue에서 보석 하나를 꺼내어 담는 처리를 하고 (정답에 누적합하고) 다음 크기의 가방에 대해 같은 작업을 반복하면 됩니다. 

 

좀 더 최적화된 방법이 있을것 같은데 나중에 생각나면 포스팅을 업데이트 하도록 하겠습니다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		PriorityQueue<int[]> pqueue = new PriorityQueue<int[]>((e1, e2) -> {
			return e2[1] - e1[1];
		});
		int[][] jewels = new int[N][2];
		int[] bags = new int[K];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			jewels[n][0] = Integer.parseInt(st.nextToken());
			jewels[n][1] = Integer.parseInt(st.nextToken());
		}

		for (int k = 0; k < K; k++) {
			bags[k] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(jewels, (e1, e2) -> {
			return e1[0] - e2[0];
		});
		Arrays.sort(bags);

		int index = 0;
		long answer = 0;

		for (int k = 0; k < K; k++) {
			int nowBag = bags[k];

			while (index < N) {
				if (jewels[index][0] <= nowBag) {
					pqueue.add(jewels[index].clone());
					index++;
				} else {
					break;
				}
			}
			if(!pqueue.isEmpty()) {
				answer += pqueue.poll()[1];
			}
		}

		System.out.println(answer);
	}
}

 

 

 

 

728x90

https://www.acmicpc.net/problem/20040

 

20040번: 사이클 게임

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한

www.acmicpc.net

 

또 다른 웰 노운(Well Known인데 우리는 모르는) 알고리즘, 분리집합의 등장입니다. 

유니온이라고도 알려져 있습니다.

유니온은 일종의 단방향 트리라고 생각하셔도 될 것 같습니다.

데이터들을 집합들로 구분할때 어떻게 할 수 있을까요?

일일히 넘버링을 붙이거나 이름을 붙여도 되겠지만, 구현은 어떻게 하실건가요?

두개의 집합이 합쳐질때는요?

 

분리집합은 자신들을 대표하는 데이터를 부모로 가리킴으로서 자신이 속한 집합을 구분합니다.

 

이 데이터를 노드라고 생각한다면, 집합은 여러 노드들이 연결된 그래프가 되겠죠.

자신이 이미 속한 집합의 노드와 연결된다면 그 그래프는 사이클이 생긴 그래프가 됩니다.

간단하죠?

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;
	static int[] parent;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int answer = 0;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		parent = new int[N];
		for (int n = 0; n < N; n++) {
			parent[n] = n;
		}

		for (int m = 1; m <= M; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int aParent = findParent(a);
			int bParent = findParent(b);

			if (aParent == bParent) {
				answer = m;
				break;
			} else {
				parent[aParent] = bParent;
			}
		}

		System.out.println(answer);
	}

	static int findParent(int a) {
		if (parent[a] == a) {
			return a;
		} else {
			parent[a] = findParent(parent[a]);
			return parent[a];
		}
	}
}
728x90

+ Recent posts