Problem Solving

목차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://school.programmers.co.kr/learn/courses/30/lessons/388354 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제에는 각 노드에 대한 정의가 나와있다.모든 노드는 홀수 노드, 짝수 노드, 역홀수 노드, 역짝수 노드 중 하나이며 홀짝 트리와 역홀짝 트리는 아래의 노드로만 이루어진 트리를 의미한다. 홀짝 트리역홀짝 트리홀수 노드역홀수 노드짝수 노드역짝수 노드 2. 접근 방식문제에서 주어진 트리는 루트 노드가 설정되어 있지 않다. 루트 노드와 루트 노드가 아닌 일반 노드는 어떤 차이점이 있을까?..

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있고, 벽이 있는 칸에는 경주로를 건설할 수 없다. 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로라고 한다. (개당 100원)두 직선 도로가 서로 직각으로 만나는 지점을 코너라고 부른다. (개당 500원) 경주로를 건설하는데 필요한 최소 비용을 구하는 문제이다. 이때 언제 코너가 만들어지는지 계산하려면 ..

목차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://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr "ICN"에서 출발해 방문하는 모든 공항 경로를 출력하는 문제이다. 이때 공항 수는 3개 이상 10,000개 이하이다. 출발지도착지ICNSFOICNATL 예제 2처럼 가능한 경로가 2개 이상인 경우엔 알파벳 순서가 앞서는 경로를 먼저 방문한다.가능한 경로가 2개 이상이면 오름차순 정렬된 결과를 선택해야 한다는 의미로위의 표를 기준으로 ATL을 먼저 방문해야 한다. 2. 접근 방식방문..

목차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://school.programmers.co.kr/learn/courses/30/lessons/389479 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 핵심 조건은 아래와 같다. 같은 시간대에 게임을 이용하는 사람이 m명 늘어날 때마다 서버 1대 추가n * m → 최소 n대의 증설된 서버가 필요k = 5 ) 10시에 증설한 서버는 10 ~ 15시에만 운영 0 ~ 23시까지의 모든 게임 이용자를 감당하기 위한 최소 서버 증설 횟수를 구하면 된다. 2. 접근 방식players의 길이, m,..

목차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를 초과한다.이 경우, 배낭에 물건을 담을 수 없다.따라서 이전 상태의 값을 그대로 가져..