취업 준비 및 일상

https://www.acmicpc.net/problem/23258 23258번: 밤편지 $C = 3$일 때, 1번 정점에서 4번 정점으로 가는 경로 중 3번 정점을 지나는 경로는 반딧불이 3번 정점에서 8방울의 이슬을 마시고 잠들어버리기 때문에 불가능하다. 따라서 가능한 경로는 2번 정점 www.acmicpc.net 풀이 2^C > (1 + 2 + ... + 2^(C-1)) 이므로, 2^C 미만만큼 이슬을 먹을 수 있는 반딧물은 1~C-1 칸을 거쳐서 갈 수 있다. 따라서, 3차원 int 배열 d[시작점][끝점][플로이드 단계(0이상 N이하)]를 '해당 플로이드 단계에서 시작점에서 끝점까지 가는 최소 거리'로 정의하여, 플로이드를 하면서 d를 채운다. 배운 점 초기화할 때 조심하기: s==e일 때 0을..

https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 문제 서훈이는 오늘 있었던 알고리즘 과목 기말고사를 망쳐서 기분이 좋지 않다. 서훈이는 스트레스도 풀 겸 시험 문제로 나온 그래프를 불로 태우려고 한다. 서훈이는 그래프의 정점 (위 그림에서 동그라미로 표시된 곳) 중 한 곳에 불을 붙일 수 있다. 정점에 불이 붙으면 곧바로 노드와 연결된 간선을 따라서 불이 전달된다. 간선 위에서는 불은 1..

https://www.acmicpc.net/problem/13314 13314번: 플로이드에 오타가? 평소에 코딩 실력이 부족하다고 느끼고 있는 지구이는 익명게시판에서 “백스페이스 키를 쓰지 않고 코딩하기를 추천합니다” 라는 글을 읽게 되었다. 글의 최하단에는 매우 작은 글씨로 “효 www.acmicpc.net 문제 평소에 코딩 실력이 부족하다고 느끼고 있는 지구이는 익명게시판에서 “백스페이스 키를 쓰지 않고 코딩하기를 추천합니다” 라는 글을 읽게 되었다. 글의 최하단에는 매우 작은 글씨로 “효과는 보장할 수 없습니다” 같은 내용의 글이 5줄에 걸쳐 알아보기 힘들게 쓰여 있었지만, 지구이는 그래도 한 번은 시도해 볼 만한 방법이라고 생각했고, 직접 해보기로 했다. 지구이가 처음으로 도전한 문제는 다음과 ..

https://www.acmicpc.net/problem/13168 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net 문제 친한 친구인 승현이와 지학이는 여름방학 때 여행을 가기로 계획했습니다. 해외여행은 금전적으로 부담이 많기 때문에 둘은 한국의 여러 도시를 여행하기로 했습니다. 한국에는 N개의 도시가 있으며, 승현이는 이 중 여행할 M개의 도시를 결정했습니다. 여행 경로에서 같은 도시를 여러 번 방문할 수 있으며, 여행을 시작하는 도시와 끝내는 도시는 같습니다. 한국에는 두 ..

https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 문제 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 ..

https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 문제 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공사가 진행되면서 어떻게 한 건진 알 수 없지만 일방통행만 가능한 길이 많이 늘고 말았다. 컴퓨터과학과 학생 남규는 전공 수업을 듣고 교양 수업을 들으러 가던 중 길을 잃어 3일 밤낮을 헤매다가 공학관에서 종..

https://www.acmicpc.net/problem/1956 문제 V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다. 도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다. 입력 첫째 줄에 V와 E가 빈칸을 사이에 두고..

https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어..

개념 V개의 점이 있는 그래프에서, 최단 거리를 찾는 알고리즘 for문을 3번 돌면서, dist[i][j]를 'i번째 점부터 j번째 점까지 곧바로 가는 최솟값, 곧바로 or 1번 점을 거치거나 거치지 않으면서 가는 최솟값, 곧바로 or 1번 점을 거치거나 거치지 않으면서 or 2번 점을 거치거나 거치지 않는 최솟값, ... , 곧바로 or 1번 점을 ... or V번 점을 거치거나 거치지 않으면서 가는 최솟값'을 구하는 알고리즘이다. 일반적으로 DP랑 따로 배우긴 하나(그래프 최단거리 알고리즘 배울 때 묶어서 배우...지?), DP 알고리즘이다. Time Complexity: 점의 개수 V에 대하여 for문 3번 돌기 떄문에 O(V^3) 음의 간선이 있어도 가능하나, 음의 사이클이 있으면 불가능 (음의 ..