알고리즘31 [알고리즘] 2020 카카오 인턴십 - 보석 쇼핑 (Two Pointers Algorithm) 1. 문제 이번 문제는 2020 카카오 인턴십에 출제된 보석 쇼핑이라는 문제이다. 2. 문제 풀이 처음에 어떤 알고리즘과 자료구조를 사용해야할지 감을 못잡아서 제대로 접근을 하지 못했었다. 이번 문제는 하나의 1차원 배열에서 left, right를 0으로 두고 left와 right를 조작해서 원하는 값을 찾는 투포인터스 알고리즘(Two Pointers Algorithm)문제이다. 1. 우선 현재 map에 들어있는 보석의 종류가 gems에 들어있는 보석의 종류보다 작을 경우 right를 1씩 증가시켜주면서map에다가 넣는다. 2. map에 들어있는 보석의 종류가 gems에 들어있는 보석의 종류와 같을 경우 left를 하나 증가 시켜주고 map에 들어있는 보석의 개수가 0개이면 map에서 해당 key를 삭제.. 2021. 1. 13. [알고리즘] 프로그래머스 - 섬 연결하기(탐욕법) 1. 문제 2. 문제 풀이 1. 각각의 섬이 다리로 연결된 비용을 map 배열에 저장한다. 2. 시작 섬으로 0번째 섬을 방문 했다고 표시해준다. 3. 모든 섬을 방문 하지 않았다면 모든 섬을 방문할 때 까지 최소값을 구한다. 4. 현재 방문한 섬들을 기준으로 이 섬과 연결된 다리중 가장 최소값을 선택해서 다리를 newMap 배열에 건설했다고 표시한다. 5. 4번 과정을 반복해서 answer에 각각의 최소값을 더해주고, 모든 섬을 방문하면 답이 나온다. public class Solution { int[][] map; int[][] newMap; boolean[] visit; int answer = 0; public boolean isAllVisit(){ boolean flag = true; for(in.. 2020. 10. 26. [알고리즘] 프로그래머스 - 구명보트(탐욕법) 1. 문제 2. 문제 풀이 보트에는 2명 밖에 타지 못하므로 몸무게가 가장 많이 나가는 사람과 가장 적게 나가는 사람이 탈 경우 가장 많이 탈 수 있다. 사람들을 몸무게 순으로 정렬하고 남은 사람중 가장 많이 나가는 사람과 가장 적게 나가는 사람이 탈 경우 탈 수 있으면 같이 태우고, 같이 못타는 경우는 몸무게가 가장 많이 나가는 사람만 타게한다. import java.util.Arrays; class Solution { public int solution(int[] people, int limit) { int answer = 0; Arrays.sort(people); int s = 0; int e = people.length-1; while(s 2020. 10. 26. [알고리즘] 프로그래머스 - 더 맵게(힙) 1. 문제 2. 문제 풀이 스코빌지수가 가장 낮은 2개의 음식을 뽑아서 새로운 음식을 만들어서 우선순위 큐에 계속 넣어주고, 가장 스코빌지수가 낮음 음식이 주어진 K와 같거나 커지면 몇번만에 K 이상으로 만들었는지 반환해주는 간단한 문제였다. 코드를 보면 크게 설명할게 없다는 것을 알 수 있다. import java.util.*; class Solution { PriorityQueue priorityQueue = new PriorityQueue(); int answer = 0; public int solution(int[] scoville, int K) { for(int i=0;i 2020. 8. 18. [알고리즘] 프로그래머스 - 디스크 컨트롤러(힙) 1. 문제 2. 문제 풀이 최대값이나 최소값을 뽑아내는 우선순위큐(힙)를 이용해서 문제를 풀었다. 우선 요청시간과 처리시간을 저장할 수 있도록 Job 클래스를 만들어서 데이터를 저장하게 하였다. Job의 정렬 기준으로는 처리 시간이 더 작은게 앞으로 오게 하였다. waitQueue에는 현재 시간과 비교해서 하나의 작업이 끝났을 때 요청 시간이 현재 시간보다 작거나 같으면 waitQueue에 저장을 하였다. 주어진 jobs 배열을 요청 시간에 대해서 오름차순으로 정렬한다. 모든 job을 waitQueue에 넣고, 대기큐(waitQueue)에 job이 없을때까지 반복문을 실행한다. waitQueue에 작업을 넣지 않았고, 현재 시간이 작업 요청 시간보다 작거나 같으면 waitQueue에 job을 넣어준다. .. 2020. 8. 18. [알고리즘] 프로그래머스 - 여행경로(dfs/bfs) 1. 문제 2. 문제풀이 처음에 풀때 인접행렬을 이용해서 인접행렬의 방문한 곳은 다시 방문하지 않는 형태로 풀었었다. 하지만 항공사를 여러번 방문 할 수 있기 때문에 인접행렬이아닌, 항공권을 사용했는지를 체크하는 형태로 바꾸었다. 주어진 조건중에 알파벳 순서가 앞서는 경로를 return 하라는 조건을 각 배열을 정렬해야하나 했다가 String으로 방문 가능한 경로를 ','로 이어주고 그 Stirng들을 저장한 list를 정렬하는 방식으로 수정하였다. 1. 출발 항공사가 "ICN"일 경우 그 항공권을 사용했다고 표시해주고 dfs알고리즘을 호출한다. 2. route에 현재 경로를 더해주고, 현재 사용하지 않은 티켓중에 이전 도착지와 현재 티켓의 출발지가 같다면 티켓을 사용했다고 표시하고 dfs 알고리즘을 다.. 2020. 8. 8. 이전 1 2 3 4 5 6 다음
