Jeongchul Kim
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 ..
2018년 카카오 blind 코딩 테스트 - 길 찾기 게임 python 문제 설명 : 길 찾기 게임 - 이진 트리(binary tree) 검색길 찾기 게임전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다.내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다. 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다. 그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 ..
2018년 카카오 blind 코딩 테스트 - 무지의 먹방 라이브 python 문제 설명 : 무지의 먹방 라이브 : Greedy무지의 먹방 라이브* 효율성 테스트에 부분 점수가 있는 문제입니다. 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다.각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.마지막 번호의 음식..