Cloud.log

[문제 링크] 👉 https://www.acmicpc.net/problem/1303풀이 방법💡 DFS, BFS 이용 📌 주의할 점가로, 세로 확인하가Solutionfrom collections import dequedx = [1, 0, -1, 0]dy = [0, -1, 0, 1]N, M = map(int, input().split())war = [input().strip() for _ in range(M)]visited = [[0] * N for _ in range(M)]W, B = 0, 0def dfs(i, j, color): cnt = 1 visited[i][j] = 1 queue = deque() queue.append((i, j)) while queue: ..

[문제 링크] 👉https://www.acmicpc.net/problem/5212 풀이 방법 이 문제는 주어진 지도를 미래의 상태로 변형하고, 불필요한 바다 부분을 제거해 가장 외곽의 땅만 출력하는 문제이다. 1️⃣ 초기값 설정dx = [1, 0, -1, 0] # x(행) dy = [0, -1, 0, 1] # y(열) future_map = [["."]*C for _ in range(R)] # 미래 지도 생성지도를 순회하면서 각 X(땅) 주위에 바다가 3칸 있으면 땅이 잠기도록 한다.새로운 미래 지도를 future_map 이라고 하고, 모두 "." (바다)가 담긴 2차원 배열에 생성한다.dx, dy 는 상하좌우 확인에 필요한 좌표이다. 2️⃣ 미래 지도 생성for x in range(R): ..

[문제 링크] 👉https://www.acmicpc.net/problem/5635 Solutionsol.1 (date 함수 사용)from datetime import daten = int(input()) # 학생의 수students = [input().split() for _ in range(n)]# 초기화된 생일 변수youngest_date, oldest_date = date(1990, 1, 1), date(2010, 12, 31)youngest_name, oldest_name = "", ""# 학생들의 생일 비교for name, day, month, year in students: birth_date = date(int(year), int(month), int(day)) if birth..

[문제 링크] 👉https://www.acmicpc.net/problem/2563 풀이💡 100x100 도화지의 각 좌표를 하나의 큰 이차원 배열로 생각하여 해당 위치를 차지하고 있는 색종이 위치를 체크 각 색종이의 좌표에 해당하는 영역을 배열에 표시한 다음, 전체 배열에서 검은색 영역의 넓이를 구하면 된다.  100x100 배열 생성paper 배열을 만들어 도화지의 각 위치에 색종이가 붙었는지 확인할 수 있도록 한다.색종이 붙이기각 색종이의 좌표 (x, y)에서 시작하여, 10x10 크기의 정사각형 영역에 해당하는 paper 배열의 값들을 1로 설정검은 영역 계산모든 행을 순회하며 1로 설정된 영역을 합산하여 검은 영역의 넓이를 구한다. SolutionN = int(input()) # 색종이 수p..

[문제 링크] 👉 https://www.acmicpc.net/problem/2002풀이1️⃣ 차량 진입 순서 기록차량이 진입할 때의 순서를 딕셔너리로 저장하여, 각 차량의 진입 위치를 빠르게 조회할 수 있게 한다.car_in_dict = dict(zip(car_in, range(1, len(car_in) + 1)))  2️⃣ 차량 진입 순서 인덱스 변환차량이 나가는 순서에 따라 각 차량의 진입 순서 인덱스를 리스트로 변환한다. 이 리스트는 나가는 순서를 진입 순서로 매핑한 형태이다.for i in car_out: calc.append(car_in_dict[i])  3️⃣ 추월 여부 확인calc 리스트를 순차적으로 확인하여, 앞선 차량의 진입 순서가 뒤 차량보다 크다면 추월이 발생한 것으로 간주하고..

[문제 링크] 👉https://www.acmicpc.net/problem/1021 풀이💡 카드의 절반 기준으로 문제를 푼다.  빼내려는 카드가 중간 보다 왼쪽에 있을 때 2번 연산을 한다.n_deq.rotate(-1)큐를 왼쪽으로 1만큼 회전 반대로 빼내려는 카드가 중간 보다 오른쪽에 있을 때 3번 연산을 한다. n_deq.rotate(1)큐를 오른쪽으로 1만큼 회전 Solutionfrom collections import dequen, m = map(int, input().split())pop_num = list(map(int, input().split()))n_deq = deque()for i in range(1, n + 1): n_deq.append(i)result = 0for i in p..

