반갑습니다!

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 참여 선수 배열의 크기가 완주 선수 배열의 크기보다 항상 1만큼 크다. 따라서 이를 이용해서 해결하면 된다. 아래의 코드는 참여 선수의 이름을 Key로, 참여 선수 이름의 갯수를 Value로 하는 맵을 통해 해결했다. 참여 선수 배열을 순회하며 맵에 저장하고, 완주 선수 배열을 순회하며 맵의 Value를 1씩 감소시킨다. 이 때 Value가 0이 되는 경우 맵에서 삭제시킨다. 이렇게하면 모든 배열을 순회했을 때 맵에 남아있는 Key 값이 완주하지 못한 선수가 된다. 코드 C++ #include #incl..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해당 문제에서는 설치할 기지국의 개수가 중요하다. 어느 지점에 설치하는지는 몰라도 되기 때문에 개수만 구하는 방법으로 해결했다. 이미 설치된 기지국은 크게 3종류로 나눌 수 있다. 첫번째 기지국 마지막 기지국 나머지 기지국 이렇게 3종류로 나눈 이유는 각 기지국 사이에 새로운 기지국을 설치해야하는데, 첫번째 기지국과 마지막 기지국의 전파 도달 거리가 아파트를 벗어날 수 있기 때문이다. 따라서 각각의 케이스를 나눠주었다. 그렇다면 이제 각 기지국 사이에 몇 개의 기지국을 지을 수 있는지에 대해 알아보자. ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 그래프의 최단 거리를 계산해서 해결하는 문제이다. 따라서 최단 경로 알고리즘을 사용하면 해결할 수 있을 것으로 보이는데, 해당 문제에서 N이 최대 50이므로 간단한 플로이드-와샬 알고리즘을 사용해서 해결했다. 이 문제에서 플로이드-와샬 알고리즘을 사용할 때 주의할 점은 a에서 b로 가는 경로가 여러 개일 수 있다는 점이다. 따라서 인접 배열을 만들 때, 해당 경로에 대한 최솟값으로 만들어줘야한다. 코드 C++ #include #include #define MAX 987654321 using namespa..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 처음 봤을 때, C++ 기준으로 next_permutation()을 사용해서 해결할 수 있을 것이라 생각했지만, n이 20이하의 자연수이므로 효율성 테스트를 통과할 수 없다. 해당 문제는 k번째 방법만 알면 되기 때문에 순열의 모든 경우를 구할 필요 없이 해당 경우만 구해주면 된다. k번째 방법은 첫번째 자리 숫자부터 어떤 숫자가 들어갈지 계산을 통해 구할 수 있다. 예를 들어 n이 5이고, k가 107이라고 해보자. 우선 n이 5이므로 줄 서는 방법은 총 5! = 120 가지가 된다. 총 120..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 동적계획법을 사용해서 해결했다. 해당 문제는 2차원으로 생각해보면 규칙이 보인다. n = 5, money = [1, 2, 5] 인 경우를 살펴보자. 가로 줄은 금액, 세로 줄은 동전의 종류이다. 위의 표를 dp[][]라고 하고 가로줄을 j, 세로줄을 i, 새로 추가되는 동전의 금액을 w라고 했을 때, 위의 표를 보면 w == j 가 되는 순간부터 값이 달라지는 것을 알 수 있다. 조금 더 자세히 살펴보면 w == j일 때는 dp[i][j] = dp[i-1][j] + 1이 되고, w < j 일 때는 dp[..