조준장 개발자 생존기

문제 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 알고리즘 - 벡터의 외적을 통해 시계 방향인지 아닌지를 판별한다. 코드 import sys p = [list(map(int, sys.stdin.readline().split())) for _ in range(3)] v1 = [p[1][0] - p[0][0], p[1][1] - p[0][1]] # p1 -> p0 v2 = [p[2][0] - p[1][0], p[2][1] - p[1][1]] #..

문제 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 알고리즘 - dp를 통해 문제를 수행한다. - 우선 처음에 가로로 갈 수 있는 모든 빈 곳을 1로 초기화한다. - 다음으로 반복문을 통해 가로/세로/대각선으로 갈 수 있는 곳에 위치에 dp를 더해준다. - 3가지 방향으로 파이프가 이동해 온 경우의 수의 합을 출력한다. 코드 import sys n = int(sys.stdin.readline()) graph = [list(map(int, sys.stdin.readline().split..

문제 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 모든 육지 지점에서 다른 육지 지점까지의 거리를 bfs를 통해 체크한다. - 체크된 거리 중 제일 먼 거리 -1을 출력한다. - -1을 해주는 이유는 처음 지점에서 1로 방문 체크를 했기 때문이다. - 방문 체크를 하는 이유는 중복으로 처음 지점을 지나는 것을 방지하기 위해서이다. 코드 # pypy3 통과.. python3 시간초과.. import sys from collections import deque..

문제 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 알고리즘 - 반복문을 통해 각 줄을 확인한다. - 반복문을 통해 각 칸의 들어갈 수 있는 최대/최소 값을 구한다. - 최대/최소 값은 매 반복이 끝날 때마다 max_dp/min_dp에 초기화시켜준다. 코드 import sys n = int(sys.stdin.readline()) max_dp = [0 for _ in range(3)] min_dp = [0 for _ in range(3)] max_tmp = [0 for _ in range(3)] min_tmp = [0 fo..

문제 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. 코드 import sys from collections import deque # bfs 탐색 def bfs(): visited = [1e9] * 1000001 queue = deque([s]) visited[s] = 0 while queue: target = queue.popleft() # 스타트 링크에 도착했으면 버튼을 누른 횟수 출력 if target == g: return visited[target] # 반복문을..

문제 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 알고리즘 - 0 - 1 bfs 탐색을 통해 문제를 수행한다. - 동생의 위치에 도달했다면 리턴하고 도달하지 못했다면 이동한다. - 이동은 3가지 방법을 반복문을 통해 수행한다. - 이동하는 곳이 범위 내에 있고 이동하지 않은 곳이라면 이동한다. - 순간이동이라면 이전에 초로 갱신하고 appendleft()로 탐색한다. - 순간이동이 아니라면 이전에 초에 +1 해주고 append()로 탐색한다. - 위 탐색과정이 다른 것이 0..

문제 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 알고리즘 - 0번째 idx를 기준으로 오름차순 정렬을 한다. - 정렬된 전깃줄에 가장 길게 증가하는 부분 수열을 찾는다. - 이중 반복문을 통해 n번의 수까지 증가하는 길이를 구한다. - 길이를 구할 때 i번의 수와 그전에 수들을 비교한다. - 0번째 idx를 기준으로 오름차순 정렬을 했기 때문에 1번째 idx를 기준으로 수들을 비교한다. - 이때 가장 길게 증가하는 부분 수열이 겹치지 않는 전깃줄이므로 전체에서 빼준 값을 출력한다. 코드 import sys n ..

문제 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 알고리즘 - 반복문을 통해 미로를 확인한다. - 현재 좌표에 올 수 있는 모든 경우의 수의 최댓값과 현재 좌표에 사탕 수를 더한다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] dp = [[0 for _ in range(m + 1)] for _ in ra..

문제 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 알고리즘 - 반복문을 통해 이동해야 하는 채널로 가기 위한 방법을 확인한다. - 반복문을 통해 채널로 이동하기 위해 눌러야 하는 번호가 고장이 났는지 확인하고 고장이 났다면 그 번호를 눌러서는 이동할 수 없다. - 채널로 이동 가능하다면 원래 cnt, 채널을 누른 개수와 +/- 를 누른 개수를 더한 값을 비교하여 cnt에 담는다. - 마지막 cnt 값이 채널로 가기 위한 최소 개수가 된다. 코드 import sys n = int(sys.st..

문제 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 알고리즘 - 반복문을 통해 모든 작업이 완료될 때까지 작업을 한다. - zip을 통해 현재 작업 진도를 작업 속도와 더한다. - 현재 작업 진도가 100보다 크거나 같다면 현재 모든 작업 진도가 100보다 크거나 같은 것을 리스트에서 빼준다. - 이때 빠진 작업의 개수를 answer에 추가한다. - 모든 작업이 완료했다면 answer를 출력한다. 코드 def solution(progresses, speeds): answer = [] while pro..