https://www.acmicpc.net/problem/22865 22865번: 가장 먼 곳 $N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할 www.acmicpc.net 다익스트라 알고리즘을 이용해서 a, b, c로부터 모든 지점까지의 거리를 구한다. 그 거리들을 담아 놓은 리스트가 dist_a, dist_b, dist_c이다. for i in range(1, n+1): if max_dist < min(dist_a[i], dist_b[i], dist_c[i]): max_dist = min(dist_a[i], dist_b[i], dist_c[..
Algorithm (PS)
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 분할 정복 문제이다 구현은 2가지 함수로 크게 나누었다. 1. def multiply() : 행렬과 행렬을 곱셈한후 return 해주는 함수 특별한것 없이 행렬 계산을 for 문으로 구현했다. 2. def solve() : 분할정복으로 연산하는 함수 지수 B가 홀수 일 때와 짝수일때를 나눠서 연산했다 지수이니까 ..! 예를들어서 지수가 (=B 값이) 5인 경우 도식화 해보면 다음과 같다 5를 5//2 로 나눈 ..
https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 주어진 그래프는 연결그래프이다. 모든 노드들이 연결된 상태이다. 노드의 개수는 N개 이고, 간선의 개수는 N-1 이다. 최소 비행기의 개수는, cycle을 형성하지 않으면서 모든 노드들을 연결해주는 간선의 개수인 N-1가 답이 된다. tree문제를 풀고 싶었는데 운좋게 얻어걸렸다 ㅋㅋㅋㅋ T = int(input()) for _ in range(T): n, m..
https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 이 문제는 문제를 읽고 이해하는데 시간이 걸렸다.. 결론적으로 구현해야 할 것은 다음의 1 ~ 4 번이고 이걸 묶어서 한단계라고 하는 것이다. '몇 번째 단계'인지 구하는건데 이것도 설명에 명확히 나와있지 않아서 오래 걸렸다 ㅡㅡ 그래도 deque로 원형큐를 시뮬레이션하는 방법과 같이 인상깊은 점이 있어서 재미있는 문제였다 배운 점 1. 원형큐에서 회전할 때 deque.rot..
https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 1 2 3 4 5 6 7 8 수열중에서 홀수를 K개 삭제할 수 있다는 것이 포인트 따라서 연속해서 등장하는 홀수의 개수를 기준으로 현재 연속된 짝수의 개수를 수열의 길이라고 볼 수 있다. 수열에서 인덱스를 하나씩 증가시키면서 이를 수열의 맨 처음 부분인 start 라고 본다. 그리고 현재 위치인 start에서 짝수의 수열 길이를 갱신해준다음, start 값이 하나 증가하기 이전에 현재 start값에 대한 처리를 아래와 같이 해준..
https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 카카오의 프렌즈 4 블록 문제랑 매우 유사한 시뮬레이션 + bfs문제였다 4블록이랑 다른 점은 4블록은 정사각형을 만들어야 없어지고 Puyo Puyo는 연속해서 4개 블록연결되어 있으면 어떤모양이든 터진다 ! 블록이 터진 후에 위에서부터 아래로 빈칸이 없도록 블록을 내려주는것도 유사하다 import sys from collections import deque board =..
https://www.acmicpc.net/problem/21923 21923번: 곡예 비행 동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 www.acmicpc.net 상승비행의 dp와 하강 비행의 dp값을 각각 구한 후, 두 테이블을 합쳐서 나오는 최댓값을 구한다. n, m = map(int, input().split()) array = [] for i in range(n): data = list(map(int, input().split())) array.append(data) up = [(0, -1), (1, 0)] down = [(1,0), (0,1)] dp_u..
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 레이팅 점수를 얻기 위한 ㅋㅋ 클래스문제..! n = int(input()) array = list(map(int, input().split())) left = 0 right = n-1 x = 0 y = 0 diff = int(1e9) * 2 while left < right: temp = array[left] + array[right] if abs(temp) < diff: diff = ab..
