상담원 인원 코딩테스트 연습 - 상담원 인원 | 프로그래머스 스쿨  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방식각 유형마다 멘토를 한 명씩 배치하고, 남은 멘토들은 한 명씩 for문을 돌리며 어떤 유형에 배치시켰을 때 최종 대기 시간이 가장 적게 나오는지 계산하도록 하였습니다. 대기 시간을 구할 때는 우선순위 큐를 활용해 멘토의 현재 멘토링 종료시간을 넣고, 오름차순으로 정렬되도록 하였습니다. 이를 통해 큐에서 poll된 노드는 가장 빨리 끝나는 멘토의 종료 시간이 됩니다. 큐의 사이즈가 해당 유형의 멘토 수와 같아지면 해당 유형의 모든 멘토가 일을 하고 있는 것이고, 큐의 사이즈가 멘토 ..

2056번: 작업2056번: 작업 접근 방식[그래프정렬] 위상 정렬(Topological Sort) : 네이버 블로그 [그래프정렬] 위상 정렬(Topological Sort)본 게시글에서는 그래프에 대한 선행 학습이 되어있다는 가정 하에 설명이 진행된다. 만일 그래프에 대해 ...blog.naver.com스케줄링 문제의 특성은 방향성은 있지만, 사이클은 없는 그래프라는 점입니다. 이를 DAG(Directed Acyclic Graph)라고 부릅니다. 위상정렬은 이 DAG를 이용한 정렬 방식으로 진입 차수(indegree)의 비 내림차순(=오름차순이지만 두 수가 같을 수도 있음) 순서를 기준으로 그래프를 정렬하는 방법입니다. 진입 차수란 노드로 들어오는 간선의 개수인데, 이 문제를 통해 말하자면 해당 작업을..

2665번: 미로만들기 2665번: 미로만들기  접근 방식가장 적은 검은 방만을 바꾸는 경로 = 가장 적은 검은 방을 지나온 경로입니다.따라서 BFS를 통해 최종 목적지까지 도달하는 경로들 중 지나쳐온 검은 방의 횟수가 가장 적은 경로를 선택해 주도록 하였습니다. 문제에서는 흰 방이 1, 검은 방이 0 으로 주어지고 있는데거꾸로 흰 방을 0, 검은 방을 1로 저장해 두는 것이 이후에 검은 방 개수를 카운팅 하는데 유리합니다. BFS 수행을 위해서는 우선순위 큐를 통해 가장 검은 방을 적게 지나친 노드가 앞쪽으로 오게 해주었습니다.그리고 매 반복마다 우선순위가 가장 높은 노드를 꺼내와 다음 위치를 생성하여 큐에 삽입해 주고, 도착지에 도달할 때까지 이 과정을 반복하게 하면 됩니다. BFS를 수행하셨어도 ..

미로 탈출 명령어코딩테스트 연습 - 미로 탈출 명령어 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방식시작 좌표(x,y : 단 여기서 x는 행, y는 열임에 주의)와 목적지 좌표(r,c)가 함께 주어지므로, DFS를 통해 상하좌우로 움직여서 k번째에 목적지에 도달하게끔 만들어주면 됩니다. 다만, 검사 방식은 단순 DFS만을 사용해도 되므로 문제가 없는 반면, 시간 초과 등에서 발생하는 애로사항 등은 따로 체크해주셔야 합니다. 예를 들어 목표지점에 k번으로 도달하기까지의 모든 경로들을 탐색하게 하면 시간 초과로 인해 실패하게 됩니다. 문제가 사전순으로 빠른 탈출 경로만을 요구..

30689번: 미로 보수 30689번: 미로 보수  접근 방식처음에 떠올렸던 방식은 아래와 같습니다. 1. 각 좌표마다 isVisited 여부를 체크하여 false면 탐색 시작2-1. 다시 돌아오면 최소 비용 산출 → 결과에 합산2-2. 밖으로 나가면 그대로 종료 하지만 이렇게 코드를 작성하면 "틀렸습니다"가 나옵니다. 그 이유는 미로에 갇힌 모든 경우가 완벽한 Circle인 것은 아니기 때문입니다. 이 말인 즉슨, Circle이 만들어지는 딱 그 부분에만 한해서 점프대의 설치 비용을 조사해봐야 한다는 것입니다.따라서 이를 위해서 루프 내부에 루프를 하나 더 두어야 합니다. 또한 isVisited만으로는, 이미 방문한 노드를 다시 만나게 되었을 때 이것이 탈출로 이어지는지 Circle로 갇히게 되는지 ..

