Algorithm

[백준, Java] 10775번 : 공항

🔗 문제 링크 https://www.acmicpc.net/problem/10775 😮 문제 해결 방법 문제에서 비행기가 순서대로 도착할 예정이고 각 비행기의 값은 1부터 해당 값까지의 게이트에 도킹할 수 있는 것을 의미한다. 자신의 순서에 비행기가 도킹할 수 없을 때까지 개수를 세준다. 비행기가 도킹할 수 있는 게이트를 찾기 위해서 Union-Find를 이용한다. 게이트 배열을 자신의 게이트로 초기화를 하고, 해당 값의 비행기가 도킹되면 다음에 도킹될 동일한 값의 비행기는 현재 게이트보다 하나 작은 게이트로 도킹되어야 한다. 예를 들어, 게이트가 4개이고 아무 비행기도 게이트에 도킹되지 않았다면 게이트 배열은 1,2,3,4값을 가질 것이다. 3번 비행기가 3번 게이트에 도킹되면 이 후에 들어오는 3번 비..

[백준, Java] 1414번 : 불우이웃돕기

🔗 문제 링크 https://www.acmicpc.net/problem/1414 😮 문제 해결 방법 문제의 입력이 인접행렬 방식으로 들어오고, 알파벳과 0으로 들어온다. 따라서, 입력이 이어진 랜선의 길이이기 때문에 숫자로 변환하고 그래프를 만들어준다. 모든 컴퓨터에 대해 랜선 그래프를 만들어 줬으므로 모든 컴퓨터가 이어질 수 있게 가장 짧은 랜선을 구하면 된다. 따라서, 최소신장트리를 구하는 프림 혹은 크루스칼 알고리즘을 이용해 구현하면 문제를 해결할 수 있다. 알파벳을 숫자로 변환환다. 컴퓨터에 대해 랜선 정보를 연결한다(정점과 간선을 이용해 그래프 생성) 프림 알고리즘을 수행한다. 어떤 컴퓨터에서 시작하더라도 모두 이어져야하므로 상관이 없다. 최소 길이 랜선을 구하고 전체 랜선 길이에서 빼준다. 🚩..

[백준, Java] 19621번 : 회의실 배정 2

🔗 문제 링크 https://www.acmicpc.net/problem/19621 😮 문제 해결 방법 문제의 제한 조건에서 K 번째 회의는 K-1 , K+1번째 회의와 겹친다고 했기 때문에 K 기준으로 회의를 참석하는 경우 K-1, K+1회의는 참석할 수 없다. 반대로 회의에 참가하지 않는 경우 K-1, K+1 회의는 참가할 수 있다. 따라서, 첫 회의를 기준으로 참가하는 경우와 불참하는 경우로 DFS를 이용한 완전탐색으로 문제를 해결했다. 회의의 최대 개수가25개까지 주어지므로 DFS를 이용한 완전탐색이 가능하다. 첫 번째 회의 기준으로 참가와 불참 경우로 탐색을 진행한다. 첫 번째 회의에 참가하는 경우 2번째 회의는 참가하지 못하기 때문에 3번째 회의에 참가하도록 depth + 2를 해주고 현재 회의..

[백준, Java] 9934번 : 완전 이진 트리

🔗 문제 링크 https://www.acmicpc.net/problem/9934 😮 문제 해결 방법 상근이가 도시를 방문한 조건을 살펴보면 가장 왼쪽에 있는 도시까지 방문한 후 그 부모를 방문 한 뒤 다시 오른쪽을 탐색한다. 즉, inorder 중위 순회 방식과 동일하다. 상근이가 방문한 도시의 트리 모양을 표현해줘야 하는 것이 목적이므로, 노드 번호가 1, 2, 3 순차적으로 증가하는 완전 이진 트리를 새로 만들어줬다. 새로 만든 트리를 이용해 중위 순회를 한 후 방문한 도시들을 스택에 저장한다. 입력으로 받은 도시와 스택에 저장한 도시가 동일한 순서이기 때문에 입력으로 받은 도시와 스택에 저장한 도시를 하나의 클래스로 매핑해준 뒤 새로 만든 트리의 모양대로 만들어준다. 새로 만든 트리는 노드 번호가 ..

[백준, Java] 9465번 : 스티커

🔗 문제 링크 https://www.acmicpc.net/problem/9465 😮 문제 해결 방법 매 열마다 1행 혹은 2행의 스티커를 뜯었을 때의 최대 점수를 구해주면 되기 때문에 2차원 배열로 선언해준다. 최대 점수는 n열까지 모두 뜯었을 때 1행 n열 혹은 2행 n열의 점수 중 큰 점수가 가장 최대로 구할 수 있는 점수이다. 현재 열이 3열이라고 가정하고 스티커를 뜯는 경우를 판단해보자. 3열의 스티커를 뜯는 경우는 1행 3열, 2행 3열의 스티커를 뜯는 경우 2가지이다. 1행 3열의 스티커를 뜯는 경우 → row : 0 col : 2 인접한 변을 가진 스티커는 뜯을 수 없기 때문에 **이전 열 대각선(현재 행과 반대되는 행)**에 위치한 최대 점수 값과 현재 스티커 점수를 더해준다. → dp[p..