투투

문제 크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 다음과 같은 N=6인 경우 지도를 살펴보자. 이때, 길은 총 2N개가 있으며, 아래와 같다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해..

programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 접근 문제를 읽었을 때 n개의 섬을 연결하는 최소신장트리를 구성하는 것을 알 수 있었고 크루스칼 알고리즘을 적용하였다. 구현 - 입력받은 costs를 비용을 기준으로 오름차순 정렬한다. - 이후 자신의 최상위 부모노드를 입력하기 위해 리스트 p를 선언하고 초기에는 자기자신을 가리키도록 한다. costs = sorted(costs, key=lambda x: x[2]) p = [i for i in range(n)] - 자신의 최상위 부모노드를 찾는 find_set함수를 구현하였..

문제 동아리방이 가지고 싶었던 병찬이는 LINK 사업단에 문의하여 N개의 방 중의 하나를 얻을 기회를 얻었다. 일자로 되어있는 건물에 N개의 방은 일직선상에 존재하며, 각 방에는 번호가 매겨져 있다. 맨 왼쪽 방의 번호는 1번이며, 순서대로 증가하여 맨 오른쪽 방의 번호가 N번이다. 각 방 사이에는 방을 구분하는 벽이 존재한다. 물론 병찬이 외에도 많은 사람이 동아리방을 원한다. 다행히 방은 충분했기에 병찬이는 안심하고 있었지만… 그때였다. 빅-종빈빌런이 나타나 건물 벽을 허물기 시작한 것이다! 빅-종빈빌런은 다음과 같은 규칙으로 벽을 무너뜨린다. x < y 를 만족하는 두 방에 대해서 x번 방부터 y번 방 사이에 있는 모든 벽을 허문다. 두 방 사이의 벽이 허물어지면 두 방은 하나의 방으로 합쳐진다. ..

문제 상근이는 트럭을 가지고 긴 일직선 도로를 운전하고 있다. 도로에는 신호등이 설치되어 있다. 상근이는 각 신호등에 대해서 빨간 불이 지속되는 시간과 초록 불이 지속되는 시간을 미리 구해왔다. (빨강색과 초록색 불빛은 무한히 반복된다) 상근이의 트럭이 도로에 진입했을 때, 모든 신호등의 색상은 빨간색이고, 사이클이 막 시작한 상태이다. 상근이는 1초에 1미터를 움직인다. 신호등의 색상이 빨간색인 경우에는 그 자리에서 멈추고 초록색으로 바뀔때 까지 기다린다. 상근이가 도로의 끝까지 이동하는데 걸리는 시간을 구하는 프로그램을 작성하시오. 도로의 시작은 0미터이고, 끝은 L미터인 지점이다. 입력 첫째 줄에 신호등의 개수 N과 도로의 길이 L이 주어진다. (1 ≤ N ≤ 100, 1 ≤ L ≤ 1000) 다음..

문제 상근이는 2차원 평면 위에서 움직일 수 있는 거북이 로봇을 하나 가지고 있다. 거북이 로봇에게 내릴 수 있는 명령은 다음과 같이 네가지가 있다. F: 한 눈금 앞으로 B: 한 눈금 뒤로 L: 왼쪽으로 90도 회전 R: 오른쪽으로 90도 회전 L과 R명령을 내렸을 때, 로봇은 이동하지 않고, 방향만 바꾼다. 명령을 나열한 것을 거북이 로봇의 컨트롤 프로그램이라고 한다. 상근이는 자신의 컨트롤 프로그램으로 거북이가 이동한 영역을 계산해보려고 한다. 거북이는 항상 x축과 y축에 평행한 방향으로만 이동한다. 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형의 넓이를 구하는 프로그램을 작성하시오. 단, 직사각형의 모든 변은 x축이나 y축에 평행이어야 한다. 아래 그림에서 거북이는 가장 처음에 ..

문제 월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다..

문제 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다. 벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다. i번 칸의 내구도는 Ai이다. 위의 그림에서 1번 칸이 있는 위치를 "올리는 위치", N번 칸이 있는 위치를 "내리는 위치"라고 한다. 컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올리는 위치에만 올릴 수 있고, 내리는 위치에서만 내릴 수 있다. 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다. 로봇을 올리는 위치..

문제 N개의 물병이 있고 각 물병은 무한대로 물을 담을 수 있다. 이때 최대 K개의 물병만 옮길 수 있다고 하자. 처음에 각 물 병은 1만큼 담겨져있으며 같은 양이 들어있는 두 개의 물병을 하나의 물병으로 합칠 수 있다. 또한 합칠 물병이 없을 때는 1리터의 물병을 사올 수 있다. 이때 최대 K개의 물병으로 만들기위해 사온 물병의 개수를 구하라. 입력 첫째 줄에 N과 K가 주어진다. N은 10^7보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다. 접근 이진수로 접근하는 방법이 있었다. N이 1부터 8일 때 사오지않고 옮길 수 있는 병의 개수를 구해보면 N을 이진수로 변경했을 때..

문제 앞으로 N일간 주식 가격이 숫자로 주어진다. 이 중 K번 거래를 하려고한다. 거래를 할 때는 하루에 한 번만 할 수 있으며 첫 날을 제외하고 이전날보다 주식가격이 올랐을 때만 거래를 한다. 이 때 K번 거래를 할 수 있는지 검사하는 프로그램을 작성하시오. 입력 입력 파일에는 여러 테스트 메이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 정수 N과 K이 주어진다. N은 앞으로 주가를 알 수 있는 날 수이며, (1 ≤ N ≤ 10,000) K는 거래의 회수이다. (1 ≤ K ≤ 10,000) 다음 줄에는 앞으로 N 날의 주가가 사이에 공백을 두고 주어진다. 주가는 1부터 10,..

문제 어린이집에 N명의 학생이 있고 소풍을 가려고한다. N명의 학생에게 1번부터 N번까지 번호를 부착하였고 학생들을 보호하기위해 번호순서대로 일렬로 서서 걸어가도록 하였다. 중간에 학생들의 번호순서가 바뀌었다. 이때 학생들을 이동시켜서 원래 번호순서대로 다시 줄 세우기위해서는 최소한 몇 명의 학생을 이동시켜야하는지 구하라. 입력 첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다. 출력 첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다. 접근 예전에 크루스칼이나 프림을 적용하는 문제를 풀 때 최소신장트리를 구성해야한다는 것을 파악하면 쉽게 풀 수 있었다. 이번 문제에서도 LIS를 구하는..