𝐀𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42897 1. 시간 초과 코드 (Java)(1) 코드class Solution { public int solution(int[] money) { int answer = 0; int N = money.length; int[][] dp = new int[N+1][2]; for (int i=2; i (2) 채점 결과 처음에는 자바로 제출했는데, 시간복잡도가 O(N)인 코드를 제출했음에도 시간 초과를 받았다🤯알고리즘의 문제인가? 싶어서 같은 코드를 C++로 만들어서 제출해봤다. 2. 통과 코드 (C++)(1) 코드#include #include..

문제: 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/118669 2022 카카오 인턴십 기출이다. 출입구에서 출발하여 산봉우리 한 곳을 찍은 뒤 원래의 출입구로 돌아와야 한다. 주어진 간선들은 모두 양방향이기 때문에, 산봉우리에 올라갈 때와 산봉우리에서 내려올 때를 구분하지 않고, 편도 코스의 최소 intensity만 구해주면 된다. (올라갈 때의 intensity) < (내려올 때의 intensity) 라면, 올라간 코스 그대로 내려오는 것이 더 이득이기 때문이다. 여기서는 산봉우리를 출발점으로 잡고, 내려올 때 기준으로 intensity를 구했다. 출발점에서 최소 intensity를 갖는 출입구 노드를 찾아야 하고, 간선에 가중치가 존재..

문제 링크: 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..