본문 바로가기

대딩192

[프로그래머스 lv3] 다단계 칫솔 판매 풀이 해설서로의 추천 관계를 그래프(트리)로 만들어놓자.특정인 x에 대하여 수익 n이 발생했을 때, 부모 노드인 추천인을 따라가면서 재귀적으로 수익을 분배하면 된다.수익 분배는 n/10만큼씩 부모 노드 방향으로 진행되다가, 더이상 위의 추천인이 없거나 배분할 금액이 없을 때 중단된다.수익을 재귀적으로 분배한 후, enroll 배열에 있는 이름의 순서대로 수익을 나열하여 리턴하면 정답이다.  코드#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;using ii = pair;using iii = tuple.. 2022. 8. 30.
[프로그래머스 lv3] 합승 택시 요금 풀이 해설해당 문제는 2021 KAKAO BLIND RECRUITMENT 기출 문제로 아래 사이트에 공식 해설이 있습니다.2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설 무지와 어피치가 i지점까지 합승을 하고, i지점부터 a, b를 각자 이동할 때, 총 요금은 dist[s][i]+dist[i][a]+dist[i][b] 이다.플로이드 와샬 알고리즘으로 특정 지점에서 특정 지점까지의 최단 거리를 모두 구하자.i = 1부터 i = n까지에 대하여 dist[s][i]+dist[i][a]+dist[i][b]의 최솟값을 찾고 리턴하면 정답이다. (참고하면 좋은 포스트: 최단거리구하기_플로이드 와샬(Floyd Warshall) 알고리즘)  팁해당 문제를 다익스트라 알고리즘으로.. 2022. 8. 30.
[프로그래머스 lv3] 등산 코스 정하기 풀이 해설해당 문제는 2022 KAKAO TECH INTERNSHIP 문제로 아래 사이트에 공식 해설이 있습니다.2022 테크 여름인턴십 코딩테스트 해설 1) 등산 코스는 출발 지점에서 시작하여 쉼터를 지나고(여러개 가능) 산봉오리를 지나 다시 쉼터를 지나고 출발지점으로 와야 한다.이 때, 출발 지점에서 산봉오리를 지난 후 다시 돌아오는 길은 올라갔던 길과 동일하게 내려오면 되므로 출발 지점 -> 산봉오리까지의 경로만 생각하면 된다. 즉, 이 문제는 출발 지점에서 산봉오리까지 도달할 때 최소 intencity를 구하는 문제이다. 2) 산봉오리는 중간에 여러개를 찍으면 안되고, 마지막 하나만 찍어야 한다. 이러한 조건을 만족시키려면, 간선 (x, y)가 주어졌을 때, 출발지점에서는 나가는 그래프만, 산봉오리에서.. 2022. 8. 29.
최단거리구하기_다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘에 대한 이해 - 하나의 정점으로 부터 다른 모든 정점까지의 최단거리를 구하는 문제이다. - 음수 간선이 있는 그래프에서는 사용할 수 없다. - 우선순위큐를 이용한다. V = 6, E = 7인 다음 그래프에 대하여, 정점 1번으로 부터 다른 모든 정점까지의 거리를 구해보자. 1번으로부터의 거리를 저장하는 dist 배열을 구성하고, 우선순위 큐에 1번 노드의 (거리, 노드번호)를 추가한다. 우선순위 큐는 가장 작은 값을 먼저 뱉어내므로, 1번으로부터의 거리가 가장 가까운 노드를 뽑아내면 (0, 1)이 된다. 이 때, 큐에서 뽑아낸 (0, 1)의 정보와 배열의 정보 dist[1] = 0이 일치하므로 1번까지의 거리를 확정한다. 1번에서 이동할 수 있는 노드는 2번 노드 뿐이다. 거리가 확정.. 2022. 8. 29.
[프로그래머스 lv3] 단어 변환 풀이 해설재귀를 이용하여 가능한 모든 경우를 탐색하는 백트래킹 문제이다.현재 단어를 x라고 했을 때, 다음으로 이동할 수 있는 단어는 words에 있는 단어 중 아직 방문하지 않았고, x와 한개의 글자만 다른 단어이다.다음 단어로 이동하면서, 도착한 노드가 target과 같을 때 이동 횟수의 최솟값을 갱신한다.모든 경로를 탐색한 뒤 이동 횟수의 최솟값을 리턴하면 정답이다.  코드#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;using ii = pair;using iii = tuple;int mn =.. 2022. 8. 29.
[프로그래머스 lv3] 여행경로 풀이 해설여러 경로가 있을 때, 사전 순으로 목적지를 선택해야 하므로 tickets을 정렬시킨다. 흔히 dfs는 노드를 중심으로 방문여부를 체크하고 탐색을 진행한다.그런데, 이 문제의 경우 노드가 아닌 티켓을 중심으로 탐색을 진행해야 한다.노드의 경우 여러번 방문이 가능하기 때문에, 티켓의 사용여부를 체크하면서 다음 티켓을 탐색해야 한다. 현재 방문 노드가 x일 때, 출발지를 x로 하는 티켓 중 아직 체크되지 않은 티켓을 사용할 수 있다.tickets[i]를 사용할 때, tickest[i][1]이 다음 목적지가 되므로 tickets[i][1]을 출발지점으로 하는 dfs를 수행하면 된다.가능한 깊이까지 모두 탐색하였을 때, 모든 티켓을 사용하지 않았다면 다음 루트를 고려해야 하므로 flag를 사용하여 모든 티켓.. 2022. 8. 28.
[프로그래머스 lv3] 네트워크 풀이 해설bfs(너비 우선 탐색)을 수행하면 한번에 하나의 그래프를 탐색할 수 있다.visited 배열에 탐색한 노드를 체크할 때, 특정 노드를 아직 체크하지 않았다면 해당 노드를 루트노드로 하는 새로운 그래프를 탐색할 수 있다는 뜻이다.따라서, 모든 노드를 순회하면서 해당 노드가 이미 체크되었는지 확인하고, 체크되지 않았다면 이를 루트노드로 하는 새로운 그래프를 bfs로 탐색한다.새로운 그래프를 순회할 때마다 네트워크 개수를 1 증가시키고 총 네트워크 개수를 리턴하면 정답이다.  코드#include #include #include #include #include #include #include #include #include #include #include #include #include #include #.. 2022. 8. 27.
[프로그래머스 lv3] 순위 풀이 해설n의 입력값이 100이하 이므로, 시간복잡도가 O(V^3)인 플로이드 와샬 알고리즘으로 해결할 수 있다. i가 k를 이길 수 있고, k가 j를 이길 수 있을 때, i는 j를 이길 수 있다.따라서, dp[i][k] == true 이고 dp[k][j] == true 이면 dp[i][j] = true 이다. 위의 사실을 이용하여 이길 수 있는 모든 경우를 구해놓은 뒤, 특정 선수에 대하여 이기는 경우의 수와 지는 경우의 수를 모두 세어보자.특정 선수가 이기는 사람 수를 nwin, 특정 선수가 지는 사람 수를 nloss라고 했을 때 nwin+nloss-1(본인 제외) = n 이면 해당 선수의 순위를 결정할 수 있다. nwin+loss-1 == n인 선수의 수를 카운트하여 리턴하면 정답이다. 코드#includ.. 2022. 8. 27.
[프로그래머스 lv3] 가장 먼 노드 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 1번 노드로 부터 각 노드까지의 최단 거리를 구한 후, 최단 거리가 최대인 노드의 개수를 구하는 문제이다. 1번 노드를 출발지점으로 하여 bfs를 수행시키고, 각 노드를 방문할 때 최단 거리를 기록한다. 1번 노드로 부터 x번 노드까지의 최단 거리를 dist[x]라 할 때, dist[x] 값 중 최댓값을 구하고, 최댓값을 갖는 x의 개수를 리턴하면 정답이다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ii = pair;.. 2022. 8. 27.
[프로그래머스 lv2] 3xn 타일링 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 2x1(1x2) 모양의 직사각형으로 3xn 직사각형을 채우는 경우의 수를 구하는 문제이다. n을 하나씩 늘려가면서 규칙을 찾아보자. 1. n = 1 일 때 주어진 직사각형으로 3 x 1 직사각형을 채울 수 없다. n = 1 뿐만 아니라 n이 홀수이면 무조건 채울 수 없다는 사실을 알 수 있다. 2. n = 2 일 때 3가지 방법으로 채울 수 있다. 즉, d[2] = 3 3. n = 4 일 때 (1) 앞의 두 칸을 먼저 채우고 나머지를 3x2 직사각형을 채우는 방법으로 채운다. (3 x dp[2]) (2) 네 칸을 전역에 걸쳐 채운다. (2) (네 칸을 전역에 걸쳐 채우는 방법은 다음과 같다.) 즉, dp[4] = 3 x dp[2] + 2 4. n = .. 2022. 8. 25.

티스토리툴바