알고리즘
-
[백준] 24512번 : Bottleneck Travelling Salesman Problem(Small) - 자바(JAVA)알고리즘/백준 2022. 4. 16. 00:01
https://www.acmicpc.net/problem/24512 24512번: Bottleneck Travelling Salesman Problem (Small) 외판원 순회 문제는 영어로 Traveling Salesman Problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 이 중 변종 문제 중 하나인 Bottleneck Traveling Salesman Probl www.acmicpc.net 문제 풀이 전 설계 from, to, cost를 가지는 Edge 클래스를 생성합니다. 한 정점에서 출발하여 N-1 정점을 모두 한 번씩 방문하고 다시 처음 정점으로 돌아오는 순회이므로 최근에 배웠던 Prim 알고리즘과 Kruskal 알고..
-
5432. 쇠막대기 자르기 - 자바(JAVA)알고리즘/SW Expert Academy 2022. 4. 15. 00:01
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl47b6DGMDFAXm SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 여러개의 쇠막대기를 레이저로 절단하려고 한다. () 는 레이저를 의미합니다. 쇠막대기의 왼쪽 끝은 '(' 으로 오른쪽 끝은 ')' 으로 표현합니다. 위와 같은 방식으로 쇠막대기가 잘리게되면 17개로 잘리게 됩니다. 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 개수를 구하세요 문제 풀이 전 설계 입력값을 toCharArray로 char형 배열로 바꾸..
-
[백준] 10026번 : 적록색약 - 자바(JAVA)알고리즘/백준 2022. 4. 14. 00:01
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 전 설계 board [i][j] 별로 DFS를 진행한다. 이때 visited [i][j]를 두어 방문된 것은 true로 변환한다. 만약 board[x][y]를 방문해서 DFS를 진행하려고 했지만 visited [x][y] = true라면 DFS가 진행되지 않고 다음으로 넘어갑니다. DFS횟수만큼 count합니다. 처음 값기준으로 4방 탐색을 하며 값이 동일할 때까지 탐색합니다. ..
-
[백준] 2477번 : 참외밭 - 자바(JAVA)알고리즘/백준 2022. 4. 13. 00:01
https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 문제 해석 6 각형 참외밭의 면적을 구하여 참외의 수를 구하라 문제 풀이 전 설계 방향이 주어지기 때문에 모든 점의 좌표계를 구하여 내부에 있는 점을 확인하고 차이를 계산하여 면적을 구하려고 했습니다. 그러다가 가장 큰 길이를 기준으로 탐색해나가는 방식으로 넓이를 구하는것으로 바꾸었습니다. 1. 우선 가장 긴 길이를 찾습니다. (160) 2. 160 인덱스를 기준으로 양옆에 큰 값을 구합니다 (..
-
[백준] 15686번 : 치킨 배달 - 자바(JAVA)알고리즘/백준 2022. 4. 12. 00:01
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해석 크기가 N x N 인 도시가 존재합니다. 도시는 빈 칸, 치킨집, 집 으로 구성됩니다. 치킨 거리 = 집과 가장 가까운 치킨집 사이의 거리 도시의 치킨 거리 = 모든 집의 치킨 거리의 합 치킨집의 수익 증가를 위해 일부를 폐업시키려고 할 때 M개를 고르고 나머지를 모두 폐업시키려고 한다. 이 때 가장 작은 도시의 치킨 거리를 구하세요 문제 풀이 전 설계 조합을 통한..
-
[백준] 14719번 : 빗물 - 자바(JAVA)알고리즘/백준 2022. 4. 10. 00:01
https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제 해석 2차원 세계에 블록이 쌓여있고 비가 오면 블록 사이에 빗물이 고인다. 이때 고이는 빗물의 총량은 얼마일까? 2차원 세계의 바닥을 항상 막혀있다고 가정하여도 좋다. 문제 풀이 전 설계 빗물이 고일 수 없는 상황은 블록의 크기가 작아졌다가 커지는 구간이 없을 때이다. 반대로 빗물이 고일 수 있는 상황은 블록의 크기가 작아졌다가 커지는 구간이 존재할 때입니다. 우리가 알아야..
-
7465. 창용 마을 무리의 개수 - 자바(JAVA)알고리즘/SW Expert Academy 2022. 4. 9. 00:01
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 마을에는 N명의 사람이 살고 있다. 사람들은 1번부터 N번까지 번호가 부여되어 있습니다 두 사람은 서로 알고 있는 관계일 수 있고, 아닐 수 있습니다. 두 사람이 서로 아는 사람이거나 몇 사람을 거쳐서 알 수 있는 관계라면 이러한 사람들을 모두 묶어 하나의 무리라고 합니다. 창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하세요. 문제 풀이 전 설계 입력을 통해 인접 행렬을..
-
[백준] 1759번 : 암호 만들기 - 자바(JAVA)알고리즘/백준 2022. 4. 7. 00:01
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 해석 암호로 동작하는 보안시스템을 만드려고 한다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한개의 모음(a,e,i,o,u)와 최소 두 개의 자음으로 주성되어 있습니다. 암호는 알파벳이 증가하는 순서로 배열됩니다. 위의 규칙을 따르는 암호를 모두 출력하세요 문제 풀이 전 설계 1. R개의 알파벳을 조합을 이용하여 L개를 뽑는다. 2. 모음이 1개이상 자음이 2개이상인 조합들만 Str..