본문 바로가기

Algorithms

(98)
[Python] Progrmmers 코딩테스트 연습 : 섬 연결하기 (Greedy, Kruskal) ---문제--- 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때..
[Java] 백준 알고리즘 7568 번 문제 : 덩치 (Brute Force) --- 문제 --- 몸풀기용으로 풀기 좋은 ^>^ (허세..) Brute Force 문제 였습니다. 간단히, 값을 입력 할 때, 이전에 입력된 값들과 하나씩 비교를 해가면서 덩치의 등수를 세가는 방식으로 문제를 풀었습니다. --- 코드 --- import java.util.Scanner; public class Bj7568 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); System.out.println(num); int[][] list = new int[num][2]; int[] result = new int[num]; // Input 받기 및 전 사람들과 덩치 비교..
[Java] Progrmmers 코딩테스트 연습 :가장 큰 수 (Array,배열) ---문제--- 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. ---코드--- import java..
[Java] SW Expert Academy 1767번 문제: 프로세서 연결하기 (완전탐색, 백트랙킹) --- 문제 --- [SW Test 샘플문제] 프로세서 연결하기 --- 코드 --- 되추적 ( 백트래킹, Backtracking ) 과 완전 탐색 (DFS) 를 이용해서 문제를 풀었습니다. 1. 가에 있는 코어 빼고, 모든 코어의 좌표 목록을 저장하고 2. 코어 한개씩, 상 하 좌 우 중 라인이 가능한 곳을 차례로 그리고 다음 코어로 탐색을 넘기고 3. 현재 코어에서 라인을 아예 그리지 않는 상황도 다음 코어로 넘깁니다. 4. 이런 식으로 그렸다가 지웠다가 하면서 완전 탐색을 돌려서 최종 값을 저장하고 출력하면 됩니다. import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.LinkedList; impor..
[Java] Progrmmers 코딩테스트 연습 :단속카메라 (Greedy) ---문제---- 문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다. 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다. 차량..
[Java] Progrmmers 코딩테스트 연습 : K번째수 (정렬) ---문제--- 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1 이상 100..
[Java] Progrmmers 코딩테스트 연습 : 디스크 컨트롤러 (Heap) --- 문제 --- 문제 설명 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어 - 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다. - A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms) - B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에..
[Java] 2020 카카오 공채 코딩테스트 문제 : 가사 검색(자료구조/ Trie 자료구조) --- 문제 --- 2020 KAKAO BLIND RECRUITMENT : 가사 검색 제시된 단어들 중 에서, 원하는 단어와 조건이 맞는 경우의 수를 세는 문제 정확도와 효율성을 둘 다 본다는 특징이 있는 문제였습니다. --- 코드 --- 문제를 보고 처음에 딱 든 생각은 완전탐색 이었습니다. queries 에 있는 단어들을 하나씩 가져와서 words에 있는 길이가 같은 단어들을 모두 검사하는 방식 입니다. 정확도에서는 만점을 받았지만, 역시나 효율성에서 막혔습니다 ㅠㅠ 그래서 어떤 방법이 좋을까 생각하다가, 카카오 페이지에 올라와있는 해설을 보게되었습니다. https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/ 2020 신입 개발자..

728x90
반응형