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로 관리했고, 이동을 동일하게 진행시켜서 문제를 해결했다.