난쟁이 개발자

[Gold III] 벽 부수고 이동하기 - 2206문제 링크성능 요약메모리: 277176 KB, 시간: 1320 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2024년 9월 22일 03:04:35문제 설명N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.한 칸에서 이동할 수 있는..

[Gold III] 웜홀 - 1865문제 링크성능 요약메모리: 113124 KB, 시간: 244 ms분류벨만–포드, 그래프 이론, 최단 경로제출 일자2024년 12월 8일 00:31:01문제 설명때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 ..

[Gold IV] 플로이드 - 11404문제 링크성능 요약메모리: 121432 KB, 시간: 196 ms분류플로이드–워셜, 그래프 이론, 최단 경로제출 일자2024년 12월 2일 23:26:23문제 설명n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어..

[Gold III] 아기 상어 - 16236문제 링크성능 요약메모리: 114004 KB, 시간: 124 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션제출 일자2024년 11월 30일 21:06:10문제 설명N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 ..

[Gold V] 선수과목 (Prerequisite) - 14567문제 링크성능 요약메모리: 142820 KB, 시간: 376 ms분류방향 비순환 그래프, 다이나믹 프로그래밍, 그래프 이론, 위상 정렬제출 일자2024년 11월 28일 21:10:35문제 설명올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 ..

[Gold IV] 트리의 지름 - 1967문제 링크성능 요약메모리: 112624 KB, 시간: 124 ms분류깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리제출 일자2024년 11월 27일 19:29:08문제 설명트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.입력으로 루트가 있는 트리를 ..

[Gold V] 로봇 청소기 - 14503문제 링크성능 요약메모리: 109240 KB, 시간: 116 ms분류구현, 시뮬레이션제출 일자2023년 11월 13일 12:50:00문제 설명로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.로봇 청소기가 있는 방은 N×M$N \times M$ 크기의 직사각형으로 나타낼 수 있으며, 1×1$1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r,c)$(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0)$(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 ..

[Gold IV] 연구소 - 14502문제 링크성능 요약메모리: 123676 KB, 시간: 2264 ms분류너비 우선 탐색, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색, 구현제출 일자2024년 11월 25일 22:12:40문제 설명인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의..

챕터3에서는 데이터 세트를 적절한 함수에 최적화하고 이 함수가 새 데이터에서 잘 수행되는지 확인하는 방법을 설명한다. 이 장에서는 이 과정이 인공 지능 문제의 핵심이며, 이후 챕터에서 더 복잡한 작업을 일반화되는 방법을 보여준다.많은 머신 러닝 모델의 핵심은 주어진 데이터 포인트 세트를 적절한 함수에 최적화 하는 것.회귀, 로지스틱 회귀, 서포트 벡터 머신과 같은 인기 있는 머신 러닝 기술을 소개한다.이러한 기술들을, 훈련 함수, 손실 함수, 최적화 라는 통합 주제를 공유한다.훈련 함수는 데이터에서 학습한 매개변수를 사용하여 입력 데이터에서 출력을 예측한다.손실 함수는 훈련 함수의 예측과 실제 데이터 레이블 간의 오차를 측정한다.최적화는 손실 함수를 최소화하는 매개변수 값을 찾는다.중요한 개념들회귀 : ..

이 챕터에서는 AI에서 데이터가 얼마나 중요한지를 강조한다. 또한 구조화된 데이터와 비구조화된 데이터, 선형 모델과 비선형 모델, 실제 데이터와 시뮬레이션된 데이터, 결정적 함수와 확률 변수, 이산 분포와 연속 분포, 사전 확률과 사후 확률, 가능도 함수 등 혼동하기 쉬운 개념의 차이점을 명확히 한다. 또한 세부 사항을 다루지 않고 AI에 필요한 확률 및 통계에 대한 로드맵을 제공하며 가장 널리 사용되는 확률 분포를 소개한다.데이터의 중요성데이터는 AI 시스템의 핵심. AI는 주로 데이터에서 학습하고 패턴을 식별하여 결론을 도출하고 결정을 내린다.데이터 과학과 AI라는 용어가 종종 같은 의미로 사용되지만, 데이터 과학은 AI의 핵심 구성 요소이지만 AI 자체와는 동일하지 않는다.실제 데이터와 시뮬레이션된..