본문 바로가기

Algorithm/프로그래머스 고득점 Kit

[고득점 Kit] 문제 풀이를 마치며...
2022. 3. 30. 첫번째 바퀴 - 21년 6월 동기와 첫 스터디 회사동기들과 무작정 시작했던 알고리즘 공부. 일주일에 한 챕터씩 매주 머리싸매고 고통중에 답 안보겠다고 말하면서 일주일간 고민하다가 몰래 정답 찾아가며 알고리즘 문제를 접하고 풀었었다. 그렇게 10개 쳅터를 3달간 풀면서 우리는 알게모르게 많은것들을 학습할 수 있었고, 다양한 부분에 확장해가면서 무지했던 자바문법과 개념들을 학습해나가는 시발점이 되었다. 이 첫 스터디를 시작으로 자바 8을 쓰는 자바 개발자로 재직중이면서도 Stream, Lambda, Optional, Collections, Generic 등에 굉장히 무지했던 내 자신을 부끄러히 여기고, 자바 문법을 다시 점검하고 공부하면서, 무지해서 더 많은 공부의 필요성을 느끼며, 동력을 얻을 수 있었다...
[Heap] 이중 우선순위 큐 - Java코드
2022. 3. 25. https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 문제 이해 우선순위큐를 최소값 정렬과 최댓값 정렬로 2개를 만들면 쉽게 풀 수 있다. 풀이 import java.util.Collections; import java.util.PriorityQueue; import java.util.StringTokenizer; class Solution { public static int[] solution(String[] operations) { int[] answer = new int[2]; //최소 힙, 최대 힙 PriorityQueue pq = new PriorityQueue(); Priority..
[Heap] 디스크 컨트롤러 - Java코드 ★★★
2022. 3. 25. https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제 이해 반가운 개념이 나타났다. (OS시간에 배웠던 SJF 방식) 입력으로 작업의 요청시간과 수행시간이 들어온다. 가장 짧은 Job부터 스케줄링하면 각각의 Job이 요청시간으로부터 대기시간과 수행종료 시점까지의 시간의 총 평균시간이 가장 짧은 스케줄링 기법이다. 해당 기법을 Java로 짜보는건 처음이지만, Heap을 이용해 정렬된 요청시간과 대기시간을 ..
[Heap] 더 맵게 - Java 코드
2022. 3. 24. https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 문제 이해 정렬의 개념이 필요하다. Heap (PriortyQueue) 자료구조에 들어가므로 오름차순 정렬되는 특성을 이용하여 매개변수로 받는 스코빌지수가 정렬되면, 첫번째 원소(peek)가 K를 만족하는지 체크하면서 poll() 를 통해 가장 맵지 않은 두 원소를 차례로 빼서 새로운 조합을 다시 힙에 넣어주며 풀면 된다. 풀이 import java..
[스택/큐] 주식가격 - Java 코드 ★★★
2022. 3. 3. https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 문제 이해 각 원소의 유지되는 시간은 한 인덱스당 1초이다. 마지막 원소의 유지시간은 무조건 0이다. 배열을 사용한 풀이 완전탐색을 이용하면 보다 직관적이고 수월하다. class Solution { public int[] solution(int[] prices) { // 완전탐색은 n2 순회 int[] res = new ..
[스택/큐] 다리를 지나는 트럭 - Java코드 ★★★
2022. 3. 3. https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr 문제 이해 다리에 트럭이 선입 선출되는 문제이므로 FILO이 아닌 FIFO에 큐를 이용한다. 큐에 들어간 무게합은 wegith보다 작은지 검사하면서 다리라는 Queue를 활용하여 무게의 합을 관리하면서 초를 재야한다. 설계 문제 체감상 Lv2가 아닌 Lv3정도는 되는것 같다. 다리의 길이만큼을 가지는 Queue를 설계하고 싶었지만, 큐..
[스택/큐] 프린터 - Java코드
2022. 2. 22. https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 문제 이해 문제를 보면, 해당 location에 있는 문서가 몇번째로 출력되는지를 구하는문제인데, 차례대로 우선순위를 확인하여 , 우선순위가 아니면, 작업을 맨뒤로 보내버린다. 즉. 선입 선출 구조의 큐를 이용해야 한다. Peek 작업이 Queue가 가지는 max값(최고 우선순위값)이 아니라면 맨뒤에 넣어주는 작업을 하면서, 해를 구하면 되겠다. 풀이 입력으로 들어..
[스택/큐] 기능개발 - Java코드
2022. 2. 22. https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 문제 이해 문제를 상세히 읽어보면 각각의 일률을 구할 수 있고, 들어온 순서대로 종속적인 업무이기 때문에, 앞에서 배포가 되지않으면 뒤에 업무가 완성되어도 배포할 수 없다. 이 문제는 선입 선출로 순서배포가 일어나는 구조이기때문에, 스택이아닌 큐 자료구조를 이용한다. 일률을 큐에 저장하고 peek값에 일률보다 작거나 같은것들을 count해주면서 함께 배포..
[그래프] 방의 개수 - Java코드 ★★★★★ 매우 어려움
2021. 8. 26. https://programmers.co.kr/learn/courses/30/lessons/49190?language=java 코딩테스트 연습 - 방의 개수 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr 문제 설계 오랫동안 생각해보면서 설계에 결론을 내렸다. 1. (0,0)에서 계속적인 좌표값이 반드시 필요하다. 2. 어디로 이동했는지에 대한 방향정보가 필요하다. (방향정보를 저장하지않더라도, 다음좌표에대한 연결정보가 필요) 3. 새로운 간선으로 좌표에 두번째 접근시, 방이 생긴다! (HashSet에 지나가는좌표를 저장해줘야 함) + 위에 세가지가 핵심이지만, 대각선에 대해서도 생각을 해야한다. 뱀처럼 끊어지지않..
[그래프] 순위 - Java코드
2021. 8. 26. https://programmers.co.kr/learn/courses/30/lessons/49191?language=java 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 문제 문제 이해 입출력 설명에 집중할 필요가 있다. 문제가 실질적인 경기와 다르게 계산된다. 승패라기보다 절대적 전투력 정도로 생각해야 될 것같다. 먼저 A->B , B->C이면 A->C도 성립한다. 설계 질문하기란에서 보니 다엑스트라, 플로이드 워셜 알고리즘을 쓴다는 말이 많지만, 모르니깐 원초적인 접근으로 풀어보겠다. 승패여부를 기록할 NxN 크기의 매트릭스를 만들어서 승 1 , 패 -1 자신은 0으로 초기화해준다. ex> n=5, resu..
[그래프] 가장 먼 노드 - Java코드 ★★★
2021. 8. 26. https://programmers.co.kr/learn/courses/30/lessons/49189# 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제 설계 그래프 탐색은 이미 bfs, dfs 파트에서 하였다. 이문제는 1에서 시작해서 넓이 level을 중심으로 단계적 탐색이 이루어져야 하므로 bfs문제로 보았다. 1로 부터 단계적으로 넓이중심에 탐색을 진행하면서, 반복적으로 진행해야하므로 Queue를 이용해서 1을 기준으로 단계별로 저 add, poll를 반복해준다 여기서 순회한 간선에 대해서는 배열 flag를 이용하거나, set을 이용해주면 되는데, 나는 set 자료구조..
[이분탐색] 징검다리 - Java 코드 ★★★★
2021. 8. 18. https://programmers.co.kr/learn/courses/30/lessons/43236?language=java 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 레벨 4지만 정말 어려웠다. 문제 이해 예제를 기준으로 다시 정리해보면 0 ~ 25 사이거리에 [2,11,14,17,21] 위치에 돌들이 존재하는 상황이며, 0 ~ 25 사이에서 어떤 위치값이 N개의 돌을 제거 했을때, 가질수 있는 최소 거리값들 중 최대값일까?이다. 예제와 같이 5개의 돌의 위치가 주어지면, 돌과 돌사이거리..
[이분탐색] 입국심사 - Java코드 ★★★
2021. 8. 17. https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제 이해 몇 분이 가장 최적의 시간인지를 찾으면 된다. 시간을 탐색할 범위는 1 ~ N x times[LastIndex] 이다. 이 범위 안에서 이분탐색을 통해, 해당시간에 n명을 만족하는 경우를 찾아 반환해주면 된다. 주의 문제에서 input의 범위는 n은 총 10억명까지, 대기시간은 총 10억 분까지도 들어올수있다. 이분탐색의 맨 우측 끝값이 최악의 경우 1..
[DFS/BFS] 여행경로 - Java코드 ★★★
2021. 8. 12. https://programmers.co.kr/learn/courses/30/lessons/43164?language=java 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제 풀이 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; class 여행경로 { /* 테스트 1 〉통과 (78.43ms, 106MB) 테스트 2 〉통과 (8.62ms, 81.2MB) 테스트 3 〉통과 (..
[DFS/BFS] 단어변환 - Java코드 ★★
2021. 8. 11. https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 설계 DFS / BFS 을 통해 결과를 구하는 로직은 어렵지 않지만, 여러가지 클래스와 인터페이스의 존재를 알고 사용하는것이, 간결하면서도 효율적인 코드를 만들 수 있다고 생각되므로 Stream() 클래스에 대해서 좀더 공부해야할것같다. 풀이 import java.util.ArrayList..
[DFS/BFS] 네트워크 - Java코드
2021. 8. 11. https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 설계 노드별 간선의 연결여부가 네트워크수를 결정 짓는다. Top으로부터 연결된 아이들을 제거해가면서 네트워크수를 Count해주면 될것 같다. 나는 computers[i][i]값이 무조건 1이라는 속성을 이용해서 Flag로 활용하여 이미 연결된 네트워크라는 것을 확인 할때마다 0으로 바꿔주었다. (잘못된) 풀이 class Solution { static..
[DFS/BFS] 타겟넘버 - Java코드
2021. 8. 11. https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 설계 쉽습니다. 사칙연산도 2개만 존재하고, 이전에 동적계획법에서 N으로의 표현문제를 풀었었기에, 비슷하면서도 난이도가 낮은 DFS로 판단하고 풀었습니다. 결과를 저장하는 answer 변수를 전역으로 선언하여 반환하지 않는 재귀함수로 구현하여 경우의 수를 순회하였습니다. 풀이 class Solution ..
[동적 계획법] 도둑질 - Java 코드
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제 이해 원형의 구조를 가지기 떄문에 첫번째집을 털면 마지막집을 털수없고, 두번째 집부터 털어야 마지막까지 비교가 가능해진다. 그러므로 두 가지 Case를 나눠서 순회하여 최댓값을 구하고, 두 경우 중 큰값을 반환해주면 된다. 중요한건 DP를 사용해야하므로, 두번의 케이스의 메모이제이션을 위해 Array를 만들어야한다. (두번 돌려면 원본을 훼손하면 안되니깐....
[동적 계획법] 등굣길 - Java코드 ★★★ (설계가 어려움)
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 설계 오른쪽, 아래로만 움직이면서 침수된 판을 제외하고 지나갈수 있는 경로중 최소값 경로의 갯수를 구하는 문제이다. 최단 경로를 구하라 했지만, 사실 어떻게 가도 경로값은 같을수 밖에 없다;; 포인트 경로를 구하는 법은 내머리로 나오지 않았고 한 블로그를 참고했다 M,N의 이차원배열을 선언하고, 경로값을 초기화해주되, 범람지역은 0으로 생각하고 ..
[동적 계획법] 정수 삼각형 - Java코드
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제 풀이 아래에서 부터 순회하면서, 상위노드에 값을 더해주면서 메모이제이션 한다. class Solution { public int solution(int[][] triangle) { for(int i=triangle.length-2;i>=0;i--) { for(int j=0;j

티스토리툴바