본문 바로가기

알고리즘

[백준] 1780 종이의 개수 (Python 파이썬) https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 설명 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종.. 더보기
[백준] 1992 쿼드트리 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 위 링크의 문제 설명을 보고 문제를 이해하기 어려울 수 있는데, 한 구역안에 점들이 모두 같은 숫자로 이루어져있지 않으면 왼쪽 위-> 오른쪽 위-> 왼쪽 아래 -> 오른쪽 아래 순 (지그재그 모양)으로 나누어 나타낸다는 것을 이해하면 쉽다. 풀이 과정 이 문제는 큰 구역을 작은 구역으로 계속 쪼개어 나타내는 분할 정복 문제이다. 문제의 예시처럼, 다음과 같은 배열이 주어졌을.. 더보기
[백준] 2447 별 찍기 - 10 (Python 파이썬) https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 설명 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기.. 더보기
[백준] 2133 타일 채우기 (Python 파이썬) https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 설명 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 풀이 과정 먼저, 벽을 체울 수 있는 경우의 수를 구해보자. 벽의 가로길이가 홀수라면 벽을 가득 체울 수 없다. 예를 들어, N = 1 이라면 아래 한 칸이 남기 때문에 벽을 체울 수 없다. (타일은 2x1과 1x2만 존재하기 때문에) N = 2 일때는 다음과 같이 3가지 경우의 수가 존재한다. N = 4 일 때는 가로를 반으로 나눠 N = 2가 2개 있다고 생각할 수 있다. 그래서 앞의 3가지 x 뒤의 3가지 = 9.. 더보기
[백준] 2098 외판원 순회 (Python 파이썬) https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 설명 자세한 문제 설명은 위 링크를 참조해 주세요 1번부터 N번까지의 도시가 있고, 어느 한 도시를 출발하여 모든 도시를 찍고 다시 출발지점으로 돌아오는데 드는 최소 비용을 구하는 문제이다. 풀이 과정 이 문제는 비트마스킹 + DP + DFS 를 모두 활용하는 문제로 난이도가 있는 문제이다. 각 도시를 방문했는지의 여부는 비트마스킹( 0001, 0002 .. 더보기
[백준] 11723 집합 (파이썬 비트마스크) https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 설명 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제.. 더보기
[백준] 1094 막대기 (Python 파이썬) https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 문제 설명 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다. 지민이가 가지고 있는 막대의 길이를 모두 더한다... 더보기
[백준] 9237 이장님 초대 (Python 파이썬) https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 문제 설명 농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다. 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 .. 더보기

티스토리툴바