룰루랄라 알고리즘

나름대로 Time Complexity를 생각해서 배열을 정렬하고 첫 번째 인덱스의 나무와 두 번째 인덱스의 나무의 차를 계산하면서 총합을 더해갔는데 계속 틀려서 다른 방법을 생각했다. 배열을 정렬하지 않고 이진탐색을 이용하는 방법인데, 주어진 배열과 수가 커서 알맞은 방법인 것 같다. 나무 중에서 가장 길이가 긴 나무의 높이를 top, 바닥을 down으로 두고 위아래로 이진 탐색을 진행한다. 만약 높이가 middle일 때 모든 (나무 높이-middle)의 합이 구하고자 하는 높이와 같다면 답이 구해진다. 위와 같이 숫자가 정확히 나누어 떨어지지 않는다면 middle이 아니고 middle-1이 답일 것이다. 숫자의 범위가 매우 클 떄 이진탐색을 고려해 보자. https://www.acmicpc.net/pr..

투 포인터의 약간의 변형 문제 두개의 포인터가 양 끝쪽이 아니라 모두 왼쪽에서 부터 시작하는 문제이다. 생각보다 인덱스의 범위, left right의 인덱스 등등 헷갈리는게 많았다. 보기엔 쉬워보이지만 직접 작성해보니 생각보다 어려운 문제. 처음 작성한 코드는 아래와 같은데 위 처럼 매 순간 마다 모든 구간을 sum한다면 투 포인터의 의미가 없어져 버린다는 것을 인지하지 못했었다.

코드는 알고리즘 - 위상 정렬에 있음 기본적인 위상 정렬 문제 위상 정렬을 사용하지 않고 스택을 이용해 풀었으나 당연히 시간초과로 실패 처음 위상 정렬이란 알고리즘을 알고 공부하게된 계기가 되었음

입출력에 대한 이해가 어려웠던 문제 테스트케이스를 입력으로 주지 않는 문제 파이썬의 try except를 사용해 풀었다. try는 에러가 일어나지 않을 때 작동하는 코드, except는 에러가 발생 했을 때 작동하는 코드이다. N의 최대 개수가 1000000이므로 정렬 후 투 포인터로 가장 왼쪽 값과 오른쪽 값을 더해 target X와 일치 할 때 결과를 result에 저장하고 함수를 종료한다.

처음에 이진 탐색으로 stack에 있는 값을 찾지 않고 아래와 같이 in을 써서 탐색 했다가 시간초과에 걸렸다. N,M이 각각 500,000 이하의 큰 수 임을 생각하지 못했다. 값이 큰 리스트를 탐색 할 때는 이진 탐색을 생각해보자