프로그래머스 검색 결과

해당 글 37건

[프로그래머스](Greedy) 체육복 (C++)

체육복(Level1) 문제 전체문제 보기 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 접근법 이 문제는 Level1 문제 답게 복잡하게 생각한다거나, 특별한 반례를 고민해야하는 문제는 아니다. 아래와 같이 간단하게 해결 할 수 있다. 실제 코딩테스트에서 이런 문제가 나온다면 빠른 시간에 풀수 있어야 하기 때문에 빠르게 문제를 해석하고 구현하는 연습을 하자. 모든 학생들에 대한 벡터를 만들고 체육복에 대한 정보를 입력한다. 모든 학생에 대해서 조회를한다. 만약 체육복을 2벌 가지고 있는 학생이 있다면, 앞에 ..
Algorithms/Greedy 2021. 7. 15. 05:30

[프로그래머스](Graph) 순위(C++)

순위(Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 접근법 이 문제에서 구해야 하는 것은 순위를 알수 없는 선수의 숫자이다. 문제에서 주어진 예시를 그래프와 표로 나타내면 다음과 같다. 문제의 제한사항을 보면 A선수가 B 선수보다 실력이 좋으면 항상 A선수가 이긴다고 했다. 즉 A선수가 B를 이기고, B선수가 C선수를 이긴다면 A선수는 항상 C 선수를 이긴다는 뜻이다. 이러한 규칙으로 위 그래프에서 추론할 수 있는 경기 결과를 정리해보면 다음과 같을 것이다. 1은 2를 이겼고, 2는 5를 이겼기 때문에 1은 5를 이길 것이다. 4는 2를 이겼고, 2는 5를 이겼기 때문에 4는 ..
Algorithms/Graph 2021. 7. 14. 16:47

[프로그래머스](Graph) 가장 먼 노드(C++)

가장 먼 노드(Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 접근법 문제에서 구해야하는 값은 "1번 노드에서 가장 멀리 떨어진 노드의 갯수"이다. 이 값을 구하기 위해 다음과 같이 접근한다. 모든 노드를 1번 노드부터 시작하여 너비우선 탐색(BFS)를 진행하면서, 각 노드에 깊이를 기록한다. 너비우선 탐색은 같은 깊이의 노드들을 먼저 탐색하고 한 단계 깊은 노드를 탐색하기 때문에 마지막 탐색한 노드의 깊이가 가장 멀리 떨어진 노드의 거리가 된다. BFS 탐색이 종료된 이후 마지막으로 탐색한 노드의 깊이와 같은 노드의 갯수를 카운트하여 반환한..
Algorithms/Graph 2021. 7. 13. 10:58

[프로그래머스](DFS/BFS) 단어 변환 (C++)

단어 변환(Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 접근법 각 단어를 하나의 노드로 간주한다면 "변환 가능한 단어"라는 말은 "이동 가능한 노드"라는 개념으로 볼 수 있다. 결국 이 문제는 그래프에서 길 찾기 문제와 본질적으로 같다. 다만, 노드가 알파벳으로 구성된 단어라는 점이 일반적인 길 찾기와의 차이점이다. 때문에 이 문제에서는 임의의 두 노드가 서로 이동 가능한 노드인지를 구분하기 위한 별도의 방법이 필요하다. 문제..
Algorithms/DFS & BFS 2021. 5. 15. 14:32