알고리즘

문제: 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://www.acmicpc.net/problem/5052 풀이 정렬과 트리를 이용하여 풀 수 있는 문제였다. 풀이를 찾아보니 훨씬 센스있는 방법으로 푼 분들도 많았다. (1) 전화번호 정렬하기 N = Integer.parseInt(br.readLine()); String[] phoneNumbers = new String[N]; for (int i=0; i NO를 출력하고 다음 테스트케이스로 넘어감 2. 다음 문자를 검사. 다음 문자가 n이면 다음 노드는 child[n]이 됨 3. 만약 child[n]이 null면 새 인스턴스 할당해주기 4. 다음 노드로 이동 5. 다음 문자가 없다면, 현재 노드의 cnt를 1 증가시키기 위와 같은 알고리즘을 코드로 옮기면 이렇게 된다. boolean..

문제 링크: 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도로 설정하든 똑같기 때문이다. 중요한 건 온도를 올릴지 내릴지이다. 온도 범위 보정 문제에서 주어지는 온도 범위..

문제 링크: https://www.acmicpc.net/problem/10942 풀이 다이나믹 프로그래밍 문제였다. 부분 수열의 팰린드롬 여부를 이용하면 전체 수열의 팰린드롬 여부를 구할 수 있기 때문이다. (1) 점화식 세우기 부분 수열을 이용해 현재 수열의 팰린드롬 여부를 어떻게 확인할 수 있을까? 1. 양 끝 숫자를 제외한 부분 수열이 팰린드롬이고, 2. 양 끝 숫자가 같으면 해당 수열도 팰린드롬이다. 이를 코드로 나타내면 다음과 같다. if(dp[i+1][j-1]==1 && num[i]==num[j]) { dp[i][j] = 1; } 여기서 인덱스 에러를 방지하려면 i+1