문제 링크 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..
문제 링크 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의 승패는 모른다 -..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12952# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 이 문제는 dfs를 통한 완전탐색 과정에서, 백트래킹으로, 불가능한 트리의 가지를 가지치기 하여 수행 시간을 감소시켜야만 시간초과가 발생하지 않는다. 나는 이를 위해, 퀸이 8방향 모든 칸으로 이동하는 특성 중 좌, 우 모두 이동 가능한 특성을 활용하여 각 dfs(depth) 에서, depth 번째 행에 퀸을 놓을 수 있는 위치를 찾는 것으로 문제를 해결했다. 퀸을 놓을 행은..
