문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 재정의 테트로미노가 주어지고, 보드판이 주어진다. 보드판에 최대 몇 칸을 채울 수 있는지 확인하는 문제. 회전을 해서 넣을 수 있다. 문제는 테트로미노가 고정적이 아니라, 보드로 주어진다는 점. 테트로미노를 획득하고, 보드판에 맞는지 확인하는 과정은 어렵지 않다. DFS로 블럭 형태를 결정하고, 이에 맞는 보드판이 있는지 DFS 확인하고 비교하면 된다. 블럭을 어떻게 저장할 것이며 블럭의 회전을 어떻게 구현할 것인가가 핵심인 문제. 상대 좌표로 관리하기 시작 지점을 0, 0으로 계산하고 상대좌표를 계산하..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 재정의 아이템 줍기 문제이다. 사각형이 겹친 형태로 있을 때, 가장 외곽라인들의 총합을 길로 정한다. 이 길에서 최단거리로 목표지점 까지 도달하는 방법을 구하는 문제. 최단거리이고 가중치가 다 동일하므로, BFS로 최단 거리를 구할 수 있다. 겹친 사각형에서 어떻게 루트를 구할 것인가가 관건인 문제. 사각형의..
문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 재정의 트리가 구성되어 있을 때, leaf_node를 세리는 문제이다. 특정 노드 한 개를 삭제하였을 때, 남는 leaf_node의 수를 구하면 된다. leaf_node를 어떻게 다룰지가 핵심인 문제이다. 재귀적으로 leaf_node 조합하기 트리는 재귀적 구조로 구성되어 응용하기 좋다. 특정 노드에서, 자식들의 가진 leaf_node를 더하면 총 leaf를 구할 수 있다. 이렇게 구현하면 한 가지 문제가 생긴다. A라는 노드에서 자식 B 하나를 가진..
문제 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net DDR을 하는데, 에너지를 최소한으로 쓰고 게임을 끝내는 방법에 대한 단순한 문제이다. 재정의 greedy 한가? (탐욕적 선택 속성을 가지는가?) 앞선 선택이 뒤의 선택에 영향을 미치지 않는다면, greedy하게 풀 수 있을 것이다. 현재의 발을 옮겼다가, 뒤 이어 이전 발의 위치만 무한으로 나온다면 손해를 보게 된다. -> greedy하게 풀 수 없다. 완전 탐색 결국 모든 경우의 수를 확인해야 하므로, 완전 탐색을 사..
문제 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 재정의 택배택배 문제는 상대적으로 심플하다. A에서 B로 최단거리로 이동할려면 어느 노드로 가야하는지 구하면 된다. 즉, 최단거리 갱신 타이밍에 가야할 노드도 갱신한다. 미확인 도착지 주어지는 후보노드들의 최단 거리를..
문제 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 재정의 경우의 수를 활용하여 풀려고 하니 쉽지 않았다. 단순 곱사건(동시에 일어나는 사건)이 아니라, 합사건도 같이 일어나기 때문이다. 이는 완전 탐색을 요구하고, 상태 공간의 중복이 발생한다. 그냥 DP를 사용하려고 하니, 상태 공간의 정의가 마음에 들지 않았다. 손으로 작성 해 보니 어떤 상태 공간을 사용할지 찾을 수 있었다. 역시 DP각은 손으로 써서 봐야 잘 보인다. 재귀 함수로 문제 정의하기 완전 탐색을 해야함을 인지 했으니, 일단 재귀 함수로 간단하게 정의를..
문제 & 재정의 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 위 문제는 상하좌우 방향에 인접한 블럭들의 크기를 구하는 전형적인 탐색 문제이다. UnionFind로 탐색하기 탐색이 가능한 것은 (x, y)를 기준으로 (x+-1, y)와 (x, y+-1) 총 4개의 경우로 탐색이 가능하다. 이 상하좌우 인접을 하나하나 탐색하는게 아니라, 각각의 그룹으로 묶을 수 있다면? 그룹별 크기를 구하는건 자연스럽게 할 수 있다. 그룹으로 묶는 방법은 여러가지가 있지만 MST를 구현할 때 사용하는 Un..
문제 2268번: 수들의 합 7 첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는 www.acmicpc.net 재정의 PrefixSum(구간 합)과 갱신을 하는 단순한 문제. N이 10**6이고, M이 10**6이다. O(n*log n)으로 풀어야 한다. M번 만큼의 loop는 무조건 돌아야 하므로, PrefixSum, Update를 O(log n)이하로 풀어야 한다. 누적합을 이용하면 O(1)로 PrefixSum을 구할 수 있다. 하지만 update하는데 O(n)이 들기 때문에, 누적합을 활용할 수 없다. O(log n)으로 ..
문제 & 재정의 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 이전 글인 Greedy에서 상위/하위 호환 처리하기와 동일한 문제이다. Day로 표현하기 일년을 365일이라 칭하는 것 처럼, 일 단위로 표현하는 방법. month_per_day = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] def date_to_sum(month: int, day: int) -> int: return sum(month_per_day[1:month]) + day..
