Algorithm 106

[백준] 7770 - 아즈텍 피라미드

문제문제 : https://www.acmicpc.net/problem/7770아즈텍 피라미드는 1 * 1 * 1 크기의 정육면체 돌 블록으로 만든다. 피라미드는 먼저 블록 하나를 놓은 뒤, 이후에 놓는 블록은 이전에 놓인 블록과 한 면 전체를 공유해야 한다.블록은 땅 바로 위에 있거나, 블록 아래에 있는 블록의 모든 면이 인접하고 있을 때 안정적이라고 하며, 모든 블록은 안정적이여야 한다.사용할 수 있는 블록의 개수가 주어졌을 때, 블록으로 만들 수 있는 안정적인 피라미드의 높이를 구하여라.   풀이계산하기 편하게 이미 쌓은 블록을 위로 올리고, 바닥에 놓아야 할 블록의 수를 생각해보자.층에 따라 바닥에 최소로 놓아야 하는 블록의 수는 다음과 같다.N층일 때 바닥에 놓아야 하는 최소 블록의 수를 구했다면..

Algorithm/백준 2025.01.10

[백준] 2959 - 거북이

문제문제 : https://www.acmicpc.net/problem/2959300년 동안 살면서 거의 모든 일을 다 해본 거북이는 이제 어떤 것에도 흥미를 느끼지 않는다. 이번 주말에 거북이는 시간을 때울 무언가로 거북이 세계에서 매우 유명한 '가장 큰 직사각형 만들기' 게임을 하려고 한다.게임을 시작하기 위해선 양의 정수 네 개를 먼저 생각해야 한다. 한 방향으로 움직인 후에는 90도 회전하고 새로운 방향으로 움직여야 한다. 이렇게 세 번 회전하고 네 번 움직여 선분 네 개를 만든다.선분을 그릴 때 움직일 걸음의 수가 바로 미리 생각해 둔 네 정수 중 하나이다. 한 정수는 한 번만 사용해야 한다. 정수를 사용하는 순서에 따라서 다양한 모양이 만들어지는데, 정사각형을 찾을 수 없을 수도 있다.만들 수 ..

Algorithm/백준 2025.01.09

[백준] 2903 - 중앙 이동 알고리즘

문제문제 : https://www.acmicpc.net/problem/2903상근이는 친구들과 함께 외계 지형이 필요한 SF 영화를 찍으려고 한다. 외계 지형은 CG로 중앙 이동 알고리즘을 이용해 만들 생각이다. 알고리즘은 다음과 같다.1. 시작하면서 정사각형을 이루는 점 4개를 고른다.2. 정사각형의 각 변의 중앙에 점을 하나 추가한다.3. 정사각형의 중심에 점을 하나 추가한다. 아래 그림은 알고리즘을 2번 거쳤을 때의 모습이다.알고리즘을 N번 거쳤을 때의 점의 개수를 구하여라.   풀이먼저 문제 예시를 살펴보면 알고리즘을 1번 거쳤을 때는 한 변의 점의 개수 3개의 제곱이 전체 점의 개수이고, 2번 거쳤을 때는 한 변의 점의 개수 5개의 제곱이 전체 점의 개수에 해당한다는 것을 알 수 있다.즉, 전체..

Algorithm/백준 2025.01.08

[백준] 4998 - 저금

문제문제 : https://www.acmicpc.net/problem/4998상근이는 은행에 가서 통장을 만들고 N원을 저금했다. 은행은 통장을 만들지 1년이 지날 때마다 통장에 저금되어 있는 돈의 B%만큼을 이자로 적립한다. 상근이는 이 통장에 추가적인 거래를 하지 않았을 때, 몇 년이 지나야 통장에 저금되어 있는 돈이 M원을 넘을지 궁금하다.N, M, B가 주어졌을 때 몇 년이 지나야 하는지 구하여라. 단, 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각, 테스트 케이스는 한 줄이며 N, B, M이 주어진다.   풀이원금에 대한 이자를 연을 기죽으로 더해지는 연 복리를 계산하는 문제다. 복리 계산법은 쉽게 아래와 같이 표현할 수 있다.즉, 이 문제는 아래 공식을 만족하는 지수 \( x \)를 구..

Algorithm/백준 2025.01.07

[Algorithm] 서로 다른 두 범위가 겹치는지 확인하기

개요다음과 같이 두 개의 범위가 있다고 할 때,├───A───┤ ├───B───┤두 범위에 서로 겹치는 부분이 있는지, 없는지 판단하고 싶다. 간단한 방법이 있는지 알아본다.   경우의 수서로 다른 두 개의 범위가 위치할 수 있는 경우의 수부터 알아보자. 1. 범위 A의 최댓값이 범위 B의 최솟값보다 작은 경우max(A) ├───A───┤ ├───B───┤ 2. 범위 A의 최대값이 범위 B의 최솟값보다 크거나 같으면서 범위 B의 최댓값보다 작거나 같은 경우min(B) ├───A───┤ ├───B───┤ 3. 범위 A의 최소값이 범위 B의 최솟값보다 크거나 같으면서 범위 B의 최댓값보다 작거나 같은 경우min(B) ├───A───┤├───B───┤ 4. 범위 A의 ..

