JADE's Repository

문제 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..

Queue? 위 그림의 왼쪽처럼 식당에 입장하기 위해 줄을 서는 것을 생각해보면 가장 먼저 줄을 선 사람이 가장 먼저 입장한다. Queue도 이와 같은 방식으로 동작한다. 이처럼 먼저 들어간 것이 먼저 나오는 것을 선입선출(First In First Out, FIFO)라고 한다. Queue의 주요 연산 Enqueue와 Dequeue Enqueue(): 값을 집어넣는 것을 의미 Dequeue(): 값을 꺼내는 것을 의미 Java에서 Queue의 Enqueue와 Dequeue 메소드 Enqueue: add, offer Dequeue: remove, poll Queue의 시간복잡도 Enqueue(): O(1) Dequeue(): O(1) 탐색: O(n) Queue에서 값을 탐색하여 얻는 것은 부적절하다. 실제..

문제 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) 따라서 ..

Stack? 위처럼 접시를 쌓으면 마지막에 쌓은 접시가 맨 위에 놓일 것이다. 그러면 당연하게도 가장 마지막에 쌓은 접시를 제일 먼저 꺼내게 된다. Stack도 이와 같은 방식으로 동작한다. 이처럼 마지막에 쌓은 것을 가장 먼저 꺼내게되는 것을 후입선출(Last In First Out, LIFO)이라고 한다. Stack의 주요 연산 Push와 Pop push(): 요소를 추가 pop(): 가장 최근에 추가된 요소를 제거 Stack의 시간복잡도 push(): O(1) pop(): O(1) get(): O(n) get(): 값을 조회하는 메소드 Appendix 1946년 앨런 튜링은 서브 루틴을 호출하는 과정을 bury, 되돌아오는 과정을 unbury라고 불렀는데 이것을 스택의 기원이라고도 한다. 스택은 콜..

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 적용 각 칸마다 [벽을 부수지 ..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 코드 dictionary에 parent: [left, right]를 추가하여 순회 Tree를 직접 구현해서 풀다가 postorder가 안되서 포기 import sys def pr..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 ..