Problem Solving/BOJ

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명 승패를 기록한 결과를 보고 가능한 결과인지, 불가능한 결과인지를 검사하는 문제다. 이때 가능한 결과라면 "1"을 출력하고, 불가능한 결과라면 "0"을 출력한다. 2. 접근 방식조별 예선은 총 6개의 국가가 같은 조에 속한 국가들과 한 번씩 경기를 치룬다. ⭐⭐⭐ 즉, 총 경기 횟수는 6C2로 15개가 된다. ⭐⭐⭐ 이때 15개의 가능한 경기쌍을 구하고 해당 경기에 대해 승, 무, 패 결과를 백트래킹한다면모든 경기를 순회했을 때 입력받은 예제의 가능 여부를 판별할 수 있다. 이를 코드로 구현해보자. 3. 코드import java.io.*;import java.io.BufferedReader;import java.io.IOExcep..

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명https://www.acmicpc.net/problem/1027 문제는 비교적 간단하다. 빌딩들의 높이가 주어졌을 때 가장 많이 보이는 고층 빌딩의 개수를 찾는 것이다. 빌딩 A에서 빌딩 B를 보려면 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 2. 접근 방식빌딩의 높이는 계속 달라지고, 앞의 계산 결과를 활용하기 어렵기 때문에 슬라이딩 윈도우나 dp는 고려하지 않았다. 문제에서 주어진 "빌딩을 보기 위한 조건"은 기울기의 사전적 정의와 유사해보였다. 좌표 평면에 아래의 입력 예제를 그린 그림이다. 3 // 빌딩 개수1 3 2 // 빌딩 높이 (1, 1)을 기준으로 볼 때 (2, 3)은 ..

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명https://www.acmicpc.net/problem/5052 전화번호 목록이 주어질 때, 목록에 일관성이 있는가를 검사하는 문제이다.일관성은 한 번호가 다른 번호의 접두어가 되는가를 기준으로 평가한다. 한 번호가 다른 번호의 접두어가 된다. → 일관성 X긴급전화 : 911선영 : 91 12 54 26한 번호가 다른 번호의 접두어가 아니다. → 일관성 O긴급전화 : 911수연 : 91 22 54 26 2. 접근 방식일관성이 없는 경우는 접두어가 같다는 조건을 활용하기 위해 정렬 을 떠올렸다. 입력값이 다음과 같이 주어졌을 때 91191091129129113 전화번호 목록을 String을 기준으로 정렬하면 아래와 같은 순서가 된다. ..

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명https://www.acmicpc.net/problem/1197 최소 스패닝 트리의 가중치를 구하는 문제이다. 최소 스패닝 트리는 그래프의 모든 정점들을 연결해야 하기 때문에 간선의 수는 노드 - 1개를 가진다. 또한 가중치의 합이 최소로 만들기 위해 사이클을 가지면 안 된다.1 - 2 / 1 - 3이 연결되어 있을 때 이미 모든 정점을 움직일 수 있기 때문에 2 - 3을 포함하면 가중치에 불필요한 값이 추가되며, 사이클이 발생한다. 2. 접근 방식가중치의 합을 최소로 만들어야 한다 = 가중치가 작은값부터 쏙쏙 골라간다 1. 먼저 모든 간선들을 가중치를 기준으로 오름차순 정렬2. 해당 간선을 포함했을 때 사이클이 안생긴다 → 최소..

목차1. 문제 설명2. 접근 방식3. 코드4. 시간 복잡도 및 공간 복잡도 계산 1. 문제 설명https://www.acmicpc.net/problem/1138 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. 입력값으로 키가 1인 사람부터 차례대로 자기보다 큰 사람이 왼쪽에 몇 명 있었는지 주어지면, 실제로 줄을 선 순서대로 키를 출력해주면 된다. 2. 접근 방식예제 입력 1을 기준으로 아래와 같이 해석할 수 있다. 키 1 : 왼쪽에 자기보다 키 큰 사람 2명키 2 : 왼쪽에 자기보다 키 큰 사람 1명키 3 : 왼쪽에 자기보다 키 큰 사람 1명키 4 : 왼쪽에 자기보다 키 큰 사람 0명 int[] arr에 [ 2, 1, 1, 0 ] 을 저장한다고 가정할 때 ✅️ 만약..

목차1. 문제 설명2. 정답     1. 문제 설명https://www.acmicpc.net/problem/12865   정말 말그대로 평범한 배낭 알고리즘 문제로, 점화식을 도출하는 방법을 정리해보려고 한다.배낭 알고리즘은 전형적인 dp문제다. 결국에 배낭에 물건을 담냐, 담지 않느냐로 쪼갤 수 있기 때문이다.     먼저 dp 배열을 정의해보자. dp[i][w]i번째까지의 물건을 고려했을 때무게 w를 버틸 수 있는 배낭의 최대 가치 물건을 선택할 때에는 두 가지 선택지가 있다. 1. 현재 물건의 무게가 배낭에 담을 수 있는 최대 무게를 초과 첫 번째 물건의 무게는 8kg로 배낭에 최대로 담을 수 있는 무게인 7kg를 초과한다.이 경우, 배낭에 물건을 담을 수 없다.따라서 이전 상태의 값을 그대로 가져..

목차1. 문제 설명2. 정답     1. 문제 설명https://www.acmicpc.net/problem/2146 지도가 주어질 때 가장 짧은 다리를 하나 놓아 두 대륙을 연결하는 방법을 찾는 문제다.  바다 = 0육지 = 1위의 그림과 같이 지도가 주어지면 회색 영역의 섬을 dfs로 구한다.바다와 육지가 각각 0, 1의 값을 사용하기 때문에 각각의 섬에 2부터 번호를 부여한다. 즉 dfs로 모든 영역을 순회했을 때 각각의 섬은 오른쪽 사진과 같은 번호를 부여받는다.  두 대륙을 연결하는 가장 짧은 다리는 (해안선과 근접한 육지) - (해안선과 근접한 육지)간의 최단 거리와 같다. Q. 최단 거리를 구해야한다면?A. bfs를 써야 한다는 뜻이다!   그렇다 이 문제는 dfs + bfs 짬뽕인 것이다....