Algorithm 2024.10.04

[백준] 28702 - FizzBuzz

문제문제 : https://www.acmicpc.net/problem/28702FizzBuzz 문제는 i = 1, 2, 3,... 에 대해 다음 규칙에 따라 문자열을 한 줄에 하나씩 출력하는 문제이다.i가 3의 배수이면서 5의 배수이면 FizzBuzz를 출력한다.i가 3의 배수이면서 5의 배수가 아니면 Fizz를 출력한다.i가 3의 배수가 아니면서 5의 배수이면 Buzz를 출력한다.i가 3의 배수가 아니면서 5의 배수도 아니면 i 값을 출력한다.연속으로 출력된 세 개의 문자열이 주어질 때 이 세 문자열 다음에 올 문자열은 무엇인가?  풀이값이 출력되는 규칙을 확인해보면 3과 5의 최소공배수인 15를 주기로 출력 패턴이 반복되는 것을 확인할 수 있다. 따라서 출력 규칙을 만들고,  1. 출력 규칙 생성ru..

Algorithm/백준 2024.07.01

[백준] 1018 - 체스판 다시 칠하기

문제문제 : https://www.acmicpc.net/problem/1018지민이는 단위 정사각형으로 나누어져 있는 M X N 크기의 보드를 찾았다. 보드 내 정사각형은 검은색 또는 흰색으로 칠해져 있는데, 지민이는 보드를 잘라서 8 X 8 크기의 체스판을 만들고자 한다.체스판은 검은색과 흰색이 번갈아가면서 칠해져 있어야 하고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서 지민이는 보드를 잘라낸 후 몇 개의 정사각형을 다시 칠하려고 한다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하여라.  풀이좋은 방법이 없을지 좀 오래 고민을 해보았는데, 입력 크기도 작아서 그냥 완전 탐색하는 방식으로 진행했다. 1. 체스판 초기화체스판은..

Algorithm/백준 2024.06.20

[백준] 1260 - DFS와 BFS

문제문제 : https://www.acmicpc.net/problem/1260그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하라. 단, 방문할 수 있는 정점이 여럿인 경우에는 정점 번호가 작은 것부터 방문한다.첫째 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선을 연결하는 두 정점의 번호가 주어진다. 입력으로 주어지는 간선은 양방향이다.  접근2024.05.08-[알고리즘] 너비 우선 탐색(BFS) 이란, 2024.05.12-[알고리즘] 깊이 우선 탐색(DFS) 이란에서 살펴본 대로 구현하면 된다.   구현1. 입력값 초기화import sysN, M, V = map(int, sys.stdin.readline()...

Algorithm/백준 2024.06.19

[백준] 2108 - 통계학

문제문제 : https://www.acmicpc.net/problem/2108통계학에서 N개 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다.산술평균 : N개의 수의 합을 N으로 나눈 것중앙값 : N개의 수를 오름차순으로 나열했을 때 그 중앙에 위치하는 값최빈값 : N개의 수 중 가장 많이 나타나는 값범위 : N개의 수중 최댓값과 최솟값의 차이첫째 줄에 수의 개수 N을 입력받고, 다음 N개 줄에 걸쳐 정수를 입력받을 때 네 가지 기본 통계값을 구하여라.   접근통계 등의 데이터를 처리할 때는 numpy를 곧잘 사용하는데, 이번 글에서는 numpy 사용 없이 풀이해보려고 한다. 먼저 입력 데이터는 다음과 같이 선언했다.import sysN = int(sys.stdin.readline())list_n..

Algorithm/백준 2024.06.18

[백준] 1966 - 프린터 큐

문제문제 : https://www.acmicpc.net/problem/1966일반적으로 프린터 기기는 인쇄 명령을 받은 순서대로 문서를 인쇄한다. 그런데 최근 상근은 다음과 같이 동작하는 새 프린터 소프트웨어를 개발했다.1. 프린터 큐 내 맨 앞에 있는 문서의 중요도를 확인한다.2. 나머지 문서 중 현재 문서보다 높은 중요도의 문서가 있으면, 이 문서는 인쇄하지 않고 큐의 맨 뒤로 재배치한다. 그렇지 않으면 현재 문서를 인쇄한다.프린터 소프트웨어를 사용하여 프린터 큐에 있는 문서의 수와 중요도가 주어졌을 때, 임의 문서가 몇 번째에 인쇄되는지 반환하는 프로그램을 작성하라. 첫줄에는 테스트 케이스의 수가 주어지고, 각 테스트케이스는 두 줄로 이루어져 있다.테스트케이스의 첫번째 줄에는 문서의 개수 n과 인쇄..

Algorithm/백준 2024.06.14