Algorithm | 문제 풀이 복기

알고리즘 문제 풀이 후 복기하며 기록하는 페이지이다.

알고리즘 문제 풀이 복기

알고리즘 문제 풀이 복기

2026.03.23 - 백준 1065 | 한수

주어진 수의 모든 자리수들간의 차이값이 일정한 수를 "한수"라고 한다고 한다. 문제의 핵심은 주어진 한 수의 모든 자리수들의 차이가 일정한지 묻는 문제이다.
수를 문자열(String)으로 변환 후, 반복문을 이용해서 해결하였다. 수가 아무리 크더라도 자릿수가 크지 않기 때문에 String 혹은 Character 배열로 다루는 것이 메모리를 적게 사용한다고 판단하였다.

각 자릿수간의 관계를 판단할 때, String 또는 Character 배열로 다룰 수 있다.

2026.03.24 - 백준 14425 | 문자열 조합

문자열 집합이 주어지고, 추가로 주어지는 문자들 중 문자열 집합에 포함되는 것들의 수를 계산하는 문제이다.

핵심은 문자열 포함 여부를 판단할 때, 얼마나 빠르게 결정하는 것이다. 탐색의 시간복잡도를 O(1)로 줄이는 방법은 Hash를 이용하는 것이다. 그럼 사용할 수 있는 선택지는 HashMap 혹은 HashSet이 있는데. 이 경우에는 key, value로 관리할 2개의 값이 존재하는 게 아니므로, HashSet을 사용하는게 적절하다고 판단하였다.

HashMap vs. HashSet

2026.03.25 - 백준 1269 | 대칭 차집합

공집합이 아닌 두 집합이 주어지고, 서로에 대한 차집합들의 원소의 개수의 합을 구하는 문제이다.

집합이기 때문에 당연히 Set을 사용하려했고, 탐색을 해야 하기 때문에 HashSet을 사용했다. 원소의 개수는 20만개를 넘지 앟고, 원소의 값은 1억을 넘지 않는다. Hash를 사용했기 때문에 한 집합의 원소의 개수의 수는 의미가 없었고, 원소의 최대값이 1억이라는 점인데. Integer는 양수 21억까지는 문제없이 표현하니까 큰수로 다룰 필요는 없다.

이번 문제에서 한 가지 고민했던것은, Set의 순회여부인데, 순서만 보장되지 않을 뿐 순회는 문제없이 사용할 수 있어 Set 사용에 문제가 없을 것이란걸 확인하였다.

Set - 순회 가능하다.

2026.03.26 - 백준 11478 | 서로 다른 부분 문자열 계산 & 집합과 맵 Clear

주어진 문자열에 대해서 부분 문자열 집합의 원소의 개수를 구하는 문제이다.

부분 문자열은 부르트포스 방식을 사용하였다. 이중 for문을 사용하였고, 첫번째는 부분 문자열의 사이즈, 두번재는 앞에서부터 끝까지 해당 사이즈로 substring 하였다. 특징은 두번째 for문에서 전체 문자열의 길이까지 포함해 줘야 했다. (0번째 인덱스 부터 시작한다면 보통은 문자열 길이보다 작은 경우까지 for문을 돌리는데, 이 경우 0번째 인덱스부터 시작했음에도 문자열 길이까지 연산을 해주어야 했다.) 문자열 집합은 HashSet으로 관리하였는데, Set은 추가할 요소가 포함되어있는지 판단하지 않아도 알아서 중복 추가하지 않는 장점이 있고, Hash를 사용해서 해당 조회의 시간 복잡도도 O(1)로 낮출 수 있다.

Set을 이용하면 contains() 메서드 호출을 생략할 수 있는 경우가 있다.

• 집합과 맵 Clear

백준 사이트의 단계별 풀어보기를 따라가면서 문제를 풀고 있는데, 오늘 백준 11478 문제까지 해서 14단계인 "집합과 맵" 항목을 clear 했다.

백준 14단계 - 집합과 맵

다음은 15단계 "약수, 배수와 소수2"이다.

14단계와 15단계

2026.03.27 - 백준 13241 | 최소공배수

두 수의 최소공배수를 구하는 단순한 문제였다. 문제가 친절하게 사용해야 할 데이터 타입까지 명시해주었다.

공식이라고 볼 수 있는, GCD, LCM 로직을 활용해서 간단하게 해결하였다.

int N, M

// GCD  
int a = N;
int b = M;

while (b != 0) {
    int temp = a % b;
    a = b;
    b = temp;
}

