Algorithms 검색 결과

해당 글 123건

[프로그래머스] (완전탐색) 소수 찾기 (C++)

소수 찾기 (Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 접근법 이 문제에서 요구하는 것은 최대 7개의 주어진 숫자들로 만들 수 있는 모든 경우의 수 중에서 소수의 개수를 구하라는 것이다. 이 문제에서 고민이 필요한 알고리즘은 소수를 판별하는 방법과, 7개의 숫자로 만들 수 있는 모든 조합의 숫자를 만들 방법이 필요하다. 먼저 소수를 판별하는 방법을 살펴보자. 임의의 숫자 n이 소수인지 아닌지 판별하는 가장 쉬운 접근법은 직접 나눠보는 방법이다. 이문제에..
Algorithms/Brute Force 2021. 7. 22. 10:43

[프로그래머스] (이분탐색) 징검다리(C++)

징검다리 (Level 4) 문제 전체 문제 보기 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 접근법 이 문제에서 요구하는 것은 전체 징검다리 바위들 중에서 n개의 바위를 제거했을 때 "바위들 간격의 최솟값이 가장 큰 값"이다. 어떤 바위를 제거하냐에 따라서 간격의 최솟값이 변할 수 있는데 이중 최솟값이 가장 큰 값을 구하는 것이다. 이 문제는 이분 탐색으로 접근하면 쉽게 해결할 수 있다. 이분 탐색을 활용할 경우, 바위를 제거하는 효율적인 방법이 무엇인지는 신경 쓰지 않아도 된다. 이분 탐색을..
Algorithms/Binary Search 2021. 7. 21. 12:04

[프로그래머스] (이분탐색) 입국심사(C++)

입국심사 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 접근법 이 문제에서 요구하는 바는 가장 효율적인 입국심사 방식을 적용했을 때 모든 사람이 심사를 받는데 걸리는 시간의 최솟값이다. 이 문제를 풀기 위해서 두 가지 방법을 접근해볼 수 있을 것이다. 첫 번째로는 가장 효율적인 입국심사 방식의 메커니즘을 구현하는 방법이다. 방법은 의외로 간단하다. 우선순위 큐를 활용하여서, 모든 심사관들을 우선순위 큐에 "심사가 끝나는 시간을 기준"으로 삽입을 한다. 그리고 다음 사람이..
Algorithms/Binary Search 2021. 7. 20. 12:12

[프로그래머스] (Heap) 이중우선순위큐 (C++)

이중우선위 큐 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 접근법 보통 우선순위큐는 항상 가장 우선순위가 높은 원소를 뽑기 위해서 사용한다. 이런 우선순위 큐에서는 아쉽게도 가장 우선순위가 낮은 원소를 뽑거나 알 수는 없다. 이 문제에서 요구하는 바는 가장 우선순위가 높은 원소를 뽑을 수도, 가장 우선순위가 낮은 원소를 뽑을 수도 있는 이중 우선순위 큐를 구현하는 것이다. 이중 우선순위 큐를 구현하기 위한 자료구조는 반드시 우선순위를 기준으로 정렬되어 있어야한다. 이때 사용하기 좋은 자료구조는 균형 이진트리이다. 물론 배열이나 연결 리스트로도 구현할 수는 있다. 다만 배열과 연결 리스트를 항상 정렬된 상태로 유지하기 위해서는 데이터를 삽입할 때..
Algorithms/Heap 2021. 7. 19. 14:10