youngseo's TECH blog

분할정복의 시간복잡도는 NlogN이다. (단계 별 문제 개수 (N//2^K) X 해당 단계에서 쪼개는/병합하는 시간(2^K) X 단계 개수(크기가 이진탐색 수준으로 줄기 때문에 logN)) 이것을 밑으로 내려가면서 쪼갤 때 / 위로 올라오면서 병합할 때 2번해서 어차피 2 NlogN이므로 시간복잡도는 그냥 NlogN이다. (DP테이블은 문제 종류가 M이라고 하면 O(NM)이라 더 효과적인 것을 확인할 수 있음) ★DP와 다른 점 부분 문제가 서로 중복되지 않는다. 위 사항 덕분에 Memoization이 필요하지 않다. 굳이 내가 알아낸 데이터를 저장하지 않는다. ★이분탐색트리 또는 세그먼트 트리와 다른 점 이분탐색/세그먼트는 일단 아는 노드를 쭉 나열해 두고 둘씩 짝지어서 위로 올라가며 판단하는 과정을 ..

binary search, 이분법적으로 딱 ' 이 시간. 이 숫자. 이 갯수 '를 구하고 싶을 때 매우 강력한 툴이다. 하지만 너무 생각할 게 많다.. 그래서 꾸준히 정리를 해보도록 하겠다!!! (자꾸 끼워 맞추면서 풀다가 실전에서 시간 너무 오래 잡지 말자...) [1, 2, 3, 3, 3, 3, 4, 5, 5] 라는 배열이 있다. 우리는 3을 찾고 싶다. 음.. 3 중에서도 가장 최소의 index를 가지는 3을 찾고 싶다면, 이렇게 mid가 가장 왼쪽을 향하게 하도록 극한으로 몰아세운다. (직접 해보면 이해 잘 됨) while lo target: return binary_search(array, target, start, mid) #중간값의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 elif ar..

비트마스킹을 이용하면 굳이 배열을 쓰지 않아도 되므로 메모리도 절약될 뿐만 아니라 배열의 index로도 쓸 수 있어(0001은 1로, 0010은 2로 쓸 수 있다.) 매우 강력한 툴이다! 주로 있다/없다 의 이분법적 현상을 반영해서 표현할 수 있다. 이것만 알면..!! 된다!! & -> 모두 1일때 1반환 | -> 하나라도 1일때 1 반환 / 모두 0일 때 0반환 ^ -> 대응하는 두 비트가 서로 다를 때 1반환 >> -> 오른쪽으로 비트 옮김 100>>2:1 ★삽입 시! i번째 비트를 i값으로 변경할 때 10101에서 11101 만들고 싶다면 10101 | 1

문제정리 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 사다리 문제. 일단 문제 파악이 쉽지 않아 여러 사다리를 마구 만들어봤다. 생각노트 세로선이 - - 이렇게 똑같은 높이에 그어지면 안된다. 앞에서부터 최대한으로 만족 시키다가 아무리 앞을 바꿔도 뒤에서 더이상 안되는 경우가 생긴다. 위의 경우처럼. 선을 추가하는 경우와 추가하지 않는 경우를 생각해볼 수 있는데, 선을 추가하는 경우 그 칸이 홀수일 때, 선을 추가하지 않는 경우는 그 칸이..

문제정리 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 생각노트 두 자동차가 가는 길이 있다고 했을 때 어떻게 하면 최소로 갈 수 있을까. 이때 각 자동차를 "무조건 가까운 곳"으로 선택해서 가는 방법은 조금 생각해보면 안 된다는 것을 알 수 있다. 몇 번째 사건을 누가 처리하느냐에 따라 의존성이 계속해서 바뀌기 때문이다. (아무리 경찰차2랑 현재 거리에서는 가깝다고 하더라도 경찰차1이 사건 1,2,3을 처리하다가 더 ..

대뜸 다음 코드에서 값이 어떻게 나올지 예상해 보자. def spam(eggs): eggs.append(1) eggs=[2,3] ham=[0] spam(ham) print(ham) 그래, 배열은 메모리 주소값을 할당하는 거라고 했고, 함수 spam에 인수로 넣은 ham이 eggs가 되는 격이니까 답은 [2,3]! 이라고 했다면... ㅎㅎ이 글을 보게 된 것이 다행이다!! spam에 함수의 parameter는 eggs이다. 따라서 우리가 ham을 spam에 넣어준 동시에 함수의 parameter eggs는 ham 자체가 된다. 3행에서 eggs는 새로운 리스트를 만드는 코드이다. 그래서 이 경우, 더는 ham과 eggs와 같은 메모리 주소를 가리키지 않고 eggs는 자신만의 메모리 주소를 가지게 된다. 함..

먼저 python list의 메모리 관리 방식에 대한 이해가 필요하다. python에서 연산자 중에 '=='는 값을 비교하는 연산자이고, 'is'는 메모리의 주소를 비교하는 연산이다. 아래 코드를 보자.a=300 b=300 a is b #False a == b #True그런데 조금 다른 결과가 나타나는 경우가 있는데,a = 1 b = 1 a is b #True a == b #True엥? 이 때는 a와 b의 메모리 주소가 같은 걸까?? 이것은 파이썬의 정수형 저장 방식의 특성 때문인데, -5부터 256까지의 정수값은 특정 메모리 주소에 저장한 후 해당 숫자를 할당하려고 하면 해당 변수는 그 숫자가 가진 메모리 주소로 연결한다. 리스트가 위와 같은 메모리 저장 방식을 택하고 있다고 생각하면 되는데, 파이썬은..

카카오인턴 2022 05 07 후기! 시험은 2시부터 7시까지 5시간동안 진행되었다. 생각보다 5시간 집중하는 게 쉽지 않았다.! 1 1솔 2 1솔 3 ㅠ 4 0.5솔 5 0.5솔 4,5번은 구현은 했지만 효율성에서 몇 개를 통과를 못 했다ㅠㅠ 일단 5번은 뭔가 사람들이 다 잘 풀었을 것 같아서 합격은 장담이 안될 것 같다. 그래도 아직 시간 많으니까 좋은 경험이었다. 문제를 풀어보면서 일단 4번에서 다익스트라 알고리즘이 나온 것 같은데 이 문제를 풀면서 다익스트라에 대한 이해도가 좀 더 높아진 것 같다(heap을 사용할 때 최소힙 최대힙 쓰자고 했던 것들을 막상 구현할 때 좀 생각을 못 한 것 같아서 아쉽다ㅠㅠ) 그리고 공부할 때 가끔 문제를 좀 선별해서 풀다보니까 도형 쪽 공부는 안 해왔던 게 탄로나..