문제 링크 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/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..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42884# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 최대한 중복이 많이 발생하는 구간마다 카메라를 설치해나가면 된다. 시작 시간, 종료시간이 작은 순서로 정렬한 뒤, 현재 route와 다음 route 사이에 중복 구간이 존재하는지 확인한다. 만약 존재한다면, 현재 구간과 새롭게 편입한 route의 중복 구간을 구한 뒤, 다음 route를 통해 또다시 중복구간이 형성되는지 확인한다. 최대한 많은 자동차가 겹칠 수 있는 중복기간..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42885# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 어렵게 생각할 필요 없다. 가장 무게가 많이 나가는 사람 ( == 가장 제한된 합승 조건을 가진 사람) 부터 최대한 사람을 많이탑승 시키면 정답이 나온다. 이를 구현하기 위해 Sort를 진행한 뒤, back에서부터(가장 높은 무게의 사람) 최대한 많은 사람과 합습 시키기위해 가장 무게가 적게 나가는 순서대로 합승 시킨다.( Sort 했기에 역시 Front 부터 쭉) 정답 코..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49191# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 보고 플로이드 와샬이 떠올랐다. A >B 이고, B> C 라면 A>C라는 것은 곧, A 가 1 다리만 걸친다면 B만 이기는 것이지만, 'B' 를 거치면 C 를 이기는 경우의 수를 찾을 수 있기 때문이다. 따라서, i 번 사람이 j 번 사람과 붙어서 이기는가? 에 대해서 아래와 같이 규정하였다. dp[i][j] 1: i가 j에게 이긴다 0: i와 j의 승패는 모른다 -..
