반응형

전체 글 180

[BOJ 1038] 감소하는 수

문제감소하는 수https://www.acmicpc.net/problem/1038  풀이설명N번째 감소하는 수를 구하는 문제입니다. 감소하는 수는 오른쪽 숫자가 왼쪽 숫자보다 작아야 합니다. 과정은 다음과 같습니다.10보다 작으면 바로 반환합니다.1부터 9까지의 숫자를 큐에 넣고 시작합니다.큐에서 숫자를 하나씩 꺼냅니다.마지막 자릿수보다 작은 숫자를 뒤에 붙여 새로운 감소하는 수를 생성각 새로운 수를 큐에 추가하고 카운트 증가N번째 수에 도달하면 바로 반환모든 가능한 감소하는 수를 생성했는데도 N번째 수에 도달하지 못하면 -1을 반환합니다. 예시 코드function solution() { const N = Number(input()); if (N

Coding Problem 2025.04.03

[BOJ 14468] 소가 길을 건너간 이유 2

문제소가 길을 건너간 이유 2https://www.acmicpc.net/problem/14468  풀이설명경로가 무조건 만나는 소가 몇 쌍인지를 구하는 문제입니다. 스택을 이용합니다. 과정은 다음과 같습니다.문자열을 순회합니다.처음 나온 문자인 경우스택에 추가합니다.두 번 나온 문자인 경우그 사이에 있는 문자 개수를 카운트해 더합니다.해당 문자를 제거합니다. 예시 코드function solution() { const str = input(); let cnt = 0; const visited = Array(26).fill(false); let stack = []; for (let i = 0; i = 0; j--) { if (stack[j] === ch) break; cnt..

Coding Problem 2025.04.01

[BOJ 12852] 1로 만들기 2

문제1로 만들기 2https://www.acmicpc.net/problem/12852  풀이설명정수 X를 1로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음과 같습니다.X가 3으로 나누어 떨어지면, 3으로 나눕니다.X가 2로 나누어 떨어지면, 2로 나눕니다.1을 뺍니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i를 만드는 데 필요한 연산의 최소 횟수입니다. 점화식은 다음과 같습니다.dp[i]는 다음 세 가지 값 중 최솟값입니다.dp[i - 1] + 1i가 2로 나누어 떨어지는 경우, dp[i / 2] + 1i가 3으로 나누어 떨어지는 경우, dp[i / 3] + 1 추가적으로 경로 배열을 하나 만들어, dp 값이 업데이트 될 때마다 경로를 저장합니다.dp..

Coding Problem/DP 2025.03.27

[BOJ 10164] 격자상의 경로

문제격자상의 경로https://www.acmicpc.net/problem/10164  풀이설명조건을 만족하는 서로 다른 경로의 수를 구하는 문제입니다. 조건은 다음과 같습니다.로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있습니다. (즉, 대각선 방향으로는 이동할 수 없습니다.) 격자에 O로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 합니다.1번 칸과 N × M번 칸은 O 표시가 되어 있지 않습니다.O 표시가 되어 있는 칸은 최대 한 개입니다. DP를 사용해 해결할 수 있습니다. O 표시가 된 칸을 K라고 할 때, 격자에서 갈 수 있는 영역은 K의 우상단과 K의 좌하단입니다.따라서 해당 부분에 대한 경로만 구하면 됩니다. 예시 코드function solution..

Coding Problem/DP 2025.03.26

[BOJ 1463] 1로 만들기

문제1로 만들기https://www.acmicpc.net/problem/1463  풀이설명정수 X를 1로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음과 같습니다.X가 3으로 나누어 떨어지면, 3으로 나눕니다. X가 2로 나누어 떨어지면, 2로 나눕니다. 1을 뺍니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i를 만드는 데 필요한 연산의 최소 횟수입니다. 점화식은 다음과 같습니다.dp[i]는 다음 세 가지 값 중 최솟값입니다.dp[i - 1] + 1i가 2로 나누어 떨어지는 경우, dp[i / 2] + 1i가 3으로 나누어 떨어지는 경우, dp[i / 3] + 1 예시 코드function solution() { const N = +input(); co..

Coding Problem/DP 2025.03.25

[BOJ 2785] 체인

문제체인https://www.acmicpc.net/problem/2785  풀이설명필요한 고리의 최소 개수를 구하는 문제입니다. 방법은 다음과 같습니다.체인을 길이를 기준으로 내림차순으로 정렬합니다.가장 오른쪽 체인(가장 길이가 작은 체인)에서 고리를 하나씩 풀어 가장 왼쪽의 체인 두 개를 연결합니다.모든 체인이 연결될 때까지 2번을 반복합니다. 예시 코드function solution() { const N = Number(input()); const chains = input() .split(" ") .map(Number) .sort((a, b) => b - a); let left = 0, right = N - 1; let answer = 0; while (left

Coding Problem 2025.03.24

[BOJ 2653] 수 이어가기

문제수 이어가기https://www.acmicpc.net/problem/2635  풀이설명규칙에 맞춰 만들어지는 최대 개수의 수들을 구하는 문제입니다. 규칙은 다음과 같습니다.첫 번째 수로 양의 정수가 주어집니다. 두 번째 수는 양의 정수 중에서 하나를 선택합니다. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만듭니다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것입니다. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않습니다. 주어진 수를 N이라 할 때,N의 절반에 해당하는 수부터 N까지 1씩 증가시키며 규칙에 맞춰 수열을 만들어 구합니다. 예시 코드function solutio..

Coding Problem 2025.03.23

[BOJ 1913] 달팽이

문제달팽이https://www.acmicpc.net/problem/1913  풀이설명1부터 N^2까지의 자연수를 달팽이 모양으로 채우고, 주어진 자연수의 위치를 찾는 문제입니다. 방향은 위, 오른쪽, 아래, 왼쪽 순입니다.이동 횟수는 1 -> 1 -> 2 -> 2 -> 3 -> 3 과 같은 식으로 증가합니다.방향 전환 후 이동 횟수만큼 이동하며 수를 채우면 됩니다. 예시 코드function solution() { const N = Number(input()); const target = Number(input()); const maxNum = N * N; const matrix = Array.from({ length: N }, () => Array(N).fill(0)); let num = 1; ..

Coding Problem 2025.03.22

[BOJ 2622] 삼각형만들기

문제삼각형만들기https://www.acmicpc.net/problem/2622  풀이설명주어진 성냥개비로 만들 수 있는 삼각형의 개수를 구하는 문제입니다. 삼각형을 만들려면 가장 작은 변 2개의 길이의 합이 나머지 변의 길이보다 커야 합니다. 예시 코드function solution() { const N = Number(input()); return countTriangles(N);}function countTriangles(matchsticks) { let totalTriangles = 0; for (let a = 1; a c) totalTriangles++; } } return totalTriangles;}

Coding Problem 2025.03.21

[BOJ 2659] 십자카드 문제

문제십자카드 문제https://www.acmicpc.net/problem/2659  풀이설명입력된 카드의 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 구하는 문제입니다. 1111부터 시작해서 해당 카드의 시계수까지 카운트를 증가시키며 계산합니다. 예시 코드function solution() { const target = input().split(" ").join(""); const targetClockNum = getClockNum(target); let cnt = 0; for (let i = 1111; i

Coding Problem 2025.03.20