힙과 관련된 문제 모음입니다. 힙은 특정한 규칙을 가지는 트리로, 우선 순위 큐를 구현하는 자료구조입니다. ( 최대 힙, 최소 힙) 그래서 대게 해당 문제들은 우선 순위큐를 사용하면 손쉽게 문제 풀이를 할 수 있습니다. 우선 순위 큐를 사용한는 케이스를 제 경험으로 정리하면 아래와 같습니다. 입력의 크기가 너무 커서, 입력과 동시에 정렬이 필요한 문제 ( Level 2 - 더 맵게, Level 3 - 이중우선순위큐 ) 그리디 알고리즘 적용에서 정렬이 필요한 경우 혹은 최대값, 최소값 기준 정렬 ( Level3 - 디스크 컨트롤러 ) 1번 경우에 백준 14729(칠무해)를 연관문제로 보면되고, 2번의 경우에는 컵라면, 순회강연 문제를 함께 참고하면 좋을듯합니다. 입력의 크기가 너무 커서 입력과 동시에 정렬..

프로그래머스 레벨2 문제 중 '예상 대진표'라는 문제입니다. 문제 출처 : 링크 규칙 찾기 풀이 포인트 대진표 계산하는 문제입니다. 계속 틀리던 부분이 '경기를 진행해서 승부가 나는 것 까지' 연산을 해주어야 합니다. class Solution { public int solution(int n, int a, int b) { int answer = 0; while(true){ a = (a/2) + (a%2); b = (b/2) + (b%2); answer++; if(a == b) break; System.out.println( a + " " + b); // 테스트 케이스 7, 9, 27, 33이 틀리네. } return answer; } }

프로그래머스 레벨2 문제 중 '가장 큰 수'라는 문제입니다. 정렬 문제입니다. 문제 출처 : 링크 정렬 풀이 포인트 해당 문제는 제가 풀이를 찾다찾다... 해결이 안되서 다른 분 풀이를 참고하였습니다. 가장 큰 수를 만드는 방법을 먼저 찾아야 됩니다. 주어진 예시를 적절히 배치할 때 큰수로 만들려면 위 그림처럼 만들어야 됩니다. 위 처럼 비교를 하기 위해서는 Interger Type을 비교하는 것이 아니라 String Type을 비교함으로서 간단하게 처리할 수 있습니다. import java.util.*; class Solution { public String solution(int[] numbers) { String answer = ""; String[] str = new String[numbers.l..

프로그래머스 레벨2 문제 중 '모음사전'이라는 문제입니다. 완전 탐색입니다. 문제 출처 :링크 완전탐색 관련 문제 : 아직 못 찾음 풀이 포인트 완전 탐색인데 규칙을 찾아서 연산 횟수를 비약적으로 단축시키는 방법입니다. 기본적으로 A의 배치는 1씩 증가합니다. 다음 모음부터는 자리수마다 781, 156, 31, 6, 1씩 증가합니다. 모음 사전 만드는 규칙이 AAAAA -> AAAAE 이렇게 되는 것은 1씩 증가하기 때문입니다. AAAAA -> AAAEA 는 다섯번째 자리가 1씩 증가하고 네번째 자리가 1 증가했기에 6씩 증가하는 것입니다. 같은 이유로 각 자리의 모음이 다음으로 증가하는 과정에서 위 규칙이 적용됩니다. class Solution { public int solution(String wor..

프로그래머스 레벨2 문제 중 '땅따먹기'라는 문제입니다. DP 기본 문제입니다. 문제 출처 : 링크 DP 관련 문제 : 프로그래머스 '가장 큰 정사각형 찾기' 문제 풀이 포인트 완전 탐색으로 풀이를 시도하게 되면 시간 초과가 발생하는 문제였습니다. 그래서 각 단계별로 진행하는 과정에서 최대가 되는 값을 메모라이제이션 해야되는 문제였습니다. 1행의 경우는 이전 값이 없기에 그대로 메모라이제이션 됩니다. 2행 부터는 1행의 같은 열을 제외한 나머지 값들과 합을 구해보고, 그 합들 중 최대가 되는 값을 저장해야 됩니다. 가령 2행의 4열 값인 8을 보면 이전 행의 5와 합을 할 수 없기에 최대값은 11이 되는데, 메모라이제이션 배열을 보면 해당 값이 최대가 아닙니다. class Solution { privat..

프로그래머스 레벨2 문제 중 '숫자의 표현'이라는 문제입니다. DP 기본 문제입니다. 문제 출처 : 링크 DP 관련 문제 : 프로그래머스 땅따먹기 풀이 포인트 0과 1로만 배열이 되어있기 때문에 정사각형이 되는 지점에서 최대값을 메모라이제이션을 하면됩니다. 정사각형이 되는 지점을 찾는 것은 정사각형에서 오른쪽 아래를 기준으로 위, 왼쪽, 대각선이 모두 1이면 정사각형이라고 판단하면 됩니다. 위 내용을 기준으로 전체를 탐색합니다. 배열의 위치값이 1이면 해당 값을 기준으로 정사각형을 판단하고, 해당 위치의 메모라이제이션 값은 원래 board의 값으로 추출하는 것이 아니라, 메모라이제이션 배열에서 정사각형에 포함되는 값들 중 가장 작은 값 +1을 해주면 됩니다. 위 로직대로 동작하면 위 그림처럼 값이 채워지..