killog

n^2 가 안되게 하기 위해 remain 을 만들어서 풀어야하는 문제. 이전에 풀어본 유형임에도 오래걸렸다. 문제 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모..

이 문제에서 제일 중요한 포인트는 문제 푸는 핵심 전략이 아닌 제한 범위이다. 수빈이가 갈 수 있는 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000) 이 100000 를 방어 변두리로 잡는 것이 이 문제의 핵심 포인트 였다. 앞으로 제한 조건을 좀 더 잘 활용해야함을 잊지 말자. 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위..

1시간 10분 걸림. 문제 제대로 구현 안해서 한번 틀리고, 인덱스 에러를 안잡아 줘서 한번 틀렸고, 가짓수를 다 해봤는데 안될 경우를 생각하지 못해 여러번 틀렸다. 안될 경우를 대비해 answer 에 불가능이란 값을 default 로 줬어야하는 문제. transpose 함수를 알게 되었다. def transpose(graph): return list(map(list, zip(*graph))) 문제 크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 = len(curA[0]): return commandR(cur..

문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래와 같은 지..

많은 코드를 보았지만, blog.naver.com/PostView.nhn?blogId=kks227&logNo=220917078260&categoryNo=299&parentCategoryNo=0&viewDate=&currentPage=4&postListTopCurrentPage=&from=menu&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=4 이 글을 읽고 이해했습니다. 저는 간략하게 설명하지만, 더 자세한 설명이 필요하신 분은 이 글을 참고하시면 될 것 같습니다. 문자열 H,S(H>S) 에서 S와 H에 매칭된 부분의 접미사와 접두사가 일치할 시, 그곳부터 탐색하고, 일치하는 부분이 없을..

문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다. 지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며,..

문제 구현 구간, 시간은 선형이다. 또한, 이러한, 공통 구간을 구하는 문제에 있어서는 max(출발시간들), min(도착시간들)로 설정해서, 이것이 출발보다 도착이 빠르게 되는 조건이 부합하지 않을때, answer 에 1을 더하고, 새로 공통구간을 갱신하는 형태로 구현하면 된다. 나또한, 아직 익숙하지 않은 문제들. 암기가 필요하다. 문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 ..

문제 풀이 하노이의 탑의 원판이 n개일 때, 성공을 위한 최소 경우의 수는 2^n-1 이다. 이것은 이전에 (dp[n-1])*2+1 = dp[n] 이라는 결론에 다다를 수 있는데, 이전 스탭을 1➡3 의 목표를 1➡2 로 치환하고, 가장 큰 원판을 1➡3 으로 이동 시킨후, 이전 스탭의 목표(2) 를 3으로 옮기면 된다. (2➡3 ) 즉, 이것을 이전 리스트와 비교해 생각하자면, before step의 2➡3, 3➡2 한 결과물 1➡3 first step 의 1➡2,2➡3,3➡1 한 결과물 이라 보면 된다. 문제 설명 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위..