본문 바로가기

Algorithm/Programmers37

[고득점 Kit(탐욕법)] 구명보트 (Python) 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이 people을 정렬한 상태로 만들어준다. 그 후 left와 right를 두어 현재 가장 가벼운 사람과 무거운 사람을 최대한 같이 태울 수 있도록 해주었다. 먼저 보트에 가장 무거운 사람을 태웠을 때 limit보다 작다면 무거운 사람을 태우고 right 인덱스를 -1 해준다. 그 후 가장 가벼운 사람을 태웠을 때 limit보다 작다면 가벼운 사람을 태우고 left 인덱스를 +1 해준다. 이 때 flag를 사용했는데 만약 flag가 .. 2022. 1. 1.
[고득점 Kit(탐욕법)] 큰 수 만들기 (Python) 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 입력으로 주어진 number를 앞에서부터 탐색하면서 answer에 담아준다. 이때 현재 number의 숫자랑 answer에 담겨 있는 숫자를 하나씩 비교하여(역순으로) 현재 숫자가 answer에 담겨 있는 숫자보다 클 경우 answer의 숫자를 한자리씩 지워나간다. 예제의 "4177252841"로 살펴보면 다음과 같다. 처음 숫자인 4를 answer에 담는다. 이제 1과 answer를 한 자리씩 비교하는데 4보다 작으므로 1을 그래도 담는다. answer에는 41이 담겨져 있다. 7과 answer를 역순으로 한 자리씩 비교한다. 7이 1보다 크므로 answer에서 1을 지운다. k는 1 감소 다음으로 7과 4를 비교하는데 7이 더 크.. 2022. 1. 1.
[고득점 Kit (탐욕법)] 조이스틱 (Swift, Python) 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 풀이 먼저 각 알파벳 별로 A에서 최소 몇 번의 조이스틱 조작으로 해당 알파벳에 도달할 수 있는지를 배열로 만들어줬다. N은 위쪽 아래쪽 모두 13번을 조작해야하고 A에서 N까지는 위쪽으로, N 이후부터는 아래쪽으로 움직이면 최소한의 조작 횟수를 구할 수 있다. 그렇게 입력으로 주어진 name의 각각의 알파벳을 몇 번 움직여야 하는지 구한다. A가 아닐 경우에는 조이스틱 조작이 필요한 인덱스 배열(changeIdx)에 담아둔다. 그 후 cha.. 2021. 12. 24.
[고득점 Kit (이분탐색)] 징검다리 (Swift, Python) 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 풀이 바위가 최대 50,000개까지 있을 수 있고 이 중에서 n개를 제거해야 하는데 n개를 제거하는 경우의 수를 따지면 시간초과가 날 것이다. 이분탐색을 사용하는데 어떤 값을 기준으로 이분탐색을 해야할지 정해야한다. 문제에서 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 구하라고 하였다. 그렇기 때문에 각 지점 사이의 거리를 기준으로 하여 이분탐색을 진행했다. 시작점은 0으로 두고 끝점은 입력 값으로 주어진 distance.. 2021. 12. 14.
[고득점 Kit (이분탐색)] 입국심사 (Python, Swift) 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 풀이 해당 문제가 이분탐색을 활용해야 하는지 여부는 문제의 제한사항을 잘 살펴봐야 한다. 제한사항을 보면 입국심사를 기다리는 사람이 최대 10억명이고 각 심사관이 한 명을 심사하는데 걸리는 시간은 최대 10억분이라고 주어져 있다. 문제에서 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하라고 하였는데 제한사항을 봤을 때 이분탐색을 활용해야 하는 문제라고 생각할 수 있어야 한다(이분탐색 문제라는 것을 알고 풀기 시작했지만!) 어쨌든 문제에서 심사에 걸리는 시간.. 2021. 12. 14.
[고득점 Kit (DFS/BFS)] 여행경로 (python, swift) 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 풀이 dfs를 이용해서 문제를 해결했다. 먼저 "ICN"부터 시작해서 전체 티켓을 체크한다. 티켓을 체크해가며 여행 경로를 담아두고 전체 티켓을 다 사용했을 때 현재 찾은 경로와 이전에 찾은 경로를 비교 하여 현재 찾은 경로가 알파벳 순서가 앞설 경우 찾은 경로를 변경한다. python은 단순히 이전에 찾은 경로 배열과 현재 찾은 경로 배열을 연산자 비교를 통해서 어떤 경로가 알파벳 순서를 앞서는지 알 수 있지만 swift에서는.. 2021. 10. 12.

티스토리툴바