https://www.acmicpc.net/problem/7662 문제이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하..
https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 코딩테스트 고득점 Kit의 DFS/BFS 문제다. 코드도 길고 구현이 빡셌지만 아이디어를 생각해내기까지 어렵지는 않았다. for (int i=0;i
https://www.acmicpc.net/problem/2423 2423번: 전구를 켜라 첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다. www.acmicpc.net 문제 선영이는 N × M 직사각형 크기의 전자 회로를 디자인 하고 있다. 회로에는 N × M개의 정사각형 타일이 있고, 모두 직사각형의 변과 평행하다. 모든 타일은 두 개의 마주보는 꼭짓점이 전선으로 연결되어 있다. (그림 참조) 전원은 왼쪽 위 모서리에 연결되어 있고, 전구는 오른쪽 아래 모서리에 연결되어 있다. 전구는 전원에서 전구로 가는 경로가 있을 때만 불이 켜진다. 전구에 불을 켜기 위해서, 선영이는 몇개의..
이분탐색 상한선, 하한선을 구할 때 while 종료조건과 lo/hi를 갱신하는 경우 mid인지, mid + 1인지, mid - 1인지.. 너무 헷갈려서 따로 정리해보려한다. 이분탐색을 수행하기 위해서는 배열이 오름차순 정렬되어야 한다. - 일반적인 이분탐색 (key가 존재하는 위치 반환) static int binarySearch(int[] arr, int key) { int lo = 0; int hi = arr.length - 1; while(lo key) hi = mid - 1; else if(arr[mid] < key) lo = mid + 1; else return mid; } return -1; // key 값이 존재하지 않는 경우 } - 하한선 (key와 같거나 초과하는 값이 처음으로 나타나는 ..
[프로그래머스/자바] 다단계 칫솔 판매 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr seller/amount의 최대 길이는 100,000이기 때문에 판매한 금액마다 부모의 끝까지 올라간다면 시간 측면에서 비효율적이라고 생각했다. 그래서 판매한 금액들을 ArrayList에 저장하고, 리프 노드의 금액 */ 10을 자신의 한 단계 부모에게만 전달하는 방식으로 구현해봤다. 그리고 리프 노드에서 처리가 끝나면 그 노드와 부모의 연결을 끊어주면, 또 다른 리프노드가 생겨나고, 모든 노드가..
https://school.programmers.co.kr/learn/courses/30/lessons/131129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 브루트포스 -> 시간 초과 그리디 -> target이 50이 넘어도, 불을 맞추지 않는 것이 정답인 경우가 존재함. 여러 시도 끝에 .... dp를 사용해서 문제를 풀었다! dp = new int[target + 1][2]; // 0: 다트 수 1: 싱글/불 횟수 for(int i=1;i= 50) { // 불 맞추기 int[] temp = throwDart(n - 50); if((temp[0] ..
https://school.programmers.co.kr/learn/courses/30/lessons/136797 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dp와 BFS를 이용해 풀었다. 처음엔 숫자를 하나씩 DFS로 탐색하고, 현재 손가락 위치에서 왼쪽, 오른쪽을 사용해 해당 depth의 숫자로 갈 수 있는 최소 시간을 BFS로 풀었었다. numbers의 길이가 100000이라 시간 초과가 났었고, 왼쪽 손가락과 오른쪽 손가락 중 더 가까이에 있는 손가락으로 숫자를 누르는 그리디 방식으로 풀었는데 몇몇 테케를 틀렸었다. 그래서 먼저 1~10에서 ..
https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 문제 씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 ..