문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/181188# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 및 풀이 문제의 요점은 최대한 적은 요격을 사용해 미사일을 전부 제거하는 것이다. 하지만 단순히 최대한 많은 미사일이 겹치는 지점을 우선으로 차례로 제거해나가면 된다(그리디). 이에 한발 더가서, 어차피 모든 미사일은 제거되야하기 때문에, 앞에서부터 순차적으로 가장 많이 겹치는 지점에서 제거해나가도 올바르게 정답을 찾을 수 있다. 해설 겹치는 미사일을 찾아나갈 때, 시작점..
문제 링크 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/42883?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 최대 1000000 자리 수 이므로, 모든 가능성을 Combination 구현을 통해 탐색하는 '완전 탐색' 알고리즘을 통해 최대 값을 찾을 시, 시간 초과가 발생한다. 여기서, 1가지 규칙을 찾아 greedy로 문제를 해결할 수 있다. 바로 대소 비교의 특성이다. 9111>8999 아무리 다른 자리의 숫자가 커도, 맨 앞자리가 큰 것이 무..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 dp[a][b]를 시작점에서 (a,b) 지점까지 도달하는 경로의 가짓수라고 가정하자. 시작점에 1을 넣고(제자리에 있는 것 ==1개의 경로) dfs or bfs로 완전탐색을 수행한다. ( 이때, 아래 or 오른쪽으로만 이동하기에, 왔던 길을 되돌아올 일은 없다.) 만약 a,b라는 지점에서 두개의 분기점이 만난다면, (a-1,b) 와 (a,b-1) 지점이 만나게 된다. (아래 ..
https://school.programmers.co.kr/learn/courses/15008/lessons/121686# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 우선, 아무 생각 없이 우선순위, 실행 시간, 입력 들어온 순서, 실행 순서 가 낮은 순으로 우선순위 큐에 넣고 그대로 pop()해가며 답을 구하면 될 줄 알았지만, 이렇게는 해결할 수 없다.( 만약 첫 프로그램이 5초에 종료 되었는데, 가장 우선순위가 높은 프로그램이 8초에 시작한다고 5~8초에 아무도 실행하지 않는 반례가 발생한다.) 즉, 프로그램의 priority가 높고,..
문제 링크 https://school.programmers.co.kr/learn/courses/15008/lessons/121684 풀이 처음에는 완전탐색은 시간초과가 날 것 같아서 뭔가 로직을 써야하나? 생각하다 그냥 조합으로 가능성 전부 돌려서 찾았다. 조건만 정리하면 아래와 같다. - 각 종목마다 1명씩 대표를 뽑는다. - 한사람당 1개의 종목만 출전한다. 따라서, 전체 인원들 중, 각 종목(m개) 의 대표를 중복 없이 선택하면 된다. 단, 누가 어떤 종목을 채택하는지가 중요하기에 "순서 상관있이 선택하는 조합" 으로 생각하고 코드를 구현해도 된다. 따라서 comb라는 재귀함수를 통해 dfs 탐색으로 각 종목(depth)마다, 중복 없이 임의의 학생 1명씩을 선택하는 모든 가능성 중, 최솟값을 찾아..
해당 문제는 주사위 도면을 고정 시키고, 상,하,좌,우 이동시, 각 숫자가 어느 위치로 옮겨 지는지 하나하나 따져서 무식하게 풀었다. //original 2 4 1 3 5 6 //up 6 4 2 3 1 5 //down 1 4 5 3 6 2 //left 2 6 3 1 5 3 //right 2 1 3 6 5 4 포인트는 각 도면의 인덱스는 1,2,3,4,5,6 으로 그대로 고정되기에, 1번, 6번 인덱스 내의 값이 각각 바닥, 천장 값으로 고정되고, 각 움직임에 따라 실제 숫자 값만 바꿔주는 것이다. 정답 코드 #include using namespace std; // 2 //413 // 5 // 6 int arr[100][100]; int dice[7]; //1: 바닥, 6: 천장 int dx[4] = {..
dfs로 전선 연결이 필요한 모든 프로세서 들이 전설을 이을 모든 경우의 수를 따져서 구했다. 여기서, 만약 해당 프로세서가 벽으로 도달하지 못하는 경우를 계산하여 백트래킹( 가지치기) 를 수행하였다. 추가로, 이 문제에선,'모두 연결 가능 할시의 최단 거리' 가 아니라, '최대한 많은 개수를 연결할 시 의 최단거리' 를 구해야한다. 따라서, dfs를 통해 해당 프로세서를 '상','하','좌','우' 로 연결하는 가능성에 더해, '해당 프로세서를 연결하지 않는 가능성' 도 체크해야한다. 예시 위와 같이 입력이 들어온 경우, 우리가 전선으로 연결해줘야하는, 파란 동그라미 표시를한 프로세서에 대해 전선의 연결 가능성을 확인해야한다. 하지만, 맨위의 파랑 원은, 다른 전선들이 연결되면, 필연적으로 벽에 닿을 ..
