JADE's Repository

문제 24174번: 알고리즘 수업 - 힙 정렬 2 2 5 1 4 3(heapify(A, 2, 5)) -> 2 3 1 4 5(heapify(A, 1, 5)) -> 1 3 2 4 5(A[1] A[5]) -> 5 3 2 4 1(heapify(A, 1, 4)) -> 2 3 5 4 1(A[1] A[4]) -> 4 3 5 2 1(heapify(A, 1, 3)) -> 3 4 5 2 1(A[1] A[3]) -> 5 4 3 2 1(heapify(A, www.acmicpc.net 풀이 문제에서 제시하는 다음 수도 코드를 그대로 구현하면 되는 문제이다. 단, K번 교환될때의 배열을 저장하는 부분만 추가해주어야한다. import java.util.*; import java.util.stream.Collectors; publ..

문제 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 위처럼 앞에서 K-1개 만큼을 맨 뒤로 보낸 뒤 맨 앞에 있는 값을 뽑아주면 된다. import java.util.LinkedList; import java.util.Scanner; import java.util.stream.Collectors; import java.util.stream.IntStream; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int..

문제 26008번: 해시 해킹 첫째 줄에 비밀번호의 길이 $N$과 문자 종류의 개수 $M$, 정수 $A$가 주어진다. ($1 \le N, M, A \le 5\,000\,000$) 둘째 줄에 재현이가 알아낸 해시값 정수 $H$가 주어진다. ($0 \le H < M$) www.acmicpc.net 풀이 $P_1 \cdot A+...+P_{N-1}\cdot A^{N-1}$ 을 $x$라고 해보자 $x=2, M=5$일 때 $P_0$ 값을 변경함에 따라 해시 함수의 결과 값이 0 ~ M-1 으로 나오는 것을 확인할 수 있다. 즉, $P_0$ 값에 따라 $h(P)$의 결과를 원하는 값으로 만들 수 있다. 하지만 $h(P)$를 해시값 정수 H로 만들 수 있는 $P_0$는 딱 1개 밖에 없다. 대신 $P_1 \cdot ..

문제 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 1. 정렬을 통한 풀이 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] intArray = new int[N]; for (int i=0..

문제 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 N=10, M=3, 원소의 위치={2,9,5}라고 할 때 2번, 3번 연산에 따라 아래와 같이 진행되어야한다. 왼쪽으로 이동했을 때와 오른쪽으로 이동했을 때의 거리를 계산하여 가장 짧은 쪽의 방향을 선택하여 수행하면 되는 문제이다. 아래 코드는 직접 LinkedList로 구현하여 양방향 이동을 가능하게하였다. import java.util.*; import java.util.stream.Collectors; import java.util.strea..

문제 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 풀이 N=10, A={4,3,6,7,8,9,10,2,1,5} 일 때 4개의 Stack에 아래와 같이 삽입한다. 결과가 {1,2,3,4,5,6,7,8,9,10} 이어야하고 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치해야하므로 각 4개의 Stack에 담긴 Element를 가장 큰 수부터 차례대로 아래와 같이 꺼낼 수 있다. 차례대로 Stack에서 가장 큰 수를 차례대로 꺼낼 수 있게하는 조건은 Stack에 값을 Push할 때 반드시 작은 값이 아래로 가고 큰 값은 반드시 위에 쌓여야한다. e.g. {1, 3, 4} (O), {3, 1, 4} (X) 따라서 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 코드 DP 적용 DP 중 LIS (Longe..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 코드 DP 문제 두 문자의 길이가 다를 경우 2중 for문에서 짧은 문자가 먼저 나와야한다. 반례는 다음과..

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 코드 굳이 번거롭게 만든 재귀 문제 8개 별을 가지는 삼각형을 기준으로 수행 import sys input = sys.stdin.readline n = int(input()) graph = [[' '] * 2 * n for _ in range(n)] def recursive(row, col, N): if N == 3: graph[row][col] = '*' graph[row + 1][col -..

https://www.acmicpc.net/problem/2206 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 코드 BFS 적용 각 칸마다 [벽을 부수지 ..