Passwd

문제문제 : https://www.acmicpc.net/problem/3004상근이는 체스판을 톱으로 자르려고 한다. 체스판은 최대 N번 자를 수 있고, 변에 평행하게만 자를 수 있다. 또 자를 때는 체스판의 변의 한쪽 끝에서 다른 쪽 끝까지 잘라야 하며, 자른 후에는 조각을 이동시킬 수 없다.이때 최대 몇 조각을 낼 수 있는지 구하여라.   풀이체스판 조각이 최대가 되기 위해서는 가로와 세로를 번갈아가면서 잘라야 한다.체스판 조각의 수는 가로 조각의 수와 세로 조각의 수를 곱한 값에 해당하며, 자를 때마다 조각은 1개씩 증가한다. 또한 가로 조각과 세로 조각이 모두 증가하기 위해서는 2번 잘라야 한다.때문에 가로 조각은 N을 2로 나눈 몫에 1을 더한 값, 그리고 세로 조각은 N을 2로 나눈 몫에 나머..

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

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

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

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

문제문제 : 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..

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

문제문제 : 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()...

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

문제문제 : https://www.acmicpc.net/problem/2667그림 1과 같이 정사각형 모양의 지도에서 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 이 지도에서 상하좌우 방향으로 인접한 집의 모임을 단지로 정의하고, 단지에 번호를 붙이려고 한다.그림 2는 그림 1을 단지별로 번호를 붙인 뒤 색을 달리하여 표시한 것이다.지도를 입력받아 단지의 수와 단지 별 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하라.   접근그래프 탐색 방법인 DFS나 BFS를 사용하여 풀어낼 수 있다. 최단 경로를 요구하지 않으므로 DFS, BFS 중 편한 방법으로 구현하면 될 것 같다.다만 지도 내 단지가 하나 이상이므로 테이블 전체를 순회하면서 그래프 탐색을 수행해야 한다. 아무 조건 없이 ..