도넛과 막대 그래프 코딩테스트 연습 - 도넛과 막대 그래프 | 프로그래머스 스쿨  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방식마지막에 추가된 35번 테스트 케이스 때문에 황당했던 문제입니다. 우선 도넛, 막대, 8자 모형이 가지고 있는 규칙성이 무엇인지 확인해 보겠습니다.도넛 모형의 경우에는 모든 노드마다 나가는 간선이 1개, 들어오는 간선이 1개씩 존재합니다.막대 모형의 경우, 맨 끝 노드는 나가는 간선이 0개, 들어오는 간선이 1개이고 시작 노드는 나가는 간선이 1개, 들어오는 간선이 0개이며, 이외의 노드들은 나가는 간선이 1개, 들어오는 간선이 1개입니다.  8자 모형의 경우, 중앙..

1461번: 도서관 1461번: 도서관  접근 방식우선적으로 알아야 하는 규칙은 다음과 같습니다. 1. 마지막 책을 운반한 후에는 카운터로 돌아오지 않고 퇴근하므로, 최후에 꽂아놓아야 하는 책은 기준점 0으로부터 가장 멀리 떨어져 있는 책입니다. 2. M개씩 운반하므로, 마지막을 제외하고는 어차피 계속해서 왕복을 해야 합니다. 따라서 최후의 M권을 제외하였을 때, 가장 멀리 떨어져 있는 책부터 M개씩 운반하면 됩니다. 위 사항을 인지했다면, 책의 양수 위치들을 담는 positive 배열과 음수 위치들을 담는 negative 배열을 생성하여, 가장 멀리 떨어져 있는 것부터 M개씩 차근차근 왕복해 주도록 하면 됩니다. (positive중에서 먼 것부터 M개씩, negaitve중에서 먼 것부터 M개씩) 최후..

1253번: 좋다 1253번: 좋다  접근 방식투 포인터를 통해 두 값의 합이 목표와 동일한지 반복 검사하도록 하였습니다. 입력받은 숫자들을 오름차순으로 정렬해 준 후, 가장 작은 숫자의 인덱스(=0)와 가장 큰 숫자의 인덱스(=N-1)로부터 출발하여 두 값의 합이 목표보다 큰 경우에는 큰 숫자를 앞으로 하나 당겨주고, 합이 목표보다 작은 경우에는 작은 숫자를 뒤로 하나씩 밀게 해 주었습니다. 제공되는 수가 양수라면 자기 자신보다 작은 숫자들의 합만 신경 써도 되지만, 여기서는 입력으로 주어지는 숫자들이 정수라는 점에 유의하셔야 합니다. 즉, 음수가 포함되어 있을 수 있으므로, 오름차순 정렬했을 때 자신보다 뒤에 있는 숫자와 앞에 있는 숫자의 합이 자기 자신이 될 수도 있습니다.  또한, 0이 포함되어..

다단계 칫솔 판매코딩테스트 연습 - 다단계 칫솔 판매 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방식각 조직원마다 이익의 10%를 추천인에게 재귀적으로 전달하는 방식의 문제입니다.Map company = new HashMap(); 과 같이 해쉬맵을 통해 인원 정보를 저장해 두면 조직원 명을 통해서 쉽게 Member 노드를 불러올 수 있습니다. 최종 이익 계산은 각 조직원마다 자신의 추천인이 있는 경우에 한해, 이익금의 10%가 재귀적으로 전파되도록 Member클래스 내에 상위 추천인에게 값을 전파하는 메서드를 넣어주시면 됩니다. 저는 아래와 같이 calculate() 메서..

4485번: 녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지?  접근 방식다익스트라 알고리즘을 기반으로 최소 비용이 드는 경로를 찾는 문제입니다.출발지부터 시작하여, 각 이동마다 상하좌우 4개의 선택지 중에 이동이 가능한 선택지를 고르고, 비용 값이 최소인 경로만 계속하여 업데이트 해주면 됩니다. 잃는 양이 적은 경로만 신경 쓰는 이유는 최초로 목적지에 도달하게 되었을 때, 최종 감소량 또한 최소가 되기 때문입니다.  그렇다면 이제 각 단계(1번의 이동)마다 비용이 최소인 경로를 알아야 하는데, 이때는 우선순위 큐를 활용하여 매우 쉽게 해결할 수 있습니다. 다음과 같은 노드 클래스를 만들어 보겠습니다.// 위치 노드 static class Location implements Com..