📍개념 1. 다익스트라 최단 경로 알고리즘 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 1차원 리스트로 구하는 알고리즘 음의 간선이 없을 때 정상 작동 기본 다익스트라 코드 O(V^2) import java.util.*; class Node { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getIndex() { return this.index; } public int getDistance() { return this.distance; } } public class Main { public..
📍개념1. 다이나믹 프로그래밍큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법따라서 점화식부터 세운다2. 탑다운 방식재귀 함수를 이용하는 방법메모제이션: 한 번 구한 결과를 메모리 공간에 메모해 두고, 같은 값을 다시 호출하면 메모리에서 꺼내오는 기법. 탑다운 방식에서 사용 가능public static long fibo(int n) { // 종료 조건 if (n == 1 || n == 2) return 1; // 계산한 적 있다면 그 값 반환 if (d[n] != 0) return d[n]; // 계산한 적 없다면 계산 후 값 반환 d[n] = fibo(n - 1) + fibo(n - 2); return d[n]; }3. 보텀업 방식반복..
📍개념 1. 순차탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 리스트가 정렬되어 있지 않을 때 사용 O(N) public static int sequantialSearch(int n, String target, String[] arr) { for (int i = 0; i < n; i++) { if (arr[i].equals(target)) return i + 1; } return -1; } 2. 이진탐색 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 데이터 찾는 방법 데이터가 이미 정렬돼 있을 때 사용 O(logN) 1. 재귀함수로 구현한 결과 public static int binarySearch(int[] arr, int tar..
📖 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 더보기 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 ..
📖 문제 https://school.programmers.co.kr/learn/courses/30/lessons/1844 더보기 문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗..
📖 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43165 더보기 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사..
📖 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42746 더보기 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000..
📖 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42748 더보기 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를..
📍개념 1. 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터와 가장 앞 데이터를 교환하며 정렬하는 알고리즘. O(N^2) public class Main { public static void main(String[] args) { int n = 10; int[] arr = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 }; for (int i = 0; i arr[j]) { min_idx = j; } } // 가장 앞 데이터와 가장 작은 데이터 위치 교환 int temp = arr[i]; arr[i] = arr[min_idx]; arr[min_id..
📖 문제 https://www.acmicpc.net/problem/2331 더보기 문제 다음과 같이 정의된 수열이 있다. D[1] = A D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합 예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다. 이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다. 입력 첫째 줄에..