int GCD = a;

// LCM

int LCM = N / GCD * M;

2026.03.30 - 백준 1735 | 분수 합

주어진 두 분수의 합의 기약분수를 구한 뒤, 분자와 분모의 합을 구하는 문제이다.

풀이 방법은 여러가지가 있겠지만, 가장 간단하게 두 분수를 일단 더한뒤 분자와 분모의 최대공약수를 구해서 이를 활용해 기약분수를 만드는 방법을 사요했다. 이렇게 했을 때, 연산 횟수가 가장 적을 것이라 판단하였다.

2026.03.31 - 백준 2485 | 가로수

주어진 가로수들 사이에 가로수를 세워 모든 가로수들 사이의 간격이 동일하도록 하는데 필요한 가로수의 최소값을 구하는 문제이다.

모든 가로수 사이 간격의 최대공약수를 구하면, 이 값이 가로수들이 가져야할 간격이 된다. 이 값을 이용해 추가로 심어야 하는 가로수들의 수를 구하였다.

2026.04.01 - 백준 4134 | 다음소수

주어진 각 수에 대해서, 같거나 큰 소수들 중 최소값을 출력하는 문제이다.

이 문제에서의 핵심은 소수를 빠르게 찾는 것이다. 일단 유일한 짝수 소수인 2는 별도의 로직 없이 취한 뒤 이후 모든 짝수는 탐색대상에서 제외해준다. 이제 홀수들만 고려해 주면 되는데, 그 다음의 핵심은 반복문의 i*I 를 사용한 부분이다.

static boolean isPrime(long num) {
    if (num % 2 == 0) return false;

    for (long i=3; i*i <= num; i+=2) {
        if (num % i == 0) return false;
    }
    return true;
}

 

이렇게 사용한 이유는 num이 만약 합성수라면 √num 보다 작은 수를 반드시 약수로 갖게 되어 있다. 그런데 찾고 있는 소수는 가지고 있으면 안되기 때문에 root(num)까지로 탐색 범위를 좁힐 수 있고, 결과적으로 시간 복잡도를 O(√N)으로 낮출 수 있다.

소수는 2를 뺀 나머지 짝수는 제외한 홀수, 그중에서도 √num 까지의 수중에서 탐색해서 찾으면 된다.

2026.04.02 - 백준4948 | 베랑트랑 공준 

주어진 수 n에 대해서, n보다 크고 2n보다 작거나 같은 수 중에 존재하는 소수의 수를 출력하는 문제이다.

이 문제는 각 케이스별로 소수를 구해야 할 경우에만 소수를 구하도록 하여 연산의 수를 최적화 하였고, 소수의 수는 구해놓은 소수 리스트를 한 번 순회하며 계싼하도록 구현하였다.

2026.04.03 - 백준 17103 | 골드바흐 파티션

임의의 짝수는 두 개의 소수의 합으로 표현될 수 있다는 것이 골드바흐 파티션의 개념이다. 이 문제는 골드바흐 파티션을 이용해서, 주어진 짝수를 만드는 두 소수의 합의 조합의 수를 구하는 문제이다.

