프로그래머스

문제: https://school.programmers.co.kr/learn/courses/30/lessons/214290 경사가 1번 반복되는 경로의 수를 구해서 k번 반복되는 경로의 수를 구하면 되는 문제다. 1. 경사가 1번 반복되는 경로의 수 구하기 한 칸에서 다른 칸으로 폴짝 건너가는 것을 hop이라고 칭했다. dp[startX][startY][endX][endY][hop]: (startX, startY)에서 시작하여 (endX, endY)까지 이동했을 때, d[0]~d[hop]까지의 경사를 만족하는 경로의 수 문제에서 주어진 예제를 예로 들어보자. d = [1, -2, -1, 0, 2]이다. (1,1)부터 (2, 3)까지는 d[0]부터 d[2]까지의 경사 [-1, -2, -1]를 만족하는 경로..

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150366 풀이 처음에는 사용자 정의 클래스를 이용해 풀었는데, 값이 난리가 나서 원시 자료형을 이용해 풀었다. 병합과 분할이라는 키워드를 보고, 유니온 파인드를 떠올렸다. 배열 선언하기 static int N = 50; String[] table = new String[N*N+1]; int[] parent = new int[N*N+1]; 각 셀은 자신의 값과, 부모 노드의 인덱스를 저장해야 한다. 따라서 값을 저장할 String 배열과, 병합된 셀의 인덱스를 저장하는 int형 배열을 선언해주었다. 표의 크기가 50x50으로 고정되어 있으므로 배열의 길이는 50*50+1 = 2501로 설..

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92343 풀이 풀이방향을 잘못 잡아서 고생했다. 처음에는 리프 노드부터 거슬러 올라가면서 양 노드와 가까운 순서대로 높은 점수를 부여한 뒤, 우선순위 큐를 이용해서 풀었다. 그런데 이렇게 하면 1번 노드와 6번 노드가 동일한 점수를 갖게 된다. 2개의 양 노드를 방문할 수 있는 1번 노드가 더 유리한 선택지인데도 말이다. 그래서 이 방법은 틀린 풀이라는 결론을 얻게 되었다. 결국 구글의 도움을 받았고..ㅋㅋㅋㅋㅋ 이런 풀이를 발견했다. 핵심은 방문했던 노드 목록을 저장하는 것이다. 1-3-2 순서로 방문했을 때와 1-2-3 순서로 방문했을 때는 동일한 상태이다. (노드의 방문 순서는 문제..

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/214289 풀이 어쩌다보니 또! DP 문제를 잡았다. DP 좀 그만 잡고 싶은데 고르는 문제마다 DP...🥹 dp[i][j] = i분일 때 j도를 유지하기 위한 최소 소비전력으로 두고 풀어나가면 된다. 현재 시간이 i, 현재 온도가 j일 때 고를 수 있는 선택지는 다음 4가지가 있다. 1. 에어컨 끄기 2. 온도 1도 올리기 3. 온도 1도 내리기 4. 온도 유지하기 문제를 잘 읽어보면 알겠지만 희망온도는 의미가 없다. 현재 온도가 26도라면, 희망온도를 40도로 설정하든 30도로 설정하든 똑같기 때문이다. 중요한 건 온도를 올릴지 내릴지이다. 온도 범위 보정 문제에서 주어지는 온도 범위..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 8번, 18번 테스트케이스에서 자꾸 틀려서 고생했다🥲 풀이 평균 대기 시간을 최소화하는 문제였다. 스케줄링 알고리즘을 기억하는 사람이라면 단번에 SJF(Shortest Job First) 알고리즘이라는 걸 알아챌 수 있다. (증명은 이 포스팅에서 다룰 문제가 아니므로 생략한다.) 현재 작업 큐에 들어온 일 중에 실행시간이 가장 짧은 일을 선택해야 하므로, 우선순위 큐를 이용하면 쉽게 풀 수 있다. 💡SJF(Shortest Job First)란? 작업 소요시간이 짧은 일부터 처리하는 스케줄링 알고리즘..