Jeongchul Kim

python 부분합, 연속 부분수열 최대합부분합부분합은 배열의 시작부터 현재 위치까지의 원소의 합을 구해둔 배열(paritial_sum)입니다.다음의 표를 보면 partial_sum을 미리 계산하면 특정 구간의 합을 O(1)에 구할 수 있습니다. index012345scores[]10095801007065partial_sum[]100195275375445510 예를 들어 3번째부터 5번째의 합을 구하고 싶다하면 partial_sum[5] - partial_sum[3-1] = 510-275 = 235를 구할 수 있습니다.이 공식을 이용하면 구간합을 구할 수 있게 됩니다. def partial_sum(arr, a, b): arr = [0] + arr partial_sum = [0] * len(arr) for..

Python 구간 사이의 최소 제곱근 찾기 문제설명A, B의 두 개 정수 구간 사이에서Square Root의 최대 반복된 적용된 정수값을 반환하면 됩니다. A가 10, B가 20인 경우에 살펴보면 구간 사이에 10,11,12,13,14,15,16,17,18,19,20 값이 있습니다. 여기서 sqrt가 최대로 적용된 최소 제곱근 정수값을 찾아보면16은 16->4->2가 되므로, 함수는 2를 반환하면 됩니다. A가 3000, B가 6000인 경우를 보면 4096은 4096->64->8로 떨어지므로, 함수는 8을 반환하면 됩니다. A와 B는 2 ~ 1,000,000,000 사이의 값입니다. [1] math.sqrt를 쓰면 float형이 나온다. 이는 정수로 나눠 떨어지는 것을 확인해보기 위해서는int(math..

graph shortest path - 최단 경로 다익스트라 알고리즘 python다익스트라 알고리즘하나의 정점(node) A에서 다른 정점 B까지 최단 경로를 구한다. 이 때 간선들은 양의 weight를 가져야 한다.시작하는 A를 제외하고는 나머지 node는 미방문으로 초기화하고, 연결되지 않은 값은 inf(무한대)로 표시한다. 시작하는 node에서부터 연결된 노드들의 edge 값을 확인한다. edge 값 중에서 가장 짧은 edge를 선택하여 node의 값을 업데이트 합니다. 그 다음 노드에서도 마찬가지로 인접한 노드들의 edge를 확인하고 선택한다. 경로에 필요한 edge들의 합을 통해서 node를 업데이트 한다. 다익스트라 알고리즘은 방문하지 않은 노드가 없고, 목표 지점인 B까지 도달하면 멈추고, ..

2017년 카카오 blind 코딩 테스트 - 뉴스 클러스터링 python 문제 설명 : 뉴스 클러스터링뉴스 클러스터링여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다. 개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 카카오 신입 개발자 공채 관련 기사를 검색해보았다. 카카오 첫 공채..'블라인드' 방식 채용카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용카카오, 블라인드 전형으로 신입 개발자 공채카카오 공채, 신입 개발자 코딩 능력만 본다카카오, 신입 공채.. 코딩 실..

2017년 카카오 blind 코딩 테스트 - 추석 트래픽 python 문제 설명 : 추석 트래픽추석 트래픽이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 입력 형식solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.응답완료시간 S는 작년 추석인..

Queue 큐 python 큐는 FIFO(First Input First Out, 선입 선출)입니다. 가장 먼저 들어간 자료를 가장 먼저 꺼내게 되죠.쉽게 예를 들면 음식점에서 기다리는 줄을 생각해보면, 먼저 기다린 사람이 먼저 입장하게 되죠 큐에 원소를 넣는 작업을 enqueue, 원소를 꺼내는 작업을 dequeue이라고 합니다.두 연산은 O(1)에 이루어져야 합니다. Python에서 Queue를 다뤄보죠 python 2에서는 Queue라는 라이브러리가 따로 있습니다. import Queue queue = Queue.Queue() queue.put(1) # push queue.get() # pop https://github.com/KimJeongChul/algorithm-python/blob/maste..

stack 스택 python 스택은 LIFO(Last Input First Out, 후입 선출)입니다. 나중에 들어온 것이 가장 먼저 꺼내게 됩니다.함수 호출이 끝나고, 이전 context로 돌아 갈 때 사용 됩니다. 스택에 원소를 넣는 작업을 push, 원소를 꺼내는 작업을 pop이라고 합니다. 두 연산은 O(1)에 이루어져야 합니다. 스택을 활용한 문제를 쉽게 예로 들면 괄호 (), {}, [] 앞 뒤로 짝을 맞추는 Parentheses 문제에서 사용 가능합니다.Parentheses 은 한 번 열린 괄호는 반대편에서 순서대로 닫혀야 합니다. { { { { } } } { { } } } { }{ 여는 괄호라면 push()로 넣고, }는 괄호라면 pop()로 꺼내서 괄호와 서로 맞춰보면 됩니다. 다르다는 ..

codility - binary gap python 문제 설명 : binary gapA binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N. For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 ..