Algorithm175 [고득점 Kit (탐욕법)] 조이스틱 (Swift, Python) 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 풀이 먼저 각 알파벳 별로 A에서 최소 몇 번의 조이스틱 조작으로 해당 알파벳에 도달할 수 있는지를 배열로 만들어줬다. N은 위쪽 아래쪽 모두 13번을 조작해야하고 A에서 N까지는 위쪽으로, N 이후부터는 아래쪽으로 움직이면 최소한의 조작 횟수를 구할 수 있다. 그렇게 입력으로 주어진 name의 각각의 알파벳을 몇 번 움직여야 하는지 구한다. A가 아닐 경우에는 조이스틱 조작이 필요한 인덱스 배열(changeIdx)에 담아둔다. 그 후 cha.. 2021. 12. 24. [LeetCode] 436. Find Right Interval (Swift, Python) Find Right Interval - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 start 배열에 입력으로 주어지는 intervals 배열의 [i번의 start, i]와 같은 형태로 값을 담아주고 i번의 start를 기준으로 start 배열을 정렬한다. 그 후 intervals를 돌면서 end 값에 대해서 문제에 주어진 조건대로 start를 찾아주는 이분 탐색을 진행했다. 코드 [Swift] typealias startElement = (start: .. 2021. 12. 17. 1072. 게임 (Swift, Python) 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 풀이 이분탐색을 사용하여 해결하는 문제. 몇 번의 게임을 더 해야 하는지를 기준으로 잡으면 되는 간단한 문제였다. 간단한 문제인데 정답 비율이 낮았던건 Z를 구할 때 실수 연산에서 발생하는 오차때문인 것 같다. 처음 python으로 문제를 풀 때 Z를 구하는 식으로 다음과 같이 사용했다. Z = math.trunc((Y / X) * 100) 위와 같이 Z를 구했을 때 오답이 나왔는데 Y / X 연산에서 실수 관련해서 오차가 발생하기 때문이라는것 같다. 그.. 2021. 12. 16. [고득점 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. 3055. 탈출 (Swift, Python) 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 물이 차있는 지역과 고슴도치의 위치를 담기 위해 큐를 두 개 만들었다. 각각의 큐에는 좌표(x, y)와 시간(time) 정보가 들어간다. 처음에 입력을 받으면서 time이 0인 값으로 큐를 담아준다. 고슴도치의 위치에서 bfs 탐색을 하면서 시간 정보를 비교해준다. prev_time 변수를 하나 만들어서 이전의 시간을 담아두고 큐에서 값을 꺼낼때마다 둘을 비교해준다. 만약 둘의 값이 다르다면 물을 확장시키는 flood 함수를 호출한다. 물이 차 있는 지역을 담기 위한 .. 2021. 12. 4. 이전 1 ··· 21 22 23 24 25 26 27 ··· 30 다음
