CodeAngie

문제주어진 격자 데이터의 전후를 비교하여 주입된 백신이 CPCU-1202 백신인지 판단하는 문제이다.CPCU-1202 백신을 놓으면, 백신이 주입된 조직에서 항체를 생성하고 같은 영역의 조직에 항체가 퍼진다.항체는 조직을 변형시켜 동일한 색상이거나 다른 색상이 될 수 있다. 풀이전체 조직의 영역들 중 색상이 바뀐 영역이 1개이하여야 한다.따라서 조직을 탐색하면서 동일한 영역이 변경된 것인지를 판단하고, 색상이 변경된 영역의 개수를 세어야 한다.BFS나 DFS를 통해 동일한 색상으로 이루어진 인접 영역을 탐색하며 해당 영역이 일관된 색상으로 변경되었는지 확인한다.탐색 중 영역이 다르다면 CPCU-1202 백신이 아님으로 NO를 출력하고,색상이 변경된 영역의 개수가 2개이상이어도 NO를 출력하며,그 외의 경..

문제통로에 음식물 쓰레기가 떨어져 있을 때, 인접한 쓰레기들끼리 하나의 덩어리로 보고 그중 가장 큰 덩어리의 크기를 구하는 문제이다. 인접한 음식물 쓰레기는 상하좌우로 붙어있는 경우를 말한다.풀이이 문제는 인접한 영역을 탐색하는 그래프 탐색 문제이다.BFS나 DFS를 활용해 연결 여부를 탐색하며 덩어리의 크기를 계산하면 된다.먼저 음식물 쓰레기의 영역을 입력받는다.이때, 쓰레기가 없는 상태는 1, 쓰레기가 있는 상태는 0으로 표시한다. (visited를 사용하지 않고 쓰레기가 있는 곳의 방문 여부를 쉽게 체크할 수 있다.)인접 칸을 탐색했을 때, 다음칸으로 이동 가능하면 쓰레기 영역 크기를 늘리고 방문 표시를 해준다.max를 사용해 가장 큰 쓰레기 크기를 갱신한다.Python 코드import sysfro..

문제주어진 구간이 팰린드롬인지 빠르게 판단해 1 혹은 0을 출력하는 문제이다.풀이DP를 사용해 각 구간이 팰린드롬인지 미리 계산하면, 명우의 질문에 대한 답을 빠르게 구할 수 있다.길이가 1인 경우: 모든 숫자는 무조건 팰린드롬이다.길이가 2인 경우: 두 숫자가 같은 경우만 팰린드롬이다.길이가 3 이상인 경우: 양 끝의 두 숫자가 같고, 내부 숫자들이 팰린드롬일 때만 팰린드롬이 성립한다.팰린드롬의 길이가 3인 경우부터 차례로 DP를 사용해 팰린드롬 여부를 계산하면, 내부 구간을 비교할 수 있다.이후 a에서 b까지의 구간에  대해 DP 테이블을 참조해 팰린드롬 여부를 빠르게 출력할 수 있다.Python 코드import sysinput = sys.stdin.readlinen = int(input())arr ..

문제동영상 재생기에 대한 명령어가 주어졌을 때, 알맞게 시간 이동하여 최종 재생 위치를 도출하는 문제이다.명령어는 prev와 next 두 가지가 있으며, 현재 재생 위치가 오프닝 구간이면 자동으로 오프닝 건너뛰기를 실행한다.prev 명령은 현재 재생 위치에서 10 이전으로 이동하는 명령어이며 0보다 작아지지 않는다.next 명령은 현재 재생 위치에서 10 이후로 이동하는 명령어이며 최대 길이보다 커지지 않는다.오프닝 건너뛰기는 오프닝 구간 (op_start ≤ 현재 위치 ≤ op_end)인 경우 op_end로 이동한다.풀이문자열로 주어진 시간을 숫자로 변환하고, 명령어에 따라 시간을 더하고 뺌으로써 문제를 풀 수 있다.mm:ss 가 주어지면 t = mm*60 + ss 로 변환한다.prev 명령어가 주어지..

문제트리는 사이클이 없는 무방향 그래프이며, 두 노드 사이의 경로가 항상 하나만 존재한다.두 노드를 선택하여 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우를 트리의 지름이라고 한다.입력으로는 루트가 있는 가중치가 있는 간선들로 이루어진 트리가 주어지며, 트리의 지름을 구하는 프로그램을 작성해야 합니다.풀이트리의 지름을 찾기 위해 DFS를 활용한다.트리의 임의의 노드 $x$를 기준으로 잡는다.노드 $x$로부터 노드 간 거리를 DFS를 통해 구하고, 거리가 가장 먼 노드 $y$를 찾는다.노드 $y$를 기준으로 노드 간 거리를 다시 구한다.거리가 가장 먼 노드 $z$를 찾는다. 노드 $y$와 노드$z$ 사이의 거리가 트리의 지름이다. (가장 큰 값을 출력하면 된다.)◆ 트리의 지름 증명트리의 지름 양쪽 끝 ..

문제 n개의 보석의 무게(m)와 가격(v) 정보가 주어지고, m개의 가방이 최대 담을 수 있는 무게(c) 정보가 주어졌을 때, 가질 수 있는 보석의 최대 가격을 구하는 문제이다. 이때 한 개의 가방에는 한 개의 보석만 넣을 수 있다. 풀이 우선순위 큐를 사용하여 문제를 풀 수 있다. 보석과 가방의 무게를 비교하고 담을 수 있는 보석이라면 가장 큰 가격의 보석을 담도록 하는 것이다. 먼저 보석의 정보를 얻을 때, 같은 무게를 가진 보석이 다수 존재할 수 있음으로 딕셔너리 자료구조에 담는다. 딕셔너리로 관리하는 것이 메모리가 조금 늘지만 더 빠른 속도를 보여준다. 한 개의 가방에는 한 개의 보석만 들어가기 때문에 보석의 최대 무개(1000000)와 비교해서 넘어가는 것은 최대 무게로 대체한다. 보석의 무게가..

문제오늘 날짜가 주어지고, 약관에 따라 개인정보의 유효기간이 지나 파기해야 하는 개인정보의 번호를 리스트로 출력하는 문제이다. 풀이약관에 따라 유효기간이 다르고 개인정보가 수집된 날짜가 다르기 때문에 만료 기간을 계산하여 오늘 날짜와 비교하면 된다.먼저 약관의 정보는 빠른 속도로 불러오기 쉽도록 dictionary에 담는다.날짜를 일수로 변환하는 to_days 함수를 통해 날짜를 비교한다.(주의) 개인정보 수집 날짜와 약관 유효기관을 더한 일수에 1을 빼어야 유효기간 만료일이다. Python 코드# 날짜를 일수로 변환def to_days(date): y, m, d = map(int, date.split(".")) return y*12*28 + m*28 + ddef solution(today, ..