killog

문제 구현 구간, 시간은 선형이다. 또한, 이러한, 공통 구간을 구하는 문제에 있어서는 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)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위..

blog.naver.com/kks227/220791986409 다양한 것을 봤지만 최종적으로 현재 이해한 것의 대부분은 여기서 왔다. 이 블로그 글을 보고 정리한 내용을 적는 것이기 때문에 아직 미숙한 나보다는 위의 링크에서 원글을 보고 이해하는 것이 더 좋을 것이다. 세그먼트 트리 핵심 : 구간들을 보존하고 있는 트리 = 각 노드가 구간 혹은 그 구간의 정보를 가지고 있다. 보통 완전 이진 트리를 사용해 전체적으로 동일한 재귀구조가 반복되게 표현한다. 값의 개수가 2^n 개가 아닐때는 의미 없는 기본 값으로 채워 포화 이진 트리 형태로 사용하는 것이 대부분이다. n개의 값 -> 트리의 높이 log(N) 루트의 인덱스가 1부터 시작되며 레벨 오더 순번으로 노드 번호를 매겨서 자신의 부모, 왼쪽/오른쪽 자..

와 왜맞았지 맞고도 얼떨떨하다. 다시 공부해야하는 것이 틀림 없는 문제 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다. 입력 첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 ..

https://blog.naver.com/kks227/220907708368 를 이용해 공부함. 우선순위 대로 값을 뽑아서 s, e 값을 비교한 후, 범위 안에 없을 시, 더하고 새로운 범위를 시작한다. 문제 매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자. 이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다. 입력 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그..

백준 스위핑 알고리즘공부하고 한문제 백준 세그먼트 트리 공부하고 한 문제 백기선 mvc 강의 다 듣기 장고 3시간 공부하기 cs 스터디

이런 풀이 외우자. 문제 수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외..

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 6 [[3, 6], [4..