반갑습니다!

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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[..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 모든 선수와의 승패를 알 수 있다면 순위가 결정될 것이다. 따라서 이 문제의 핵심은 한 선수에 대해서 승패 결과의 갯수가 n-1개이면 순위가 결정된다는 것이다. 따라서 모든 선수의 승패 결과를 만들어줘야하는데, 해당 문제에서는 선수의 수가 최대 100명이므로 플로이드-와샬 알고리즘으로 모든 경우를 구할 수 있다. 따라서 플로이드 와샬 알고리즘을 사용해서 모든 경우의 승패를 표시한 뒤, 갯수를 세어주면 해결할 수 있다. 코드 C++ #include #include using namespace std; in..