Seeeni Tech Diary

1. 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오...

1. 문제 https://www.acmicpc.net/problem/20544 20544번: 공룡게임 크롬 브라우저 상에서 인터넷 연결이 안될때나, 주소창에 chrome://dino 를 입력하면 공룡 게임을 플레이 할 수 있다. www.acmicpc.net 2. 문제 풀이 알고리즘 1) DP 테이블 설계 (높이 2인 나무 필수 조건 생략) 1~n 지점에 높이가 1, 2인 나무를 놓거나 안 놓을 수가 있는데, 첫 지점에서는 나무가 없어야 한다. 나무는 연속 2개까지만 놓을 수 있고, 나무 2개의 높이의 합은 4 이상이 되어서는 안된다. 즉, 1-1, 1- 2, 2 -1은 되지만 2-2는 안 된다. dp를 어떻게 사용할까 고민 하다가 현재 0(나무 없을 때), 1, 2 중 하나를 선택할 때 이전의 높이를 고..

1. 문제 https://www.acmicpc.net/problem/20914 20914번: QWERTY 자판 Albert는 QWERTY 키보드를 이용해 (위 그림 참고) 영문 대문자로 ('A'-'Z') 구성된 문자열을 입력하고 싶다. 아직 키보드 만지는 것이 서툰 Albert는 왼쪽 검지만을 이용해 버튼을 누르는 버릇이 있다. www.acmicpc.net 2. 문제 풀이 알고리즘 1) QWERTY 좌표 딕셔너리 Q W E R T Y U I O P A S D F G H J K L Z X C V B N M QWERTY 키보드를 왼쪽으로 정렬하면 위의 표와 같이 되는데, 이 좌표를 그대로 qwerty 딕셔너리에 저장해준다. qwerty = {"Q": [0, 0], "W": [0, 1], ... , "A": ..

1. 설명 1) 최단 경로 문제 - 가중 그래프와 두 개의 정점 u, v가 주어졌을 때, u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제 - 최단 경로길이: 간선들의 무게 합 2) 속성 - 최단 경로의 부분 경로 또한 최단 경로 - 출발 정점으로부터 다른 모든 정점에 이르는 최단 경로 트리가 존재 (단일점 최단 경로) 3) 최소신장트리와의 차이점 - 방향 그래프에서도 정의 - 무방향 그래프에 음의 무게를 가진 간선이 있으면 부정 4) 시간복잡도 - 정점 수: V, 간선 수: E - 기본 알고리즘의 시간 복잡도: O(V^2) - 우선순위 큐 사용시 시간 복잡도: O(ElogV) 2. 알고리즘 수행 과정 1) 출발 정점부터 각 정점까지의 거리를 담은 최단 거리 테이블(dist)을 INF 값으로 초기화..

1. 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2. 문제 풀이 알고리즘 N x M 칸에 치즈가 놓여있는데, 1이 치즈, 0이 공기를 나타낸다. 치즈 한 칸은 상하좌우 중 공기와 닿는 부분이 2칸 이상 있으면 녹게 된다. 치즈가 모두 녹았을 때의 시간을 구해야 하는 문제이다. 빙산이 녹을 때를 구하는 문제와 차이점은 치즈의 내부 공기는 치즈를 녹는 데에 영향을 줄 수 없다는 것이다. 따라서 치즈의 내부 공기와 외부 공기를..

1. 문제 https://www.acmicpc.net/problem/17143 2. 문제 풀이 알고리즘 R x C 칸에 상어가 m마리가 있고 상어는 각각 한 칸을 차지하고, 1초 동안 움직이는 속도 s, 방향 d에 따라서 d방향으로 1초 동안 s칸만큼 이동한다. 벽에 닿을 시에는 방향을 반대방향으로 움직인다. 낚시왕은 1번 열부터 시작하여 C열에 도달할 때까지 한 열에 있는 상어 중 가장 가까운 상어를 잡는다. 열을 한 번 움직일 때마다 1초가 소요된다. 이때 낚시왕이 C열에 도달하여 움직임을 멈출 때까지 잡은 상어의 크기의 합을 구해야한다. 이 문제를 해결하기 위해서는 현재 열에서 가장 가까운 상어를 찾음 → 상어를 잡음 → 남은 상어를 이동 이 세 가지를 모두 구현해야 한다. 3. 구현 1) 입력 받..

1. 문제 https://www.acmicpc.net/problem/2146 N X N 사이즈의 지도를 입력을 받게 되는데, 이 때 바다를 0, 육지를 1로 나타내고 섬은 바다로 둘러쌓인 영역 각각을 의미하게 된다. 이때 섬 두개를 잇는 가장 짧은 다리의 길이를 구해야한다. 다리는 가장 짧게 만들 수 있는 두 섬에 한하여 만들면 된다. 2. 문제 풀이 알고리즘 예제의 입력을 보면 섬들의 육지 영역은 모두 1로만 표시되어 있어서 임의의 육지 영역 하나를 골랐을 때 이 영역이 어떤 섬의 땅인지 구분할 수가 없다. 하지만 서로 다른 두 섬을 연결하는 다리를 만들어야해서 육지 영역을 어떤 섬의 것인지 구분해주어야 한다. 그래서 처음으로 구현할 것은 섬 영역을 나누어주는 것이다. 육지 영역을 1이라는 숫자로 통일..

1. 문제 https://www.acmicpc.net/problem/11729 문제는 하노이 탑을 최소 이동으로 3번째 탑으로 옮겼을 때의 이동 횟수와 그 과정을 출력하는 것이다. 이 문제를 해결하기 위해서는 먼저 하노이 탑의 원반이 어떻게 이동을 해야하는 지부터 알아야 한다. 2. 하노이 탑 이동 알고리즘 하노이 탑이 최소 이동하였을 때를 보면 위 그림과 같은 규칙을 갖고 있다. 원판이 총 5개 일 때를 예시로 들면, 3번째 탑으로 모두 옮기고 싶으면 첫 번째 원판(제일 큰 거)을 3번째로 옮기고 나머지 4개의 원판 기둥은 두 번째 탑으로 옮기게 된다. 두 번째 원판을 세 번째 탑으로 옮기려면 나머지 3개의 원판 기둥을 첫 번째 탑으로 옮기게 된다. 3. 코드 작성 import sys n = int(s..