killog

문제 풀이 하노이의 탑의 원판이 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..

medium.com/pocs/페이지-교체-page-replacement-알고리즘-650d58ae266b를 기반으로 작성된 글입니다. 요구 페이징 시스템은 프로세스가 특정 페이지를 요구할 때 해당 페이지를 물리 메모리에 로딩한다. 메모리에 필요한 페이지가 있을 때는 잘 진행되지만, 없을 경우에는 문제가 생긴다. 프로세스가 필요로 하는 페이지가 없는 경우(page-fault) 하드 디스크에서 페이지를 찾아 빈 프레임에 로딩하는데, 여기서 또다시 ‘페이지를 올릴 빈 프레임이 없을 경우’ 란 문제에 직면할 수 있다. 이 때 사용하는 것이 새로 올릴 페이지와 교체할 희생 프레임을 찾는 알고리즘, 페이지 교체 알고리즘이다. 아래의 페이지 교체 알고리즘 예시들은 각 프로세스에 프레임 3개를 주고, 지역성 교체를 가정..