이 문제는 이전의 두 문제를 응용해 소수를 구하는 것을 이용하면 간단하게 풀 수 있는 문제이다. 다만 제출시 시간 초과 문제가 있어 구한 소수를 조회할 때 순회를 하면 안되었다. 따라서 HashSet을 이용해서 조회를 O(N^2에서 O(1)의 시간복잡도로 낮추어 해결하였다. 

2026.04.06 - 백준13090 |  창문닫기

1부터 주어진 수까지 순회하면서 각 배수의 창문이 열려있으면 닫고, 닫혀있으면 열어서 결국 몇 개의 창문이 열려 있는지 계산하는 문제이다.

처음에은 에라토스테네스의 체 방식의 순회를 생각했다. 그리고 추가로 발견한 단서는 열려있는 창문은 약수가 홀수인 점을 발견했다. 그래서 Brute Force로 순회하면서 약수가 홀수인 수들의 수를 세어 출력했다. 그런데 시간초과가 되었다. 그래서 한 단계 발전시킨 전략이 약수 중에 제곱수가 있는지를 판단해서 수를 세어 보았다. 그런데도 시간초과가 되었다. 그래서 좀 더 살펴보니, 제곱수가 없는 수들은 모두 닫히게 되기 때문에 제곱수가 있는 수들을 기점으로 가우스 정수방식을 적용해 보았다. 그렇게 했더니 수를 셀 필요 없이 단 한 번의 연산으로 열린 창문의 수를 찾을 수 있었다.

제곱수를 갖는 수의 약수는 홀수이다.

• 약수, 배수와 소수 2

15단계인 약수, 배수와 소수 2도 완료하였다.

백준 15단계 - 약수, 배수와 소수 2

다음은 16단계인 스택, 큐, 덱 1이다.

15단계와 16단계

2026.04.07 - 백준 28278 | 스택 2

스택의 동작을 묻는 문제였다. 간단하게 스택을 사용해서 풀었고, 5개의 요청을 처리한 후 출력이 필요할 땐, System.out.println() 메서드를 사용했다. 하지만 이렇게 했을 때 시간초과가 발생했고, 출력을 BufferedWriter를 이용해서 마지막에 일괄출력하는 방식으로 변경해 주어야 했다.

2026.04.08 - 백준 12789 | 도키도키 간식드리미

문제는 하나의 Main Stack이 있고, 순서가 맞을 경우 제거하지만 아닐 경우 또 하나의 Sub Stack에 수를 추가해서 다시 제거 작업을 하는 문제이다.

이 문제는 살짝 이해를 잘못해서 여러번의 시행착오가 있었다. 기존에는 먼저 메인 스택에서 하나를 검사한뒤, 그 다음 서브스택을 검사하고 이때 메인 스택에서 나왔던 수를 서브스택에 넣었었다. 그런데 실제 문제는 메인 스택을 검사한뒤 서브스택을 검사하고 이 때 메인 스택에서 뽑았던 수를 서브스택에 넣어준다. 그 뒤 서브 스택을 다시 한번 검사해야 한 번의 사이클을 마친 것이다. 문제가 살짝 복잡했다.

2026.04.09 - 백준 28279 | 덱 2

1부터 8까지 정해진 명령에 맞게 수를 출력하는 문제이다. 간단하게 Deque를 사용할 주 아는지 묻는 문제였다. LinkedList를 이용해서 해결하였다.

2026.04.10 - 백준 2346 | 풍선 터뜨리기

풍선 n 개가 주어진다. 첫번째 풍선부터 시작해서 터뜨리고, 풍선안에 있는 정보를 이용해서 양수일 경우 오른쪽으로, 음수일 경우 왼쪽으로 순환 이동을 하면서 풍선을 터뜨린 순서를 기록하는 문제이다.

풍선번호화 풍선 속 정보를 각각의 Dequeue로 관리했고, 이동을 동일하게 진행시켜서 문제를 해결했다.

2026.04.13 - 백준 24511 | queuestack

큐, 스택 들로 이루어진 배열이 있다. 주어진 수를 0번째 자료구조에 넣고, pop 했을 때 나오는 수를 다음 자료구조에 넣고 또 pop하는 과정을 배열 끝까지 수행해 마지막에 나오는 수를 출력하는 문제이다.

처음에는 실제 큐와 스택의 기능을 구현해서 작업을 했는데 시간 초과가 발생했다. 그래서 필요없는 작업을 줄이기 위해 살펴보았는데. Stack은 넣은 값을 그대로 다시 pop 하기 때문에 실제로는 존재하지 않아도 되는 데이터 구조였다. 그럼 실질적으로는 Queue만 남기 때문에 자료구조 배열은 Queue로 바뀌었고. 이전에 O(N*M)의 시간복잡도는 O(N+M)으로 간단해졌다.

• 스택, 큐, 덱 1

16단계인 스택, 큐, 덱1을 완료하였다.

백준 16단계 - 스택, 큐, 덱 1

다음은 17단계인 조합론이지만, 일전에 모두 풀어놓은 상태이다. 따라서 내일부터는 18단계인 심화2를 진행할 계획이다.

16단계부터 18단계

2026.04.14 - 백준 25192 | 인사성 밝은 곰곰이

채팅창 메시지가 input으로 주어진다. 누군가 들어오면 ENTER라는 표시가 뜨는데, 이후 첫 메시지는 모두 곰곰티 아모티콘을 사용한다. 그럼 주어진 메시지 전체를 분석했을 때 곰곰티 이모티콘은 몇번 불렸는지 묻는 문제이다.

HashSet을 이요해서 Enter 이후에 입력하는 사람들의 id를 저장하였다. 그리고 새로운 Enter가 발생하면 다시 인사를 해야하기 때문에 기존 Set Size를 횟수를 기록하는 변수에 더해준뒤 Set를 clear한 뒤 다시 곰곰티 갯수를 세도록 구현하였다.

만약 Set을 사용하지 않고, List를 사용했다면 clear하는 작업이 필요 없겠지만, 이 경우 O(n)의 탐색을 필요로 하기 때문에 Set을 사용하였다.

2026.04.15 - 백준 26069 | 붙임성 좋은 총총이

춤을 추는 사람을 만난 사람은 춤을 추게 되고, 처음엔 총총이만 춤을 추고 있다. 그리고 만난 사람들의 정보가 주어진다. 최종적으로 춤을 추고 있는 사람들의 수를 세는 문제이다.

춤을 추는 사람을 만난 사람들은 Set에 넣어서 춤추는 사람들의 정보를 모았다. 그리고 마지막에 이 Set의 size를 출력해 해결하였다.

2026.04.16 - 백준 20920 | 영단어 암기는 괴로워

영어 단어들이 주어지는데. 총 3가지 조건에 맞춰서 정렬해 출력하는 문제이다.

오랜만에 PriorityQueue를 사용해보고 싶어서 시도해보았는데, 계속 시간 초과가 났다. 그럴수밖에 없는게, 노드를 추가할 때마다 전체 비교작업을 수행하기 때문에 비교 연산수가 늘어났기 때문이다. 이를 보완하기 위해서, PriorityQueue 대신 List를 사용했고, Comparator?를 정의해줘서 한 번의 정렬로 해결하였다.

• 심화 2

18단계인 심화 2 문제를 모두 풀었다.

백준 18단계 - 심화 2

다음은 19단계 재귀에 들어갈 예정이다. 남은 문제수가 4개라 다음주에 또 끝나지 않을까 생각한다. 그리고 이제 슬슬 골드레벨 문제들이 나오기 시작한다. 이제 워밍업은 끝난 것 같다!

18단계와 19단계

2026.04.20 - 백준 24060 | 알고리즘 수업 - 병합 정렬 1

배열 하나가 주어지고, 배열을 분할한 뒤, 분할한 배열들을 정렬시키고, 새로운 배열에 두 배열을 순회하면서 정렬상태를 유지시킬수 있는 순서로 값을 넣어주면서 정렬을 시킨다. 이 때, 넣어주는 행위 한 번을 '기록한다'라고 하는데. 이 기록이 K번째의 수를 출력하는 문제이다.

배열을 정렬하기 전에 분할작업이 이뤄지는데, 정렬 전에 자기자신인 분할정렬을 재귀적으로 호출해 최종적으로 길이가 1인 배열까지 줄어들게 되고, 여기서부터 병합이 시작되도록한다. 그 뒤 기록할 때, 기록의 수를 늘려주고, K와 같아졌을 때 result 값을 세팅해 주어서 해결하였다.

2026.04.21 - 백준 10870 | 피보나치 수 5

0과 1로 시작하는 피보나치 수열에 대해서 주어진 수의 위치에 있는 수를 출력하는 문제이다. 주어진 수는 20보다 작기 때문에 단순히 연산해도 문제가 없는 간단한 문제였다. 주어진 수가 0인 경우에는 0을 출력하도록 Early Return 조건을 주었고, 이후부터는 연산을 거치도록 하여 문제를 해결하였다.

2026.04.22 - 백준 4779 | 칸토어 집합

3의 N승의 수를 구해서, 첫 N/3은 -를 채우고, 그 다음은 비우고, 마지막은 다시 -를 채우는 과정을 반복해 결과를 출력하는 문제이다.

처음에는 -를 채운뒤 실제로 제거를 하려고 했는데, 마지막에 "- -"만 출력하면 된다는 것을 생각해서, N/3이 1이 될 때 종료되는 재귀함수 호출로 문제를 해결하였다.

20226.04.24 - 백준 2447 | 별찍기 - 10

저해진 패턴을 주어진 수에 맞춰 늘려나가는 문제이다.

컴퓨터는 한 줄씩 출력해야 하기 때문에 블럭 단위로 출력을 할수 없어, 재귀를 이용해 한 줄 한 줄을 채워나가는 식으로 구현을 시도하였다. 그런데 생각보다 잘 되지 않아서, 결국 NxN 배열을 사용하게 되었다. 가장 기초가 되는 패턴은 3x3 배열인데. 초기값으로 3x3만 채워주고 이후에는 이 내용을 나머지 격자 8칸에 채우는 식으로 문제를 해결하였다.

• 재귀

19단계인 재귀 문제를 모두 풀었다.

백준 19단계 - 재귀