Cloud.log

2312번: 수 복원하기 첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net 설명 양의 정수 N을 소인수분해 한 결과를 출력하는데, 인수와 인수의 수를 출력하는 문제이다. Solution #20:00 - 20:08 #양의 정수 N을 소인수분해 한 결과를 출력해라 #메모리와 시간이 오래 걸리는 코드 import sys input = sys.stdin.readline def res(n): for i in range(2, n + 1): cnt = 0 #인수가 곱해진 횟수 초기화 while n % i == 0: #정수 n이 i로 나누어지면 cnt += 1 #인수가 곱해진 횟수 카운트 n /= i #몫을 n에 저장..

2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 설명 단순히 소수를 구하는 것이 아니다. 에라토스테네스의 체의 원리를 반영하면서 문제를 풀어줘야 한다. 다시 말해 2부터 N까지의 모든 정수 중 제일 작은 수부터 시작하여 그 소수의 배수들을 모두 지워나간다. 지워나갔으면, 안 지워진 가장 작은 수부터 또다시 반복한다. 여기까지가 에라토스테네스 체의 원리이다. 이 문제에서는 소수도 지워야 하고 배수도 지워야 하는데 그 과정에서 K번째로 지워지는 수를 찾는 것이다. 풀이 ➪ 에라토스테네의 체 알고리즘이 궁금하다면? 에라토스테네스의 체 에라토스테네스의 체란? 소수를 찾는 방법으로, 고대 그리스 수학자 에..

2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 설명 M×N 모눈종이에서 K개의 직사각형이 있고, 그 직사각형 부분을 제외한 나머지 영역의 개수와 넓이를 구하면 된다. 풀이 ✓ 그래프 탐색 - DFS로 풀이 Solution #18:35 - 19:17 -> 풀이봄 19:57 제출 import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) #->런타임 에러 방지/재귀 깊이 변경 M, N, K = map(int, input().spli..

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 설명 🌟 문제 핵심 - 안전 영역이 최대인 것을 구하라. 나도 처음엔 무슨 소리인가 했는데, 영역이라는 것을 생각해야 한다. 강수량은 주어지지 않으므로 모든 강수량을 따져야 한다. 다음과 같이 N = 5인 지역이 있다고 하자. 영역은 오른쪽, 왼쪽, 위, 아래가 이어져 있으면 한 영역으로 본다. 만약, 강수량이 0일 때 비가 오지 않음을 뜻하므로 잠기는 곳은 없다. 왼, 오, 위, 아래가 다 이어져있으면 하나의 영역으로 본다고 했으므로 안전 영역은 1이다. 만약, 강수..

7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 설명 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다. 예시) 이름 (몸무게, 키) 덩치..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 설명 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 1로 연결된 곳은 하나의 단지다. (대각선에 집이 있는 경우는 연결된 것이 아니다.) 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 총 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 풀이 ✓ BFS 알고리즘 이용 https://dev-cloud.tistory.com/161 -> 유사한 문제이다. BFS와..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 설명 위 사진은 미로를 나타낸 것이다. 1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸이다. Start칸에서 End칸까지 가야하는데, 지나갈 수 있는 최소의 칸을 구하면 된다. 주황색 형광으로 칠한 곳이 지나갈 수 있는 최소 칸 개수를 센 것이다. 칸 개수를 셀 때 시작칸과 마지막칸도 포함된다. 그럼 이제 문제를 풀어보자! 풀이 BFS 이용 1. 파이썬에서 BFS를 구현하기 위해서는 큐가 필요하다. 따라서 큐를 만든다. 파이썬 덱 모듈 내에 스택과 큐가 내장돼 있어서 사용하기 편한 덱 ..

15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설명 1 ~ N까지 자연수 중에서 M개를 고른 수열을 나열해서 출력하라는 문제이다. 또한 같은 수를 골라도 된다. 풀이 풀이는 간단하다. 1부터 N까지 수를 리스트에 다 담는다. 중복된 숫자도 들어가야 하니 중복순열을 사용한다. 중복순열은 순열과는 약간 다르게, 같은 숫자를 중복해서 담을 수 있다. ✎ itertools 라이브러리에서 product 함수를 import 한다. ☐ product(list, repeat = 뽑을 개수) Solution import s..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 설명 노드 개수를 7개라고 가정하자. 예제 입력에 둘째 줄부터 트리 상에서 연결된 두 정점이 주어진다고 했으니 그림으로 표현하면 다음과 같다. 파란색 숫자는 예제에 입력된 두 정점을 순서대로 연결된 것을 표현한 것이다. 풀이 이 문제는 DFS와 BFS 문제로 풀 수 있는데 필자는 DFS로 풀었다. for _ in range(N-1): a, b = map(int, input().split()) #노드와 연결된 걸 표현하기 위해 인접 리스트에 각각 저장 graph[a].append(b) graph[b].append(a) 위 코드를..

9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x..

10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서..

10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여덟 가지이다. push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를 덱의 뒤에 넣는다. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다...

10709번: 기상캐스터 출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시 www.acmicpc.net 문제 JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다. 각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서..

14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다. 입력 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. 출력 거스름돈 동전의 최소 개수를 출력..

16953번: A → B 첫째 줄에 A, B (1 ≤ A 162 로 바꿀 때, 거꾸로 가보자. 1) 가능한 연산 중 2를 곱하는 것이 있기 때문에 162를 2로 나누어 보는 것을 생각한다. 2) 2로 나눴을 때 나머지가 0이면 그..