[문제 링크] 👉 https://www.acmicpc.net/problem/2161풀이큐 생성 방법from collections import dequequeue = deque()collections의 덱 라이브러리를 import 한다.deque() 를 선언하면 양방향 큐인 덱이 생성된다. 첫 번째 원소를 빼내는 방법queue.popleft()popleft() 는 왼쪽의 첫 번째 원소를 큐에서 빼고 출력한다.pop() 은 오른쪽의 첫 번째 원소를 큐에서 빼고 출력한다. 제일 아래에 있는 카드를 밑으로 옮기는 방법queue.rotate(-1)rotate() 는 큐를 왼쪽 혹은 오른쪽으로 회전시키는 함수이다.인자로 얼만큼 이동시킬지 넘기면 되는데, 이때 그 수가 음수이면 왼쪽으로, 양수이면 오른쪽으로 회전한..

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를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) • all: S를 {1, 2, ..., 20} 으..

9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 설명 돌 N개가 주어질 때, 두 사람(상근이와 창영)이 턴을 돌아가면서 돌을 가져간다. 돌을 1개 또는 3개 가져갈 수 있고, 마지막 돌을 가져가는 사람이 게임을 이기게 된다. (베스킨 라빈스 생각나네?) 게임은 상근이가 먼저 시작하며 두 사람이 완벽하게 게임을 한다고 가정하고, 이기는 사람을 출력한다. 풀이 1. 간단한 풀이 돌이 짝수일 경우 창영이가 무조건 이기는 게임이 되고, 홀수일 경우 상근이가 무조건 이기는 게임이 된다. 따라서 짝수일 때와 홀수일 때를 나누어 푼다. 2. 다이나믹 프로그래밍 알고리즘 적용 다른 풀이 참조(추후에 재풀이 후 설명 예정) Solution 1. ..

2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 설명 N장의 카드가 있는데, 한 장이 남을 때까지 다음과 같은 동작을 반복한다. 1. 제일 위에 있는 카드를 버린다. 2. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 위 과정을 반복하고 나면 한 장의 카드가 남게 된다. 그 수를 구해야 한다. 풀이 Queue 사용 1. 큐 생성 2. 1장이 남을 때 까지 버리고, 옮기는 과정을 반복 반복문에서 popleft()를 이용해 윗 장을 버린다. 첫 번째 카드를 append()를 이용해 맨 ..

11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 설명 정렬되어있는 두 배열 A, B를 합친 후 정렬해서 출력한다. 첫째 줄에는 배열 A, B의 크기 N과 M이 주어진다. (1부터) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 풀이 • 방법 1 - sort() 문자형으로 입력받고 한 리스트에 A, B를 모두 저장한다. 리스트 내에 있는 요소를 모두 정수형으로 변환한다. sort()를 사용해 정렬하고 리스트에서 꺼내 출력한다. • 방법 2 - two ..

10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 설명 문제 : 회원들의 나이 순대로 정렬(오름차순), 나이가 같을 경우 가입한 순으로 정렬(내림차순) 풀이 Sort() 사용 1. 나이와 이름을 리스트에 추가한다. 나이는 정수형으로 변환시킨다. 2. 첫 번째 인자를 기준으로 정렬 즉, 나이순으로 정렬한다. 3. 리스트에서 값을 하나씩 빼내서 출력한다. • 리스트.sort(key=lambda x:x[index]) - index를 기준으로 오름차순 정렬 sort 정리 👇 [자료구조] sort, sorted, 정렬, 이중 ..

11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 설명 부분 수열의 최대 길이를 구해야 하는 문제이다. 부분 수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열이다. 쉽게 말해서 이전 수보다 작으면 수열이 이루어진다. 흔히 수학에서 보았던 두 항의 차이가 일정한 등차수열을 말하는 것이 아니다. 예를 들어, A : { 10, 30, 10, 20, 20, 10 } 이라는 수열이 있을 때, 부분 수열은 A : { 10,..

9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 설명 첫 정삼각형이 1일 때 변의 길이는 1이다. 아래와 같은 그림처럼 나선형으로 삼각형이 이어진다. 만약 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 가 있을 때 10번째 삼각형의 변의 길이는 9이다. N이 주어졌을 때 N번째 삼각형의 변의 길이를 출력하면 된다. 풀이 • Dynamic Programming 문제 피보나치 수열과 비슷하다. 규칙성을 찾아보면 아래 그림에서 1번째와 2번째를 더하면 4번째 값이 나온다. 고로, 4만큼 차이가 난다. 또한, 아래 ..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 설명 부분 수열의 최대 길이를 구해야 하는 문제이다. 부분 수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열이다. 쉽게 말해서 이전 수보다 크면 수열이 이루어진다. 흔히 수학에서 보았던 두 항의 차이가 일정한 등차수열을 말하는 것이 아니다. 예를 들어, A : { 10, 20, 10, 30, 20, 50 } 이라는 수열이 있을 때, 부분 수열은 A : { 10..