백준 1562번 : 계단 수 [Java]

https://www.acmicpc.net/problem/1562문제 탐색하기문제에서 요구하는건 특정 조건을 만족하는 계단 수를 구하는 것이다.0 ~ 9까지의 모든 수를 포함해야하며인접한 모든 자리의 차이가 1이어야 한다.계단 수는 0으로 시작할 수 없다.문제를 시작하기 탐색하기 전에 비트필드를 이용한 DP 문제가 처음이라서 검색 시간이 있었다. 간단하게 설명하자면 비트가 켜진 유무에 따라서 수의 상태를 나타낼 수 있다.0 ~ 9 까지의 모든 수를 포함하게 하려면 결국 직접 탐색을 하는 방법 밖에 없는데, 이 때 탐색을 진행하다가 특정 수를 만나면 해당 비트를 키는 방식으로 진행하면 된다. 설명을 위해 비트필드를 배열로 표현하였다. 아래와 같은 비트필드를 이용해서 계단수를 탐색하면서 1을 만났다고 가정하..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 5.
• textsms

백준 2342번 : Dance Dance Revolution [Java]

https://www.acmicpc.net/problem/2342문제 탐색하기문제에서 요구하는건 기존의 DDR 게임과 똑같지만 발이 다른 칸에 위치해야 한다는 점을 생각해보아야 한다.그렇다면 각 위치에서 특정 입력 값이 들어왔을 때 발 위치는 항상 달라야 한다는 점에서 문제 풀이 법을 착안해볼 수 있다. 이때 풀이 방법으로는 두 가지를 생각해볼 수 있다 매번 특정 위치에서의 최소 힘을 계산하고 다음으로 넘어가거나아니면 특정 위치에서의 현재 입력 값까지의 계산 값을 미리 저장해두고 다음 번 입력이 들어왔을 때 사용하는 방법이다.특정 위치를 x, y라고 하고 입력 값으로 들어올 수 있는 수는 1, 2, 3, 4이다.이를 기반으로 3차원 배열을 만들어서 DP 구현하면 처음 계산해둔 값으로 매번 입력값을 더해주..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 4.
• textsms

백준 10422번 : 괄호 풀이 [Java]

문제 탐색하기T : 전체 테스트 케이스의 개수L : 각 테스트 케이스 마다의 괄호 문자열의 길이 총 T개의 괄호 문자열의 길이에 대해 서로 다른 올바른 괄호 문자열의 개수를 구해야 한다. 가능한 시간복잡도각 길이 L에 대해서 모든 올바른 괄호의 경우를 직접 계산 한다면 각 길이에 대해서 2^L나 되는 경우를 직접 완전 탐색을 통해서 찾아야 한다L의 최대 길이는 5000 이므로 직접 모든 경우를 계산한다면 2 ^ 5000도 넘는 수를 계산 해야한다. 이에 따라서 직접 모든 경우를 찾아서 문제를 푼다면 시간복잡도 초과로 WA를 받게된다. 그러면 어떻게 계산 해야할까? 직접 올바른 괄호 문자열인지 확인하는 것이 아니라 문제에 나온 조건을 활용하여 점화식을 세워야 한다. 두 올바른 괄호 문자열 S, T에 대해서..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 3.
• textsms

백준 14503번 : 로봇청소기 풀이 [Java]

서론 코딩테스트를 처음 준비하면서 부터 지금까지 dx와 dy를 거의 항상 다음과 같이 쓰고 있었다. int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; 사실 헷갈리지 않는다면 위처럼 적어도 상관없지만 문제의 입력 조건 (방향 d에 따라서 다음 방향이 결정된다. d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.) 따라서 이번 문제와 같은 경우는 각 방향에 맞게 dx와 dy 배열을 수정했다. int[] dx = {-1, 0, 1, 0}; int[] dy = {0, 1, 0, -1}; 풀이 문제의 설명이 여러번 수정된 기록이 있는 것으로 보아 원래부터 설명이 헷갈리게 작성되어 있었던것 같다. 물론 지금 설명도 이해하기는..

• format_list_bulleted Problem Solving/BOJ
• · 2023. 8. 16.
• textsms

백준 17142번 : 연구소 3 풀이 [Java]

서론 위 문제를 풀기 전에 아래 두 문제를 풀어보길 권장한다! https://www.acmicpc.net/problem/14502 https://www.acmicpc.net/problem/17141 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러 www.acmicpc.net 풀이 전형적인 조합 + BFS의 구현 문제지..

• format_list_bulleted Problem Solving/BOJ
• · 2023. 8. 10.
• textsms

백준 7662번 : 이중 우선순위 큐에 대한 고찰 (Java, Python)

목차 서론 PS 세상에서 난 행복할 수 없는걸까... https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 한달 전에 풀었었지만 오늘 프로그래머스에서 동일한 문제를 풀다가 생각이나서 Java로 다시 풀어봤다! https://school.programmers.co.kr/learn/courses/30/lessons/42628 참고로 프로그래머스에 있는 문제와 백준에 올라와 있는 문제는 동일하다. 같은 로직을 써서 정답을 받을 수 있지만 프로그래머스의..

• format_list_bulleted Problem Solving/BOJ
• · 2023. 5. 18.
• textsms