전체 글364 Lv5 멸종위기의 대장균 찾기(SQL) 문제 설명대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화되어 나온 개체를 자식 개체라고 한다. 이 문제는 각 세대별로 자식이 없는 대장균 개체의 수를 구하고, 세대별로 오름차순으로 출력하는 것이다. 테이블 구조대장균들의 정보를 담고 있는 ECOLI_DATA 테이블의 구조는 다음과 같다.ID: 대장균 개체의 ID (PRIMARY KEY)PARENT_ID: 부모 대장균의 ID (최초 대장균은 NULL 값을 가짐)SIZE_OF_COLONY: 대장균 집단의 크기DIFFERENTIATION_DATE: 분화된 날짜GENOTYPE: 대장균의 형질문제 요구사항각 세대별로 자식이 없는 대장균의 수를 구하고, 결과는 세대에 대해 오름차순으로 정렬해야 한다. 모든 세대에는 자식이 없는 개체가 적어도.. 2024. 10. 21. 회의실 배정(Greedy) 한 개의 회의실을 사용하고자 하는 n개의 회의가 있을 때, 각 회의의 시작 시간과 끝나는 시간이 주어진다. 이때, 회의가 겹치지 않게 하면서 회의실을 최대한 많이 사용할 수 있도록 배정해야 한다. 단, 한 회의가 끝나는 동시에 다른 회의가 바로 시작될 수 있으며, 중간에 중단될 수 없다. 문제 해결 아이디어이 문제는 그리디 알고리즘으로 해결할 수 있다. 끝나는 시간이 가장 빠른 회의를 먼저 선택하는 것이 최적의 해를 보장하는 방법이다. 이렇게 해야, 다음 회의가 겹치지 않게 최대한 많이 배정할 수 있다.1. 정렬 기준회의의 끝나는 시간을 기준으로 오름차순 정렬한다.끝나는 시간이 같다면 시작 시간을 기준으로 오름차순 정렬한다.2. 그리디 선택첫 번째 회의를 선택한 후, 선택된 회의의 끝나는 시간 이후에 시.. 2024. 10. 20. 씨름 선수(Greedy) 현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다. “A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.” N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요. 현수는 씨름 선수 선발을 위해 공고를 냈으며, 총 N명의 지원자가 지원하였다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있으며, 선발 원칙은 다음과 같다."한 지원자를 다른 모든 지원자와 비교하여, 키와 몸무게 모.. 2024. 10. 19. 피자 배달 거리(삼성 SW 역량평가 기출/DFS) 이 문제는 DFS(깊이 우선 탐색)을 활용하여 조합을 구하는 문제이다. N x N 크기의 도시에서 M개의 피자집을 선택하여 도시의 피자 배달 거리를 최소화하는 것이 목표다. 각 집은 도시의 여러 피자집 중 하나와 연결되며, 그 집에서 가장 가까운 피자집까지의 거리를 계산해, 모든 집의 배달 거리 합이 최소가 되도록 해야 한다. 문제 설명도시 지도는 N x N 크기로 주어지며, 각 칸은 빈칸(0), 집(1), 피자집(2)으로 표현된다. 각 집마다 여러 피자집과의 거리가 존재하지만, 그중 최소 거리가 해당 집의 피자 배달 거리가 된다. 예를 들어, (1, 2)에 있는 집과 (2, 3)에 있는 피자집의 거리는 |1-2| + |2-3| = 2이다.이 문제는 도시에서 M개의 피자집을 선택하여, 전체 도시의 피자 .. 2024. 10. 19. 섬나라 아일랜드(BFS) BFS(너비 우선 탐색)을 사용하여 섬의 개수를 구한다. 주어진 N*N 크기의 격자판에서 1은 섬, 0은 바다를 나타내며, 상하좌우 및 대각선으로 연결된 1들로 이루어진 영역을 하나의 섬으로 간주한다. 목표는 주어진 격자판에서 몇 개의 섬이 있는지 찾는 것이다.문제 설명격자판은 N*N 크기로 주어진다.1은 섬을 나타내고, 0은 바다를 나타낸다.상하좌우 및 대각선으로 연결된 1들은 하나의 섬으로 간주된다.BFS를 사용해 연결된 섬을 탐색하고, 총섬의 개수를 구한다.입력 예시71 1 0 0 0 1 00 1 1 0 1 1 00 1 0 0 0 0 00 0 0 1 0 1 11 1 0 1 1 0 01 0 0 0 1 0 01 0 1 0 1 0 0 출력 예시5 해결 과정1. 격자판 입력받기먼저 N을 입력받고, N*N .. 2024. 10. 19. 섬나라 아일랜드(DFS) N*N 크기의 격자판이 주어진다. 각 격자에는 섬(1) 또는 바다(0)가 표시되어 있다. 섬은 상하좌우 및 대각선으로 연결된 1들로 이루어져 있으며, 각각의 섬은 독립적인 하나의 연결 요소로 간주된다. 주어진 격자판에서 몇 개의 섬이 있는지 구하는 프로그램을 작성해야 한다.입력 설명첫 번째 줄에 자연수 N(3 두 번째 줄부터 N개의 줄에 걸쳐 N개의 숫자가 입력되며, 각 숫자는 0(바다) 또는 1(섬)을 의미한다.출력 설명섬의 개수를 출력한다.입력 예시71 1 0 0 0 1 00 1 1 0 1 1 00 1 0 0 0 0 00 0 0 1 0 1 11 1 0 1 1 0 01 0 0 0 1 0 01 0 1 0 1 0 0 출력 예시5 해결 과정격자판 입력받기먼저 N을 입력받고, N*N 크기의 격자판을 2차원 배.. 2024. 10. 19. 이전 1 2 3 4 5 6 7 ··· 61 다음
