프로그래머스/Level_313

• 

  [프로그래머스 / Level_3 / C++] 가장 먼 노드 #접근방법 먼저 그래프의 정보를 다 담아놓자 양방향 간선이기 때문에 from 에서 to로 그리고 to 에서 from 의 정보를 저장한다. 이차원 벡터에서 인덱스 3번에 4, 8 ,9 가 붙어있따면 노드 3에서 노드 4, 노드 3에서 노드 8, 노드 3에서 노드 9 로 연결되어 있다는 뜻! 이후 bfs() 를 적용하기 위해서는 queue 를 생성하는데 처음 담아지는 원소의 값은 1이다 왜냐하면 1에서 가장 멀리 떨어지는 노드를 찾는거니까 1이 시작점인거지! 그리고 queue가 빌때 동안 queue의 첫번째 값을 꺼집어내서 그 값에 연결되어 있는 값들을 queue에 다시 붙여준다. 근데 이때 거리도 하나 올려서 거리 배열에 기록해주자. 근데 만약 현재 보고있는 노드번호에 거리 배열을 찾아가보니까 값이 이미 .. 프로그래머스/Level_3 2022. 5. 18.

• 

  [프로그래머스 Level_3 / C++] 최고의 집합 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합 원소의 합이 S가 되는 수 중에 제일 곱이 최대가 될 때가 언제인지 짐작이 오면 된다. S를 N으로 나누었을 때 생성되는 평균값에 가까울수록 곱이 최대가 된다. 예를 들어, S = 86 이고 N = 9 이고, 이 의미는 숫자 9개를 가지고 합을 86을 만들면 된다. N으로 S를 일단 나눠보자. 몫은 9 (평균값)이고 나머지는 5이다. 평균값 9를 N개 만큼 나열 해보자. "9 9 9 9 9 9 9 9 9" 여기에 나머지 값인 5를 가지고 1씩 공평하게 나눠주자. "9 9 9 9 10 10 10 10 10" 이 값들을 곱했을 때 최대가 나온다. #include #include #include using namesp.. 프로그래머스/Level_3 2022. 3. 4.

• 

  [프로그래머스 Level_3 / C++ ] 야근 지수 이 문제를 처음 봤을 때 우선순위 큐가 떠올라야 한다. 야근 피로도를 최소화 하는 그리디한 방법은 눈에 보이는대로 제곱한 수를 최소화 시켜야 한다. 즉, 숫자 간에 오차가 최대한 작게 만들어야한다. 예를 들어 " 3, 3, 5 " 가 주어졌을 때, 2시간의 시간이 주어지면 "3, 3, 3" 으로 만들어야 제곱의 합이 제일 작고 "1, 3, 5" 로 만들면 제곱의 합이 크다는 것을 알 수 있다. 그러므로, 우선순위 큐를 활용해서 존재하는 작업 중 가장 큰 값이 top인 max heap 으로 구성하여 N시간 동안 top에 위치한 작업량을 잠깐 꺼집어내서 한시간씩 빼주고 다시 push 해준다. #include #include #include using namespace std; long long solutio.. 프로그래머스/Level_3 2022. 3. 4.

• 

  [프로그래머스 Level_3 / C++ ] 순위 플로이드 와샬 알고리즘을 활용해서 풀어보자. 해당 알고리즘을 모른다면 맨 아래에 링크에 들어가서 보고 오기를 권한다. 어떤 마을에 A, B, C, D라는 친구들이 있는데, 가끔 친구들과 누가 더 싸움을 잘하는지 장난 삼아 얘기 해볼 때가 있다. 그러다가 A가 B의 눈빛이 마음에 들지 않아서 싸움을 걸었고 이후 주어진 정보에 따라 1대 1로 맞붙기로 한다. A는 B와 싸워서 이겼다. B는 D와 싸워서 이겼다. C는 A와 싸워서 이겼다. A : " D야~ 너는 B와 싸워서 졌으니까 넌 나한테도 져 ㅋㅋㅋㅋ " 즉, A는 D와 실제로 싸워본 적이 없지만 이길 수 있다는 것이다. 실제로 컨디션 좋은놈이 이길테지만 문제에선 그렇게 주어지진 않았다. 그렇다면 우리가 세팅해야할 것은 A가 D를 이겼다고 표시를 해줘야.. 프로그래머스/Level_3 2022. 3. 3.

