문제

풀이

1. 숫자형 배열의 크기를 비교한다.

2. n번째 숫자를 찾아내는것 -> 정렬을 고려한다. -> 기본 1회 정렬로 풀이가 가능하다.

3. 내부함수를 이용한 시간복잡도는 O(nlog(n))으로 시간 안으로 풀이가 가능하므로 채택한다.

소스

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    val N = 3
    val L = 10
    val T = readLine().toInt()	// 테스트 케이스의 수 입력
    
    // 테스트 케이스 수 만큼 반복
    repeat(T){
        val arr = IntArray(L)	// 값을 저장한 배열
        val st = StringTokenizer(readLine())	// 테스트 케이스 입력
        // 테스트 케이스 안의 숫자만큼 반복하며 배열에 대입
        repeat(L){
            arr[it] = st.nextToken().toInt()	// 정렬할 배열에 숫자를 대입
		}
        arr.sortDescending()	// 내림차순 정렬(오름차순으로 정렬해도 무방)
        
        sb.append("${arr[N-1]}\n")	// 3번째(N-1) 값을 출력값에 저장(오름차순의 경우 7번째 값)
	}
    
    println(sb)
}

문제

import java.util.*

fun main() = with(Scanner(System.`in`)) {
    var n1: Int = nextInt()
    var n2: Int = nextInt()
    val m: Int	// 최대공약수
    
    // 예외처리 n1 > n2로 변환
    if(n2 > n1){
        val temp = n1
        n1 = n2
        n2 = temp
    }
    
    // 최대공약수
    m = gcd(n1, n2)
    
    // 출력(최소공배수 = n1 * n2 / 최대공약수)
    println("" + m + "\n" + ((n1 * n2) / m))
}

// 유클리드호제법을 통한 최대공약수
fun gcd(n1: Int, n2: Int): Int{
    return if(n2 == 0)return n1 else gcd(n2, n1%n2)
}

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

import java.util.*

fun main() = with(Scanner(System.`in`)) {
    val list: ArrayList<Int> = ArrayList<Int>()	// 난쟁이의 키를 입력받을 배열
	var sum: Int = 0    // 현재 키의 총합

	// 9명의 키를 입력받기
    for(i in 0..8){
		val n = nextInt()
        sum += n
        list.add(n)
    }
    
    // 오름차순으로 정리
    list.sort()
    
    // 두 난장이의 키를 빼기
    for(i in 0..7){
        for (j in i+1..8){
			// 합이 100이 되는지 확인
            sum -= (list.get(i) + list.get(j))
            if(sum == 100){
                list[i] = -1	// 출력하지 않을 값을 표기한다.
				list[j] = -1
                break
            }
            // 정답(100인 경우)가 아니라면 수정한 값을 원복한다.
            sum += (list.get(i) + list.get(j))
		}
    }
    
    // 출력
    for(i in list){
        if(i != -1){
            println(i)
        }
    }
}

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

풀이

1. n번째 자리의 값은 n-1번째, n-2번째 값의 합이다. -> n-1, n-2번째 값을 기억하고 있어야한다. -> 배열 자료구조를 채택해서 값을 저장해 놓는다.

2. n < 20의 조건 -> 0부터 n까지 모두 보아도 충분히 작은 값, 시간복잡도 O(n) 이므로 하나씩 보는 방식을 채택한다.

3. n이 0과 1의 경우는 예외처리한다.

코드

import java.util.*

fun main() = with(Scanner(System.`in`)) {
    val n: Int = nextInt()
    val N: ArrayList<Int> = ArrayList<Int>()
    
    for(i in 0..n){
        if(i == 0){
            N.add(0)
        } else if(i == 1){
           N.add(1) 
        } else {
            N.add(N.get(i-1) + N.get(i-2))
        }
    }
    
    println(N.get(n))
}

문제

풀이

1. 2진수의 경우, 2로 나눈 나머지가 존재한다면(나머지는 1) 해당 위치 1의 값이 온다.

2. 테스트 케이스 당 n의 값을 2로 계속 나눈다면 최대 log(n)번 수행해야한다. O(TlogN)

