백준 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

프로그래머스 : k진수에서 소수 개수 구하기 풀이 (Java, Python)

목차https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr서론오늘 알아 볼 것은 자바와 파이썬에서 각각에서의 진수 변환을 어떻게 하는지, 그리고 그 내용을 토대로 이 문제를 풀어볼 것이다 자바에서의 진수 변환먼저 자바에서는 10진수에서 다른 진수로의 변환을 기본 Integer 클래스에서 toString() 메소드를 통해서 스트링 형태의 진수로 반환한다. 다음과 같이 10진수의 숫자 883438을 3진수로 변환시킨다면 아래와 같다.class Main { ..

• format_list_bulleted Problem Solving/PRGMS
• · 2023. 6. 1.
• textsms