전체 글
-
14510. 나무 높이알고리즘/SWEA 2022. 10. 23. 15:05
https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AYFofW8qpXYDFAR4&categoryId=AYFofW8qpXYDFAR4&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 N개의 나무가 있다. 초기의 각 나무의 키가 주어진다. 하루에 한 나무에 물을 줄 수 있다. 첫 날은 물을 준 나무의 키가 1 자라고, 둘째 날은 물을 준 나무의 키가 2 자라고, 셋째 날은 물을 준 나무의 키가 1 자라는 식으로, 홀수 번째 날은 키가 1 자라고 짝수 번째 날은 키가 2 자란..
-
순조부 2 - 순열(Permutation)알고리즘/알고리즘 이론 2022. 10. 15. 12:39
순열은 서로 다른 n개 중 r개를 택하여 한 줄로 나열한 것이다. 순열을 코드로 표현하는 방법은 재귀, 비트마스킹, 넥퍼(Next Permutation) 3가지 방법으로 나타낼 수 있다. 재귀 N개의 숫자를 배열에 저장 배열에서 각 위치의 숫자를 뽑았을 때, 뽑지 않았을 때의 순열을 생성 순열의 크기가 R개가 됐을 때 순열 완성 public class Permutation { // N개 중 R개의 순열 뽑기 static int N, R; // arr - 입력받을 배열 // temp - 순열을 저장할 배열 static int[] arr, temp; // 순열을 만들기 위해 arr의 요소가 선택됐는지 안됐는지 판단하는 배열 static boolean[] isSelected; public static void..
-
1854. K번째 최단경로 찾기알고리즘/백준 2022. 10. 6. 21:24
https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 문제 봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작..
-
9370. 미확인 도착지알고리즘/백준 2022. 10. 6. 21:20
https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요..
-
2887. 행성 터널알고리즘/백준 2022. 10. 2. 17:05
https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-y..
-
순조부 1 - 순열, 조합, 부분 집합알고리즘/알고리즘 이론 2022. 9. 30. 10:49
이 글에서는 알고리즘의 기초 중 하나인 순열, 조합, 부분 집합을 다루겠습니다. 순열, 조합, 부분 집합은 나중에가면 비슷하기 때문에 같은 문제를 서로 다른 방법으로도 풀 수 있는데 시간의 차이가 있기 때문에 문제를 파악해서 적절한 알고리즘을 사용할 수 있도록 개념을 정리해봅니다. 이 글에서는 각각의 기본 개념에 대해 다루며 자세한 내용은 다음 글에서 다루도록 하겠습니다. 1. 순열 정의 - 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열(순서있게)하는 것 순열은 간단하게 말해 순서가 있는 집합이라 표현할 수 있습니다. 예를 들어 {1, 2, 3} 과 {2, 1, 3}은 내용물은 같지만 순서가 다르죠 이 경우 순열에서는 두 집합은 다른 집합입니다. 표현 nPr nPr = n * (n-1) * (n-2)..
-
5557. 1학년알고리즘/백준 2022. 9. 25. 21:04
https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는..
-
1644. 소수의 연속합알고리즘/백준 2022. 9. 22. 23:24
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+..