본문 바로가기

분류 전체보기

(308)
[백준/Python] 22865번: 가장 먼 곳 문제 https://www.acmicpc.net/problem/22865 22865번: 가장 먼 곳 $N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들이 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할 www.acmicpc.net 문제 요약 N개의 땅 중에서 한 곳에 자취를 하기 위해 집을 알아보고 있다. 세 친구 A, B, C가 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이 때, 가장 먼 곳은 선택할 집에서 가장 가까운 친구의 집까지의 거리를 기준으로 가장 먼 곳을 의미한다. ex) X 위치에 있는 집에서 A, B, C의 집까지 거리가 각각 3, 5, 4이고, Y 위치에 있는 집..
[Computer Architecture] 공격적 파이프라이닝 + 한국항공대학교 길현영 교수님의 컴퓨터구조론 과목 내용을 정리한 글입니다. 공격적 파이프라이닝 파이프라이닝을 적용할 때 이론상 CPI는 1이지만, 해저드로 인해 사실상 CPI가 1보다 크다. => 더 성능을 향상시키기 위해 CPI를 1 이하로 만들자. 명령어 레벨에서의 병렬성(ILP,. Instruction Level Parallel)을 증가시킨다. 슈퍼 파이프라이닝 파이프라인의 각 단계의 클럭 주기를 줄인다. (= 단계 수 증가) 1. Clock Skew 현상이 심화될 수 있다. 2. 파이프라인 해저드 문제 발생률이 더 높아지고, 해저드에 따른 성능 패널티가 높아진다. 3. 클럭이 높아짐에 따라 클럭 주기를 더 작게 나누기 힘들어진다. (어렵다.) 4. 클럭 속도 상승은 발열 문제를 발..
[Computer Architecture] 해저드 + 한국항공대학교 길현영 교수님의 컴퓨터구조론 과목 내용을 정리한 글입니다. 해저드 선행 명령어와 후행 명령어의 중첩/실행이 원활하게 이루어지기 어려운 경우가 존재한다. => m단계 파이프라이닝에 대한 이론적 (거의) m배 성능 향상은 실제로는 불가능하다. = 다음 명령어가 다음 클럭 사이클에 실행될 수 없는 상황 = 명령어나 데이터가 준비되지 않아서 파이프라인을 멈춰야 하거나 새로운 명령어를 파이프라인에 투입할 경우 잘못된 결과가 초래되는 모든 상황이나 조건 해결 방법? => 해저드 원인이 사라질 때까지 파이프라인에 명령어 투입을 멈춰야 한다. - 파이프라인 중지 (Pipeline Stall) or 파이프라인 버블 (Pipeline Bubble) 구조적 해저드 = 파이프라인에서 실행 중인 2개 이상의 ..
[백준/Python] 1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 요약 N개의 도시(정점)와 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스(간선)가 있다. + 각 도시들은 번호가 존재하고, 버스마다 비용(양수)이 존재한다. 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다. 코드 from collections import deque import sys import heapq input = sys...
[백준/Python] 1753번: 최단 경로 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 요약 간선의 정보를 입력 받아 방향 그래프가 주어진다. + 모든 정점에는 1부터 정점 개수만큼의 번호가 매겨진다. 간선의 개수만큼 세 개의 정수 (u, v, w)가 순서대로 주어진다. + u에서 v로 가는 가중치 w인 간선이 존재한다는 의미이다. 시작점 번호를 입력 받고, 시작점에서 다른 모든 정점으로의 최단 경로를 출력한다. + 서로 다른 두 정점..
[백준/Python] 2589번: 보물섬 문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제 요약 각 칸이 육지(L), 바다(W)로 이루어진 2차원 배열 보물 지도가 있다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀 있다. + 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나 멀리 돌아가서는 안된다. 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 출력한다. + 한 칸을 이동하는 데 1이 걸린다. 코드 from..