공부/알고리즘, 자료구조 13

정렬 알고리즘

정렬을 해결하는 데 여러 알고리즘을 사용하고, 어떤 알고리즘이 어떤 상황에 적절한 상황인지는 판별하기 다소 어렵다. 물론 다음과 같은 표가 있어 어느 정도 유추는 가능하나, 앞서 말한 좋은 상황, 나쁜 상황을 알기에는 부족하다. 그렇기에 직접 자바로 이를 테스트를 진행할 프로그램을 작게나마 만들었다. testcase패키지는 테스트 케이스이며 즉, 상황(문제)을 임의적으로 넣어둔 클래스들이 모여있다. Sort 인터페이스는 모든 정렬 알고리즘의 공통 영역이다. algorithm 패키지는 위 7가지 정렬 알고리즘을 구현한 클래스들이 모여있다. StopWatch 클래스는 시간을 계산할 수 있는 클래스이다. GitHub - iqpizza6349/sort-algorithm Contribute to iqpizza63..

[프로그래머스] 디스크 컨트롤러

※ 해당 문제의 링크는 여기입니다. ※ 3단계 문제인 만큼 굉장히 어려웠던 문제였습니다. 이번 글에는 제한 사항 대신 알고리즘 및 전체 코드만 포스팅하겠습니다. (제한 사항, 문제에 잘 적혀있는 데 또 적는 거 귀찮....) 알고리즘 가장 시간이 짧은 순서대로 일을 처리해야하는 것이 주 목적입니다.하지만 일은 한 번에 하나씩만 처리가 가능하므로일이 끝나고 나서 현재 시간때 이전에 들어온 일들 중 가장 시간이 짧은 것을 다음으로 일을 하며,하나 하나씩 처리해야하는 알고리즘을 가지고 있습니다. 단, 요청 시간. 즉, 언제 들어왔는 지 역시 파악해야하는 문제입니다. 전체 소스코드 import java.util.*; class Solution { public int solution(int[][] jobs) { ..

[프로그래머스] 더 맵게

※ 해당 문제의 링크는 여기입니다. ※ 프로그래머스에서 설명되어 있듯이 "힙을 이용해서 우선순위 큐를 구현할 수 있습니다." 라고 설명되었있습니다. 우선순위 큐와 힙에 대해서 궁금하신 분들은 링크 참조해주세요. 제한사항 스코빌의 길이는 2이상 1000000 입니다. K는 0이상 1000000000 입니다. 스코빌의 원소는 각각 0이상 1000000 입니다. 모든 음식의 스코빌 지수를 K이상으로 만들 수 없다면 -1를 반환합니다. 문제는 레벨 2 치곤 꽤 쉬운 편입니다. (레벨 1에서 이상한 문제를 만난 적이 있어서 일종의 트라우마가 생겨버린 것 같기도;;) 그리고 효율성 테스트까지 있기때문에 시간복잡도도 적당히 꼬아야합니다. (재귀함수를 사용해서는 효율성 테스트를 통과하기 어렵다는 의미입니다.) 알고리즘..

[프로그래머스] 주식가격

※ 해당 문제의 링크는 여기입니다. ※ Queue를 활용하여 문제를 해결하였습니다. ※효율성 테스트가 있습니다. 혼자서 푸실 분들은 유의해주세요.※ 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 문제만 보고 헷갈릴 수 있습니다. 질문하기에 자세히 작성해주신 분이 있으셨습니다. 감사합니다. (링크) 알고리즘 굉장히 간단한 문제입니다. 배열로도 충분히 해결할 수 있는 문제입니다. 하지만 스택으로 문제를 해결하려고 했지만, 스택을 자주 사용해보지 않아 잘 몰라, 그나마 조금이라도 더 아는 Queue로 문제를 해결하였습니다. public int getTimeWhenFalls(int currentPrice, Queue left..

[프로그래머스] 다리를 지나는 트럭

※ 해당 문제의 링크는 여기입니다. ※ Inner Class를 사용해 문제를 해결하였습니다. 제한사항 bridgeLength 길이의 다리가 있고, 정해진 순서에 맞춰 트럭이 건너가야 한다. 트럭마다 무게가 각각 존재한다. bridgeLength길이만큼 트럭을 다리 위로 이동시킬 수 있으나, 다리가 최대로 버틸 수 있는 무게는 정해져 있다. 트럭은 한 번에 1씩만 움직일 수 있고, bridgeLength만큼 전부 움직여야 다리를 완전히 건넌 것이다. 한 번에 하나의 행동만 가능하다. (동시에 트럭을 2대 이상 이동시킬 수 없음) 위 문제에 자세히 설명이 되어있지 않아, 문제를 풀어서 설명하였습니다. 알고리즘 문제를 이해하는 데에 오래 걸렸습니다. 질문하기에서도 많은 분들이 문제를 이해하기 어려워하셨습니다...

[자료구조] 우선순위 큐와 힙

우선순위 큐란, 기존 큐 방식인 FIFO 방식과 함께 우선순위를 정하여 해당 방향으로 정렬을 하는 큐라고 생각하시면 됩니다. 우선순위를 어떻게 지정하냐에 따라서 큐가 바뀝니다. 우선순위 큐는 대부분은 힙을 이용하여 구현합니다. 힙은 완전이진 트리 형태의 자료구조입니다. 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다는 장점이 있습니다. 그리고 이진 탐색 트리(BST)와 달리 중복 값을 허용합니다. 힙의 종류는 2가지 정도가 있는 데, 최대 힙(Max Heap)과 최소 힙(Min Heap)이 있습니다. 이 둘을 판단하는 기준은 아주 단순합니다. 부모 노드 ≥ 자식 노드 (즉, 부모 노드의 key 값이 자식 노드보다 크거나 같은 완전 이진트리) 라면, 최대 힙입니다. 그 반대라면 최소 힙입니다..

[프로그래머스] 프린터

※ 해당 문제의 링크는 여기입니다. ※ 다른 분들이 푸신 방법이 더 좋을 수도 있지만 제가 생각해낸 방법으로 포스팅하도록 하겠습니다. (대부분 Inner Class, Queue 둘 중 하나, 혹은 둘 다 사용하셔서 푸셨습니다. 저 같은 경우에는 Queue만 사용하여 해결했습니다.) 제한사항 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냄 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣음 그렇지 않으면 J를 인쇄 알고리즘 문제를 파악함에 있어 제가 가장 중요하게 확인한 점은 값이 같더라도 위치를 정확하게 파악하는 것이었습니다. 그리고 해당 값을 인쇄, 즉 사라지게 된 후에는 다시 제한사항을 반복한다는 점이었습니다. 그래서 개인적으로 ..

[프로그래머스] 기능개발

※ 해당 문제의 링크는 여기입니다. ※ 배열로 푸는 편이 더 코드가 단순해지지 않을까 생각하였지만 스택/큐 영역인 만큼 이 둘을 최대한 사용하는 것이 맞다고 생각이 들어 Queue를 사용하여 문제를 해결하였습니다. 코드와 알고리즘 로직을 설명하기 앞서 문제에서 주의 깊게 봐야 하는 점들을 먼저 설명하도록 하겠습니다. 제한 사항 배포는 하루에 한 번만 가능하다. 뒤에 있는 기능을 먼저 완성하였다고 바로 배포할 수 없고, 앞에 있는 기능이 완성된 후, 같이 배포하게 된다. 한 번에 몇 개 배포하였는지 카운트를 배열에 저장한 후, 이를 반환해주어야 한다. 테스트 케이스 및 설명도 잘 되어있어 두세 번 정도 읽어보면 금방 이해할 수 있습니다. 알고리즘 로직 일단, 모든 알고리즘 해결 방식은 굉장히 많으므로 제가..

[프로그래머스] 베스트 앨범

※ 해당 문제의 링크는 여기입니다. ※ 다른 분들이 푸신 방법도 보았으나 내부 클래스 만드셔서 하시는 경우가 대부분이었으나 저는 HashMap 3개를 만들어 해결하였습니다. 3가지 조건을 충족하기 위해 HashMap을 만들었습니다. 각각의 HashMap은 장르, 재생 횟수 / 장르, 총 재생 횟수 / 고유 번호, 재생 횟수 로 하였습니다. HashMap songs = new HashMap(); // 장르, 횟수 HashMap heardTimes = new HashMap(); // 장르, 총 횟수 HashMap unique = new HashMap(); // 고유 번호, 횟수 장르를 키로 몇 번 재생한 횟수를 저장을 for문을 사용하여 저장하였습니다. for (int i = 0; i < genres.len..