[Python] 백준 14888 연산자 끼워넣기,

문제https://www.acmicpc.net/problem/14888 풀이 방식해당 문제는 연산자를 사용하며, 가능한 연산을 모두 해보는 완전탐색과 백트래킹으로 해결할 수 있다. 문제를 해결하기 위해서 각 연산을 수행하고, 재귀구조로 이를 구현했다.덧셈, 뺄셈, 곱셈, 나눗셈에 대한 모든 연산을 수행할 수 있도록 dfs함수 내에 for문으로 각 연산을 수행했다. 이렇게 간단하게 해결할 수 있는데, 파이썬의 경우 3번 케이스에서 문제가 발생한다. 본 문제에서 연산자의 숫자는 들어온 순서대로 진행하며, 나눗셈은 버림 연산을 한다고 명시되어 있다.여기서, 나눗셈의 버림 연산 과정이 문제이다. 파이썬에서 나눗셈의 몫만 사용하는 연산은 // 인데, 문제 발생은 이 연산자의 작동 방식에 있다.Python의 나눗셈..

• format_list_bulleted CodingTest/BOJ
• · 2025. 4. 7.
• textsms

[Python] 백준 9095 1, 2, 3 더하기 문제풀이 및 정답

문제 : https://www.acmicpc.net/problem/9095 문제풀이본 문제는 간단한 DP 알고리즘의 문제였다.DP 문제를 해결하기 위해선 초기항과 점화식이 필요하다. 하지만 이번 문제는 쉽게 생각해낼 수 있는 수준이었다.일단, 우리가 사용할 수 있는 수식에서의 숫자는 1, 2, 3이다. 여기서 초기항이 3개까지 작성되야 한다는 것을 알 수 있다. 되게 간단한 개념인데, DP 배열을 선언하고 해당 배열의 각 인덱스에는 해당 인덱스 숫자를 만들기 위한 수식의 최대 개수가 들어간다.예를 들어서 2번 인덱스에는 2를 만들 수 있는 수식의 최대 개수가 들어간다.여기서 2를 만들기 위해선 1+1, 2로 총 2개가 있다. 이러한 방식으로 1번항과 3번항을 만들면 문제를 해결하기 위한 준비가 모두 끝이..

• format_list_bulleted CodingTest/BOJ
• · 2025. 3. 3.
• textsms

[Python] 백준 1992 쿼드트리 문제풀이 및 정답해설

문제 주소 : https://www.acmicpc.net/problem/1992 문제풀이대표적인 분할정복 문제이다. 쿼드트리란, 비트를 압축하여 표현할 수 있는 트리의 구조를 의미한다고 한다.본 문제의 설명을 보면 알 수 있듯, n*n 사이즈의 맵이 주어지면, 해당 맵을 (좌상단, 우상단, 좌하단, 우하단)으로 총 4개로 분해할 수 있다.또한 분해되어 표현되는 부분은 괄호로 정리한다. 이는 트리의 상속과정을 나타낸다고도 이해할 수 있다. 분할정복을 수행할 때, 맵을 나누는 방식도 중요하지만, 어떤 정보가 필요한지 문제에 따라 구상할 필요가 있다. 이번 문제에서 필요한 정보는, 우측 상단의 좌표값과 맵의 크기인 n이다.매 분할과정에서 n은 2배수로 줄어든다.nr, nc는 사분면의 위치에 따라서 다르다.이 ..

• format_list_bulleted CodingTest/BOJ
• · 2025. 3. 2.
• textsms

[Python] 1074 Z 문제 풀이 및 정답코드

문제 : https://www.acmicpc.net/problem/1074본 문제와 같이 배열을 분할하는 문제는 흔히 분할 정복(Divide & Conquer) 기법을 활용하여 해결한다. 특히, 배열이 특정한 패턴을 따르며 순차적으로 탐색되거나 순서가 정해져 있을 경우, 재귀적인 방법이 유용하다. 이번 문제는 조금 오래 걸려서, 제대로 정리해보고자 한다.1. 문제 유형배열을 재귀적으로 나누면서 특정 위치를 찾는 문제는 대개 Z-모양 탐색, 쿼드트리 분할, 행렬 곱셈 최적화 등의 유형에서 등장한다. 이러한 문제는 일반적으로 다음과 같은 특징을 가진다.배열의 크기가 2^n × 2^n 형태로 주어진다.배열을 4개의 부분으로 나누어 처리할 수 있다.각 부분의 크기가 절반으로 줄어들면서 탐색이 진행된다.위의 특징..

• format_list_bulleted CodingTest/BOJ
• · 2025. 3. 1.
• textsms

[Python] 백준 2156 포도주 시식 문제풀이

문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 6개의 ..

• format_list_bulleted CodingTest/BOJ
• · 2025. 2. 28.
• textsms

[Python] 백준 1167 트리의 지름 문제풀이

문제트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.입력트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 ..

• format_list_bulleted CodingTest/BOJ
• · 2025. 2. 27.
• textsms