3. T는 최대 10 n의 최댓값은 10^6으로 이므로 최대 log(10^7)의 시간복잡도를 가지므로 2로 계속 나누는 방법을 채택한다.

소스 코드

import java.util.*

fun main() = with(Scanner(System.`in`)) {
    val T = nextInt()	// 테스트케이스 수
    
    // 반복
    for(i in 1..T){
        val N = nextInt()	// 테스트케이스
        module(N)	// 모듈 호출
    }
}

// 이진수를 계산하고 출력하는 모듈
fun module(N:Int) {
   val sb = StringBuilder()	// 출력용 StringBuilder
   var n = N	// 나눌값(몫)
   var c = 0	// 현재 자리 인덱스(1의 자리가 0)
   
   while(n > 0){
   	// 2의 나머지가 1이라면, 해당 자리를 1이 되므로 위치를 저장
	if(n % 2 == 1){
		sb.append(c)
		sb.append(" ")
	}
    
    // 다음조건 설정
	n /= 2	// 2로 나눈 몫
	c++		// 다음 자리(인덱스)증가
   }
   println(sb)
}

문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 

6을 예로 들면

• 6 ÷ 1 = 6 … 0
• 6 ÷ 2 = 3 … 0
• 6 ÷ 3 = 2 … 0
• 6 ÷ 4 = 1 … 2
• 6 ÷ 5 = 1 … 1
• 6 ÷ 6 = 1 … 0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

풀이

1. 나머지가 0으로 나누어 떨어지면 약수이다.

2. N이 10,000이하이다 -> 무식한 방법인 1부터 N까지 모두 확인해도 1만분의 1초(1억에 1초로 가정)

3. 시간복잡도 O(N)이지만 N이 1억 이하로 작기에 방법을 채택한다.

제출 코드

import java.util.*

fun main() = with(Scanner(System.`in`)) {
    val N = nextInt()	// 입력값 받기
    val K = nextInt()	// 입력값 받기
    var C = 0
    
    // 1부터 N까지 루프
    for(i in 1..N){
        // 약수
		if(N%i == 0){
            C++
            // K번째 약수
            if(C == K){
                // 출력
                println(i)
            }
        }
    }
    
    // 약수 확인 종료
    if(C < K) println(0)
}

import sys

sys.setrecursionlimit(10000)

def dfs(x, y, maps, visit):
    val = 0

    if x < 0 or x >= len(maps[0]): return val
    if y < 0 or y >= len(maps): return val
    if visit[y][x] is True: return val
    if maps[y][x] == "X": return val

    visit[y][x] = True
    return int(maps[y][x]) + dfs(x - 1 , y, maps, visit) + dfs(x + 1 , y, maps, visit) + dfs(x, y - 1, maps, visit) + dfs(x, y + 1, maps, visit)

def solution(maps):
    answer = []
    ylen = len(maps)
    xlen = len(maps[0])
    visit = [[False] * xlen for _ in range(ylen)]

    for x in range(xlen):
        for y in range(ylen):
            if maps[y][x] == "X": continue
            if visit[y][x] is True: continue

            cs = dfs(x, y, maps, visit)

            if cs > 0: answer.append(cs)
    if len(answer) == 0: answer.append(-1)
    else: answer.sort()

    return answer

문제는 생략...

특정 지점에서 모든 연결점을 확인하고 연결된 점들끼리 값의 총합을 찾는 문제

모든 연결점 -> 모든 지점을 확인하는 완전탐색 -> dfs or bfs를 선택

문제 제한 조건에서 행과 열의 최대 100이었기에 O(n^2) 최악의 경우 10000 이하의 노드를 확인하므로 완전 탐색 가능하다.

고려사항

1. 문제의 조건인 'X' 값이라면 건너 뜀.

2. 이미 방문한적이 있다면(visit array 가 true 라면) 건너 뜀.

3. 조건의 영역을 벗어난다면 건너 뜀.

4. dfs 선택 시 최대 깊이 10000까지 갈 수 있으므로 최소 recursionlimit은 10000 이상을 해줌(파이썬의 경우).

5. 현 지점에서 4방향을 모두 확인하고 추가적으로 봐야할 지점이 존재한다면 재귀적으로 확인하며 값을 누적해줌.

