구간 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://school.programmers.co.kr/learn/courses/30/lessons/67260 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 그래프에서, 각 노드간의 "순서" 에 관한 내용에서 위상정렬 문제임을 캐치했다. order의 내용을 각각 indegree, outdegree 배열에 저장했다. indergree[x]: x를 방문하기전 방문해야하는 노드 수 outdegree[x]: x를 먼저 방문해야 도달가능한 노드를 list로 저장. 양방향 edge를 ArrayList 배열로 구현하고, 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,..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42897# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 우선 해당 문제는 레벨4를 책정받았는데, 이것에 너무 홀려서 어렵게만 생각하지말자. 우선 '원형' 이라는 것을 배제하고 일열로 늘어 놓는다고 가정했을 때, x번째 값을 선택한다면 x-1번째 값은 선택할 수 없다. 따라서, 'x-1번째 값을 선택하는 경우의 수'를 따지거나. 'x-2번째와 x번째를 선택하는 경우의 수' 이 두가지를 고려해서 dp를 설계하면 된다. 따라서, 아래..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42583# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 이 문제의 경우, 먼저 들어간 트럭이 나가는 구조상 Queue가 적합하다. 하지만, '트럭이 진입하는 시점', '트럭이 나가는 시점' 을 잡는 것에서 헷갈릴 수 있는 포인트가 많다. 나는 기본적으로 만약 트럭이 바로 다리 위로 올라갈 수 있다면, 현재 시간 + 다리 길이로 해당 차가 나오는 시간을 구하고 Queue에 {무게,나가는 시간} 을 저장했다. 만약 현재 시간에 다음..
getline은 문자열의 delimiter 를 추가하여 문자열의 종료를 구분짓는 메소드이다. 기존의 문자열을 '\0' 혹은 '\n' 과 같이 줄바꿈, 혹은 공백에 의해 String의 종료를 감지하지만, 여기서 특정 char 타입 값을 추가하여 추가로 구분 지을 수 있다. 이를 통해 C++ 에서 문자열 Split함수를 쉽게 구현할 수 있다. 코드 예시 #include #include #include #include using namespace std; vector split(string str) { //str= "ab:cd:eh" stringstream ss(str); vector v; while (getline(ss, str, ':')) { // 주의! 구분자는 string이 아닌 char 타입 이어야한..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제해설 입력으로 N=3 이 주어지면, 사용할 수 있는 숫자는 3,33,333,.....,333333333( 최대 9개의 N사용 가능 ) 이다. 이 숫자들을 통해 사칙연산을 일정 횟수 수행하여 만들어지는 수들을 set에 저장해나간다. 여기서 "몇개의 N" 을 사용해서 구해지는지를 알아야 최소 값을 찾을 수 있기에, "몇개의 N으로 만들어진 수인가?" 에 대해서도 구해야한다. 처음에는 d..
