본문 바로가기

전체 글190

가사 검색 (이진탐색/ binarysearch) 2020년 카카오 공채 문제중 하나인데, 시간이 꽤 걸렸고 문제를 일부분 제대로 안읽은 것을 뒤늦게 확인했습니다.. 검색문에 추가되는 ?는 접미사 혹은 접두사로만 포함되고 반드시 하나이상 포함됩니다. 문제는 찾으려는 query가 주어졌을때 존재하는 단어 리스트에서 ?를 포함해 존재하는 개수를 반환하는 것입니다. 각 쿼리에 대해 left, right를 찾아 개수를 구해주면 쉽게 구할 수 있고 처음에는 bisect_left, right를 사용하지 않았지만 사용시 보다 쉽게 풀 수 있습니다. (사용했었는데 처음에 문자열에 적용이 안된다고 나와서 그냥 구현으로 풀려 시도했습니다. 그런데 파이썬이 역시 그럴리가 없죠) 주의할 부분은 접미사 접두사에 따라서 문자를 뒤집어서 확인해줘야 올바른 사전순 탐색이 가능하기 .. 2021. 6. 14.
공유기 설치 (이진 탐색) n 개의 집이 수직선으로 존재하고 각 좌표값이 주어질때 c개의 공유기를 최대한 집을 많이 띄워서 설치할때 최대거리는 얼마가 될 수 있는지 묻는 문제입니다. 처음에 문제를 조금 헷갈렸는데, 이진탐색의 기준을 최대거리로 세우고 진행하면 쉽게 풀 수 있습니다. 또한 시작 start 및 end 또한 발생할 수 있는 최소거리 , 발생할수 있는 최대거리여야 하므로 1, nums[n-1]-nums[0]이 되야합니다. (저는 헷갈려서 nums[0], nums[n-1]로 설정해서 한번 틀렸습니다.) n, c = map(int, input().split()) nums = [] for i in range(n): a = int(input()) nums.append(a) nums.sort() def binary_search(n.. 2021. 6. 14.
정렬된 배열에서 특정 수 의 개수 구하기. 정렬이 되어있지 않다면 정렬을 해주고, 만약 정렬이 되어 있따면 이진탐색을 통해 O(log n) 탐색이 가능합니다. 이진 탐색을 통해 해당 수를 탐색하며 target 값과 일치할 때 해당 값이 그 값중에 최대한 왼쪽 인덱스인지 혹은 오른쪽 인덱스인지 확인하면 됩니다. 해당 수가 0 인덱스이거나 현재 값이 target과 동일한데 그 이전 값이 target보다 작은 경우 해당 값중 가장 왼쪽이라 할 수 있습니다. 혹은 오른쪽은 이의 반대로 탐색가능합니다. n, x = map(int, input().split()) nums = list(map(int, input().split())) def find_first(nums,target): start = 0 end = len(nums)-1 while start=ta.. 2021. 6. 14.
작성의 원칙 https://brunch.co.kr/@chaeminc/652 여러 번 읽어봐야 기억에 남지 않는다 3장을 읽고 | 시험공부 할 때 대부분 2번, 3번 읽는다. 처음엔 어렵지만, 밑줄 치고 필기하며 읽다 보면 머리에 들어오는 느낌이 든다. 실제로 여러 번 읽자마자 시험을 보면 기억 brunch.co.kr 공부를 할 때는 시험을 자주 보는게 가장 좋다고 합니다. 인출 효과는 시험보다 상위 개념으로 시험이 효과가 있는 이유는 기억이 작동하는 원리가 담겨 있기 때문입니다. 뇌는 넣은 것을 꺼낼 때, 꺼낸 것을 남기고, 자주 꺼낼수록 기억에 더 남습니다. 시험 말고도 요약, 토론, 암송, 발표 등 공부한 것을 어떤 식으로든 꺼내면 기억에 오래 남게 된다는 원리입니다. 분산/교차 효과는 사람은 한 번에 많은 걸 .. 2021. 5. 25.

티스토리툴바