killog

# you can write to stdout for debugging purposes, e.g. # print("this is a debug message") import heapq def solution(A): # write your code in Python 3.6 minusGroup=[] minusReverse=[] plusGroup=[] zero=False for i in A: if i0: heapq.heappush(plusGroup,-i) elif i==0: zero=True # 마이너스 2개 이상+ max 양수 answer=0 if len(minusGroup)>=2 and len(plusGroup)>0: a1=heapq.heappop(minusGroup) a2=heapq.heappop(min..

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

어려운 문제는 아닌데, 시간 조건이 까다로웠다. pop 이 leftpop 보다 빠른 속도인건지 아니면, 어차피 경우의 수를 세는 거라 다 도는데 있어 bfs 보다 dfs가 유리한 건지 모르겠지만 dfs 로 바꾸자 호다닥 맞다고 하는 경험을 했다. 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 ..

2021.03. 02 2021.03.09 답지봄 3번 틀리고 맞음 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이..

2021.03.02 2021.03.09 답지 봄(kks 블로그 참고) 구현할 용기가 없어 코드만 베껴봄... 대표적인 kmp 문제. 핵심 아이디어는 찾는 문자열의 j 를 저장한다는 개념과 fail 함수 개념이 중요하다. 꼭 다시 풀 문제. 문제 문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다. 예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다. 문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자. 입력 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. 출력 P가..

최소 스패닝 트리는 결국 다익스트라에서 will_visit 을 우선순위큐에 넣는 방식으로 푼다고 생각하면 된다. 다시한번 풀어볼것 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 ..

이걸 보고 어떻게 이분 탐색이라는 생각을 해내고 이분 탐색이라는 것을 여기에 어떻게 적용하지?? 에 대한 생각이 많았던 문제. 결국 참고 문헌을 봤다. 내가 보기에 이분 탐색이라는 것은 결국 전체에 주어지는 제한 조건수 제한 조건 이라는 키워드와 범위가 있음을 생각을 해야하는 것 같은데, 거기까지의 발상이 안된다. 구간 나누기 문제들을 좀 더 풀어야겠다. 문제 N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다. 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다. 구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다. ..

나는 아직 그리디에 약하다. 이 문제의 경우 시간 초과를 1시간 동안 받다가 포기했다. 오답노트를 해야한다고 생각해서 작성한다. 필수 핵심 아이디어는 문자를 ord 를 통한 수로 만들고, 그것을 index 로 접근하는 것이 주 방법인거 같은데 정확한 파악이 안된다. 이전 내 풀이는 왜 시간 초과지?? import collections import sys sys.setrecursionlimit(10 ** 4) input = sys.stdin.readline print = sys.stdout.write def iinput(): return int(input()) def lisinput(): return list(map(int, input().split())) def dq(a): return collectio..