문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/181188# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 및 풀이 문제의 요점은 최대한 적은 요격을 사용해 미사일을 전부 제거하는 것이다. 하지만 단순히 최대한 많은 미사일이 겹치는 지점을 우선으로 차례로 제거해나가면 된다(그리디). 이에 한발 더가서, 어차피 모든 미사일은 제거되야하기 때문에, 앞에서부터 순차적으로 가장 많이 겹치는 지점에서 제거해나가도 올바르게 정답을 찾을 수 있다. 해설 겹치는 미사일을 찾아나갈 때, 시작점..
문제 링크 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 문제 풀이 우선 간단하게 생각하면, 방에 도착하고, 해당 방 내에 있는 스위치를 통해 가능한 모든 방의 불을 키면서 나아가면 된다. 하지만, 아래와 같은 경우에 주의해야한다. Q)만약 bfs를 돌다가 불이 꺼진 방에 도착해서 그 지점의 탐색을 종료했는데, 이후에 불이 켜져서 도달 가능해진다면? 따라서, BFS를 통해 불이 켜진 방을 ..
문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 풀이 외부와 2개의 면이 맞닿아 있는 치즈를 매 턴 제거하는 문제이다. 만약 '외부' 지점을 알 수 있다면, 모든 '외부' 지점을 탐색하며 자신의 상,하,좌,우 에 치즈가 있을 경우, 표시를 하여 2번의 표시가 담긴 치즈 블럭이 존재한다면, 2개의 면이 외부에 노출된 것으로 보고 제거하면 된다. 그렇다면 '외부' 지점을 어떻게 알 수 있을까? 이 문제에서 '모눈종이의 ..
문제 링크 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 문제 해설 N의 크기가 6으로, 전체 탐색이 6*6=36밖에 안되고, 장애물의 개수 역시 3개로 고정값이다. 따라서 permutation을 구현하여 장애물을 배정할 임의의 3개의 장애물의 위치를 정하고, 해당 위치에서 모든 학생이 걸리지 않는가? 를 테스트하는 방식으로 구현했다. 정답 코드 #include #include using namespace std; char arr[6..
문제 링크 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 문제 풀이 문제를 유심히 읽어야한다. K 번행성에서 시작해서 모든 행성을 거치는 최단경로를 찾는 것이다. 하지만 주의할 점이 a->b에 경로가 잇더라도, a->c->b와 같이 다른 곳을 거치는 것이 더 빠른 경로일 수 도 있다는 것이다. 따라서 각 정점들간의 최단 거리를 플로이드 와샬을 통해 구하는 것으로 '실제 각 정점간 최단거리' 를 찾은 뒤, 정점 방문 순서의 모든 경우의 수..
구간 dp 기본적인 dp 는 보통 아래와 같이 시작~ 끝지점까지를 구하는 것으로 '전체의 최대 or 최소'를 찾는다. dp[n] => 0~n까지의 최대or 최소 하지만, 이런식으로는 해결하지 못하는 문제도 존재한다. 만약 시작점-끝점이 아닌, '구간'에 대해 최소 or 최대 등을 bottom-up 방식으로 dp로 풀어나가기 위해선 이중배열을 기반으로 구간 dp를 구성해야한다. 구간 dp의 반복문은 보통 아래와 같다. for( 구간의 길이) for(시작점~ 시작점-길이 )// 시작점 선택 -> ( 끝점 = 시작+길이이기에 자동으로 시작~ 끝 구간 선택 가능) bottom-up 을 수행해야하기에, '구간의 길이' 가 커지는 순서로 구성해야한다. 그래야 1~3 구간을 [1~1], [2~2], [3~3], [1..
17780번 문제 링크 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 풀이 우선, 말이 합쳐진 이후에는 가장 위, 가장 아래 2개의 말만 저장하면 된다. ( 가운데의 말은 아무리 위아래를 바꾸더라도 맨 아래에 와서 움직임에 관여 불가 ) 따라서 각 말이 합쳐질 때마다, 적절한 top&bottom을 유지시킨뒤 움직임을 지시했다. 처음에는 queue를 통한 bfs 탐색으로 수행하고, 말이 합쳐질 경우, queue에 추가하지 않아 분기점을 합..
문제 링크 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 해설 기본적인 dp 문제이다. a~b 까지의 합을 구하는 방법을 0~b까지의 누적합 - 0~a까지의 누적합 으로 구하면 매번 구간합을 구하는 시간 복잡도가 j-i 번 -> 2번으로 바뀐다. 정답 코드 #include using namespace std; int arr[100001]; int sum[100001]; //누적합 int main() { int n,..
