본문 바로가기

코딩 테스트

 (17)
코테 후기 - 재밌는 자연수 n의 합 종류 만들기 코테로 나온 4문제는 다풀었고, 보통 내가 풀려고 했던 문제까지 완성해서 제출하면 보통 후기를 쓰지 않지만 이번 4번 문제는 좀 획기적인 알고리즘 방법을 복습하고자 후기를 써본다. 문제는 이렇다. 자연수 n이 주어질 때 자연수 n을 만들 수 있는 합의 값은 여러가지가 있다. n = 8일경우, 1+1+1+1+1+1+1+1, 2+1+1+1+1+1+1,... 등 많다. 이 자연수 n을 합의 종류를 만들고 그이후 여러가지 과정을 거치지만 그부분은 스킵하고 자연수 n만들기만 설명해보려고 합니다. 애초에 유명한 알고리즘이 있습니다. # 풀이 절차 과정(함수 makePlusNums에 대한 설명) 1. 맨 처음 하나의 수를 리스트에 넣음. 2. 스택에 수를 꺼내면서 꺼낸 수 x가 1이 아니면 x-1를 스택에 넣음 2-..
[고득점 kit]_탐욕법_#3. 큰 수 만들기 (문제 설명) 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24]를 만들 수 있습니다. 이 중 가장 큰 숫자는 94입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 예numberkreturn "1924" 2 "94" "12..
코딩 테스트_1. 방향전환 ( 문제 ) 다음과 같이 "EEESEEEEEENNNN" 방향이 주어집니다. ( E: 동 N: 북, S: 남, W: 서 ) 방향 하나당 100M이며 1의 시간이 걸립니다. 해당 예시로 들면 E방향으로 300M 후에 S로 움직이니 오른쪽으로 움직이는 겁니다 다시 한 번 E로 움직이니 왼쪽으로 움직이는 거지요. 그리고 6번 움직이는데,, 5번 이상 같은 방향으로 움직여야 된다고 판단될 시 100M씩은 내비게이션은 지시를 안 해도 됩니다 ( 문제 풀 때 이부분을 못 봐서 문제를 제대로 못 품 ) 그렇기 500M 움직인 이후에 다시 N방향으로 가니까 왼쪽으로 움직이게 되는 거죠. 결론적으로 출력 결과는 'Time 0:Go straight 300m and turn right', 'Time 3:Go straight ..
[고득점 kit] 프로그래머스 코딩테스트 연습 - [힙] - #1. 더 맵게 ( 문제 설명 ) 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 sc..
프로그래머스 코딩테스트 연습 - [스택/큐] - 다리를 지나는 트럭 (문제) 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6] kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭 0 [] [] [7,4,5,6] 1~2 [] [7] [4,5,6] 3 [7] [4] [5,6] 4 [7] [4,5] ..
백준 1654번 - 랜선 자르기 출처 : 1654번: 랜선 자르기 (acmicpc.net) 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 랜선 자르기 성공분류 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 62091 13596 8802 20.237% 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은..
백준 11725번 - 트리의 부모 찾기 출처 : 11725번: 트리의 부모 찾기 (acmicpc.net) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 부모 찾기 성공분류 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 18862 8013 5971 43.501% 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 ..
백준 2146번 - 다리 만들기 출처 : 2146번: 다리 만들기 (acmicpc.net) 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 다리 만들기 성공분류 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 192 MB 21390 7516 4715 33.060% 문제 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다..
728x90

티스토리툴바