• 

  [프로그래머스 Level_3 / C++] 멀리뛰기 Level_3인데 너무 쉬운 문제여서 풀이는 생략한다. 아래 코드에서 dp배열이 왜 저렇게 만들어지는 생각해보고 n이 5일때 경우의 수를 펜으로 써보자. 그러면 이해될 것이라고 판단된다. #include #include using namespace std; int dp[2001]; long long solution(int n) { long long answer = 0; dp[1]=1; dp[2]=2; for(int i=3; i 프로그래머스/Level_3 2022. 3. 3.

• 

  [프로그래머스 Level_3 / C++ / 카카오] 불량 사용자 dfs와 비트연산자를 사용해서 풀면된다. #접근방법 user_id 의 사이즈만큼 반복문을 돌리면서 banned_id를 차례대로 비교해가면서 문자열이 성립될 때 dfs를 호출한다. 이때, 방문을 표현하는 v 라는 변수에 v|(1 프로그래머스/Level_3 2022. 3. 3.

• 

  [프로그래머스 Level_3 / C++] 베스트앨범 unordered_map 을 활용해서 정렬을 잘할 수 있는지를 묻는 문제이다. #접근방법 map(장르, 재생횟수, 고유번호) m1 생성 map (장르, 재생횟수 합) m2 생성 m2에 합산한 값 저장한 후 내림차순으로 정렬 m1에 재생횟수의 내림차순으로 정렬하며 재생횟수가 같으면 고유번호 오름차순으로 정렬 m2의 Key 값은 장르의 이름이며 재생횟수의 합이 큰 것부터 작은 것까지 정렬되어있다. 그러므도 m1에서 m2 장르의 이름을 key값으로 가지는 것을 차례대로 보면서 정렬되어있는 고유번호를 2개까지만 answer에 저장하면된다. #include #include #include #include #include using namespace std; bool cmp(pairv1, pairv2){ if(v1.. 프로그래머스/Level_3 2022. 2. 25.

• 

  [프로그래머스 Level_3 / C++] 단어 변환 dfs 문제이다. #접근방법 현재 들고있는 문자열과 words 배열의 문자열들을 하나하나 비교한다. 현재 들고 있는 문자열과 words 배열의 특정 문자열과 비교했을 때 딱 하나만 다를 경우 dfs를 호출한다. 이때 dfs를 호출하기 전에 문자열의 인덱스 번호를 방문처리를 해주고 dfs 호출이 끝난 후 방문처리를 풀어준다. #include #include #include #include int v[50]; using namespace std; vector w; string t; int result = 987654321; void dfs(string s, int cnt ){ if(s==t){ result = min(result, cnt); return; } for(int i=0; i 프로그래머스/Level_3 2022. 2. 25.

• 

  [프로그래머스 Level_3 / C++] 등굣길 dp와 dfs를 활용한 문제이다. 이 문제와 매우 비슷한 백준 문제가 있으니 다음 문제도 풀어보면 좋다. 프로그래머스/Level_3 2022. 2. 25.

• 

  [프로그래머스 Level_3 / C++] 정수 삼각형 dp 배열을 생성하여 풀면 된다. level_3 라기에는 쉬운 문제여서 어떤식으로 접근하는지만 떠올리면 바로 해결할 수 있는 문제이다. #접근방법 위의 예제를 통해서 dp배열을 생성하면 밑의 숫자값으로 세팅된다. 7 10 15 18 16 15 20 25 20 19 24 30 27 26 24 왜 이런 dp 값이 나왔는지에 대해선 아래에 있는 코드를 보고 이해하길 권한다. 즉, 피라미드 구조에서 dp값을 갱신하기 위해서는 현재 위치에서 바로 위에 양쪽에 있는 숫자값중 큰 값을 골라서 더해주면 되는 것이다. * 끝지점일 경우 바로 위의 dp값을 전달받아 현재값을 더해준다. #include #include #include #include using namespace std; int dp[500][500]; in.. 프로그래머스/Level_3 2022. 2. 25.