전체 글

1783 - 병든 나이트https://www.acmicpc.net/problem/1783문제병든 나이트가 N x M 크기 체스판의 가장 왼쪽아래 칸에 위치4가지로만 움직일 수 있음1. 2칸 위로, 1칸 오른쪽2. 1칸 위로, 2칸 오른쪽3. 1칸 아래로, 2칸 오른쪽4. 2칸 아래로, 1칸 오른쪽병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 함이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 함/ 4번보다 적은 경우(방문한 칸 => 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수?입력: 체스판의 세로 길이 N, 가로 길이 M (N, M (자연수) 출력: 여행에서 방문할 수 있는 칸의 개수 중 최댓값풀이행 =..

4963 - 섬의 개수https://www.acmicpc.net/problem/4963문제정사각형으로 이뤄져 있는 섬과 바다 지도한 정사각형과 가로, 세로, 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 걸어서 갈 수 있는 경로가 있어야 함지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없음=> 섬의 개수?입력여러 개의 테스트 케이스로 이뤄져 있음각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 h가 주어짐 (w, h (양의 정수) 입력의 마지막 줄에는 0이 2개 주어짐출력: 각 테스트 케이스에 대해서, 섬의 개수풀이가로, 세로, 또는 대각선으로 이동 가능static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1..

24479 - 알고리즘 수업 - 깊이 우선 탐색 1https://www.acmicpc.net/problem/24479문제N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)정점의 번호는 1 ~ N번, 모든 간선의 가중치는 1=> 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서?입력첫째 줄: 정점의 수 N (5 다음 M개의 줄에 간선 정보 u, v 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타냄(1 모든 간선의 (u, v) 쌍의 값은 서로 다름출력첫째 줄부터 N개 줄에 정수를 한 개씩 출력i번째 줄에는 정점 i의 방문 순서를 출력시작 정점의 방문 순서는 1/ 시작 정점에서 방문할 수 X 경우는 0 출력풀이`graph[i]`: i번..

11052 - 카드 구매하기https://www.acmicpc.net/problem/11052문제카드는 카드팩의 형태로만 구매, 종류는 1개 ~ N개가 포함된 카드팩까지 총 N가지카드의 개수가 작은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것-> 돈을 최대한 많이 지불해서 카드 N개를 구매하려고 함카드 i개 포함된 카드팩의 가격: $P_i$ex. 카드팩 총 4 종류, $P_1$ = 1, $P_2$ = 5, $P_3$ = 6, $P_4$ = 7-> 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값: 10원 (2개 들어있는 카드팩 2번)=> 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값?N개보다 많은 개수의 카드를 산 다음, 나머지 카드를..

1991 - 트리 순회https://www.acmicpc.net/problem/1991 문제이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)입력첫째 줄: 이진 트리의 노드의 개수 N (1 둘째 줄부터 N개의 줄: 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어짐노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드/ 자식 노드..

1644 - 소수의 연속합https://www.acmicpc.net/problem/1644문제하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다ex. 3 : 3 (한 가지)/ 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) / 53 : 5+7+11+13+17 = 53 (두 가지)But, 연속된 소수의 합으로 나타낼 수 X 자연수: 20 : 7+13 -> 7과 13이 연속 X한 소수는 반드시 한 번의 덧셈에 사용될 수 있음 -> 3+5+5+7과 같은 표현 적합 X입력: 자연수 N (1 출력: 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수풀이에라토스테네스의 체소수가 아닌 수(합성수) 지워나가면서 소수만 남기는 방식=> 주어진 숫자 N까지 모든 소수 빠르..