전체 글115 친구인가 설명오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다.모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다.만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다.그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요.두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다. 입력첫 번째 줄에 반 학생수인 자연수 N(1다음 M개의 .. 2024. 5. 25. 다익스트라 알고리즘 설명 아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로그램을 작성하세요. (경로가 없으면 impossible을 출력한다.) 입력첫째 줄에는 정점의 수 N(1 출력1번 정점에서 각 정점으로 가는 최소비용을 2번 정점부터 차례대로 출력하세요. 문제 해결다익스트라 알고리즘다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단경로 탐색 알고리즘이다.음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다. 다익스트라 알고리즘의 메커니즘은 기본적으로 아래 두 단계를 반복하여 임의의 노드에서 각 모든 노드까지의 최단거리를 구하는 문제에서 활용할 수 있다. 임의의 노드에서 다른 노드로 가는 값을 비.. 2024. 5. 25. 최대 수입 스케쥴 (PriorityQueue 응용문제) 설명현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다. 입력첫 번째 줄에 자연수 N(1 출력첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다. 예시 입력 1 650 220 140 260 330 330 1 예시 출력 1150 문제 해결 우선순위 큐큐는 먼저 들어오는 데이터가 먼저 나가는 선입선출 (FIFO) 형식의 자료구조지만우선순위 큐는 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조 자바에서 PriorityQueue 이렇게 사용.. 2024. 5. 24. 회의실 배정 설명한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 입력첫째 줄에 회의의 수 n(1이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.회의의 시작시간과 끝나는 시간의 조건은 (시작시간 출력첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라. 예시 입력 1 51 42 33 54 65 7 예시 출력 13 예시 입력 2 33 31 32 3 예시 출력 22 문제 해결.. 2024. 5. 24. 씨름 선수 설명현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다.현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.“A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.”N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요. 입력첫째 줄에 지원자의 수 N(5두 번째 줄부터 N명의 흰돌 능력치와 검은돌 능력치 정보가 차례로 주어집니다.각 선수의 흰돌능력치가 모두 다르고, 검은돌 능력치도 모두 다릅니다. 능력치 값은 1,000,000이하의 자연수입.. 2024. 5. 24. 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용) 설명N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다.각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다.행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.도시에는 각 집마다 “피자배달거리”가 있는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다.예를 들어, 도시의 지도가 아래와 같다면(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다.최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있.. 2024. 5. 20. 이전 1 2 3 4 ··· 20 다음 반응형