6. 조건에 일치하는 것이 아무것도 없을 경우 answer에 -1을 넣어줌.

7. 조건에 일치하는 것이 하나 이상일 경우, 숫자의 오름차순으로 정렬해줌.

이런 완전탐색의 경우, 나 처럼 방문 노드를 확인하는 visit 배열을 생성하지 않고 maps의 값을 음수화 시켜서 확인한다던지 하는 기법을 활용할 수도 있다.

하지만, 알고리즘에 완전히 익숙한 사람이 아니라면, 조금 더 직관적으로 알 수 있는 방법을 사용하는 것이 좋다고 생각한다.(주관적)

(기업 코테에서는 메모리는 크게 문제가 되지 않는다.)

결론.

문제를 보고 바로 풀이방법을 찾아냈지만, 오랜만에 풀이라서 생각보다 버벅였다.

사실 maps, visit의 노드 방문시 행 열(x와 y)를 거꾸로 입력했는데 찾는데 시간이 걸렸다... 감이 많이 떨어져있다...

높은 난이도가 아니라도 하루에 한 문제씩이라도 꾸준히 풀어봐야겠다.

유니온 파인드 파이썬 구현하기 / union - find by Phython

유니온 / 파인드는 현재 노드들이 같은 그룹에 속해 있는지 확인하고 같은 그룹으로 만드는 병합이 필요할 때 사용하는 알고리즘입니다.

find 알고리즘 구현

par = [ -1 for i in range(N + 1) ]  # 루트를 담을 배열

def find(x):    # 루트를 찾아주는 함수
    if par[x] < 0:  # 아직 루트가 없다면
        return x    # 자기 자신이 루트  => 아직 연결된 적이 없음
    par[x] = find(par[x])   # 자신의 부모를 부모->부모 를 재귀로 루트 부모를 찾음
    return par[x]   # 루트 부모를 리턴

par 이라는 배열에는 각 노드의 부모를 담아 놓습니다.

par 배열의 index는 각 노드의 번호이고 그 값은 부모 노드를 의미합니다.

처음 모든 노드의 값을 -1(아직 부모가 정해지지 않음)으로 초기화합니다. -> 모든 노드(index)는 아직 부모 노드가 없음(-1)

find 함수는 재귀적으로 자신의 부모의 부모를 탐색합니다. 최종적으로 부모가 없는 노드(값이 -1인 노드)를 발견한다면 최상위 노드(root)로 볼 수 있습니다.

최상위 노드를 찾았다면 해당 노드의 값을 리턴하고 그 이전의 노드들은 최상위 노드의 번호로 자신의 부모 노드를 갱신하게 됩니다.

union 알고리즘 구현

def union(a, b):    # union 두 집합을 연결해주는 함수
    a, b = find(a), find(b) 
    if a == b:  # 루트 부모가 같다면 같은 집합 => 이미 연결 관계
        return False
    par[b] = a  # 부모 노드를 통일시켜 하나의 집합으로 병합
    return True

union 혹은 merge 알고리즘은 두 노드를 인자로 받아서 해당 노드들이 같은 그룹인지 확인하는 알고리즘입니다.

find 함수를 통해서 해당 노드의 부모 노드를 확인합니다.

위 함수에서는 인자로 받은 a, b변수에 부모의 노드의 값을 대입해 주었습니다. (인자로 받은 값은 지역변수 이므로 원본 a, b 가 변하지는 않습니다.)

만약 부모의 값이 같다면 같은 이미 같은 그룹이기에 'False'를 리턴하여 함수를 종료합니다.

그렇지 않다면, 다른 노드이므로 병합을 위해서 한쪽의 부모 노드를 다른 노드의 부모 노드로 갱신합니다. (어느 것이든 상관없습니다.)

갱신 후 같은 갱신을 하였다는 의미로 'True'를 리턴합니다.

union 함수의 목적은 두 부모 노드를 동일하게 만들어 하나의 그룹임을 확인할 수 있는 상태로 만드는 것에 있습니다. 따라서 return 값의 경우 필요에 따라서 수정할 수 있습니다.