프로그래밍/코딩테스트
-
[프로그래머스] 입국심사 / Swift프로그래밍/코딩테스트 2021. 6. 15. 02:20
[문제 보기] 더보기 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요. 제한사..
-
[2056번] 작업 / Swift프로그래밍/코딩테스트 2021. 6. 14. 20:06
https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상정렬을 사용해서 풀었다. 위상정렬 결과 자체를 이용하지는 않고 그 과정에서 각 작업에 대해서 인접한 작업을 확인할 때, 인접한 작업에 적힌 누적값이 현재까지 누적된 값 + 인접한 작업 그자체에 걸리는시간 보다 크다면 인접한 작업에 적힌 누적값을 갱신하는 방법으로 가장 긴 경우를 찾았다. 그리고 문제에서 주어진 조건인, 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재..
-
[프로그래머스] 가장 먼 노드 / Swift프로그래밍/코딩테스트 2021. 6. 13. 01:41
[문제 보기] 더보기 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 n..
-
[프로그래머스] 배달 / Swift프로그래밍/코딩테스트 2021. 6. 13. 00:38
[문제 보기] 더보기 N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다. 위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3..
-
[2018 카카오 BLIND 3차] 파일명 정렬 / Swift프로그래밍/코딩테스트 2021. 6. 11. 20:53
[문제 보기] 더보기 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다. 버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 ["img12.png", "img10.png", "img2.png", "img1.png"]일 경우, 일반적인 정렬은 ["img1.png", "img10.png", "img12.png", "img2.png"] 순이 되..
-
[2018 카카오 BLIND 1차] 캐시 / Swift프로그래밍/코딩테스트 2021. 6. 11. 15:01
[문제 보기] 더보기 캐시 지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다. 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다. 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다. 어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오. 입..
-
[LeetCode] 155. Min Stack / Swift프로그래밍/코딩테스트 2021. 6. 11. 04:23
[문제 보기] 더보기 Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. Examp..
-
[2178번] 미로 탐색 / Swift프로그래밍/코딩테스트 2021. 6. 10. 13:44
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS를 이용해서 풀었다. 큐를 사용할 때 직접구현해야하나 하다가 그냥 배열로 사용했는데 통과되었다. import Foundation func solution() -> Int { let direction: [(dy: Int, dx: Int)] = [(-1,0),(1,0),(0,-1),(0,1)] let size = readLine()!.split(separator: " ").map { Int($0)! } let n = size[..
-
[다이나믹프로그래밍] 개미전사 / Swift프로그래밍/코딩테스트 2021. 6. 8. 23:43
[문제 보기] 더보기 개미 전사 문제 (교재 220p) 난이도 ●●○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을의 식량창고는 일직선으로 이어져있다. 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사는 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오. 입출력 조건) 입력 조건 - 첫째 줄에 식량창고의 개수 N이 주어진다. (3 ≤ N ≤ 100) - 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량..
-
[프로그래머스] 2개 이하로 다른 비트 / Swift프로그래밍/코딩테스트 2021. 6. 7. 23:34
[문제 보기] 더보기 양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다. x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 예를 들어, f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다. 수비트다른 비트의 개수 2 000...0010 3 000...0011 1 f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다. 수비트다른 비트의 개수 7 000...0111 8 000...1000 4 9 000...1001 3 10 000...1010 3 11 000...1011 2 정수들이 담긴 배열 numbers가 매개변수..