본문 바로가기
2020 카카오 인턴십 - 보석 쇼핑, 파이썬 문제 프로그래머스 카카오 코딩 테스트 문제 링크 풀이 난이도 : 레벨 3 gems 배열 크기는 최대 100,000 이기 때문에 O(N^2)으로 풀면 시간 초과가 난다. 따라서 start, end 두개의 포인터를 조작하는 투포인터 알고리즘을 활용 보석의 종류별로 최소 1개 이상의 수량이 있을 때까지 right를 1씩 더해줌 최소 1개 이상의 수량이 확보되었으면 left를 1씩 움직여가며 중복된 보석을 제거해줌 gems 배열 끝까지 위 단계를 반복해 cand 배열에 넣은 후 구간 길이가 짧고, 같다면 left 크기가 작은 원소를 리턴한다. 코드 from collections import defaultdict def solution(gems): cand = [] left = right = 0 N, gem_nu..
[DB/자료구조]B+ tree(B+ 트리)란? B-tree란? B-트리는 트리형 자료구조, 이진트리를 확장해서 더 많은 child node를 가질 수 있게한 일종으로 Balanced-Tree이다. 즉 삽입과 삭제가 일어나도 최대한 균형을 유지해 이진탐색의 효율을 살리는 트리이다. 특징 모든 leaf node가 루트로부터 같은 거리 각 노드별로 가능한 children 중 적어도 절반은 가지고 있다(웬만하면 balance되어있는) 루트 노드는 예외 B+ 트리는 B-tree를 개량한 트리로 Inner Node에는 Key만 저장하고 Leaf Node에 Key와 Data를 함께 저장한다. 데이터 접근 시간복잡도가 O(1)인 hash table보다 부등호 연산에 효율적 등호 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조로 적합하지 않음 B+ T..
[프로그래머스] 스티커 모으기(2)- 파이썬 문제 프로그래머스 Summer/Winter Coding(~2018) 문제 링크 풀이 난이도 : level 3 예전 문제들은 이렇게 딱 기본 문제로 나온 것 같은데 요즘 추세는 장황한 문제가 나오는 편이다. DP로 풀었다. leet code에서도 비슷한 문제를 좀 더 깔끔하게 푼 풀이를 본 것 같은데 아래 코드는 그다지 깔끔하지는 않다. 원형이기 때문에 첫 번째를 포함하면 마지막 스티커를 포함할 수 없어 케이스를 나누어 계산하였다. dp_y는 포함케이스, dp_n는 불포함 케이스로 계산하여 풀어주었다. dp[idx]는 각 idx 까지의 최대값이다. idx 위치에서 스티커를 포함한다면 그 전단계를 포함하지 못하므로 idx -2 위치의 최대값을 포함, 그렇지 않다면 최대값은 idx -1 위치의 최대값이다. 마..
[OS]교착상태와 교착상태 방지 교착상태(dead lock)이란? 첫 번째 스레드는 두 번째 스레드가 들고 있는 객체의 락이 풀리기 기다리고, 두 번째 스레드 역시 첫 번재 스레드의 락이 풀리기를 기다리는 상황을 말한다. 즉 모든 스레드가 락이 풀리기를 기다리고 있어 무한 대기중인 상태에 빠지는 것이다. 교착 상태에 빠지기 위한 네 가지 조건 상호 배재(mutual exclusion) : 한 번에 한 프로세스만 공유 자원을 사용할 수 있을 때 점유 대기(hold and wait) : 공유 자원에 대한 접근 권한을 갖고 있는 프로세스가, 그 접근 권한을 양보하지 않은 상태에서 다른 자원에 대한 접근 권한을 요구할 때 비선점(preemption) : 한 프로세스가 다른 프로세스의 자원 접근 권한을 강제로 취소할 수 없을 때 순환대기(cir..
[OS] 동기와 비동기 동기와 비동기라는 개념은 OS에서만 쓰이는 개념은 아니지만 자주 언급되는 내용으로 간단히 정리하고 넘어가겠습니다. 동기(Synchronous)란? 동기란 말그대로 동시에 일어난다는 뜻입니다. 요청과 결과가 동시에 처리되고 요청과 처리가 순서대로 일어날 때 동기적 처리라 합니다. 따라서 비동기란 요청 순서에 따라 처리되지 않는 경우 등의 경우를 말합니다. 동기와 비동기 장단점 동기 동기적 처리는 작업의 순서가 중요한 경우 사용되며 설계가 간단하고 직관적입니다. 다만 한 가지 일이 끝날 때까지 다른 일을 못하므로 해당 작업 처리 시간이 길어질 때 다른 일을 못한다는 단점이 있습니다. system call을 보낸 후 응답을 받을 때까지 대기 상태에 있다 응답을 받은 후 종료 비동기 반대로 비동기 작업의 경우 ..
[프로그래머스]2020 카카오 인턴십- 경주로 건설, 파이썬 문제 ㅍ로그래머스 경주로 건설 문제 링크 풀이 경로문제, 벽이 있는 문제이므로 아래, 위, 오른쪽, 위 4가지 방향으로 모두 움직이는 케이스를 고려해야 한다. 비용은 상하 에서 좌우로 변할 때 600원 상하, 좌우끼리는 100원 소요되므로 상하는 -1, 좌우는 1 값을 넣어 계산해줬다. 다음에 위치할 수 있는 위치(상하좌우로 이동, 0~N 사이의 위치, 벽이 아닌 경우)를 계산한다. check 배열을 만들어 초기값으로 무한을 주고 check 배열에 들어있는 값보다 같거나 작을 경우 큐에 추가해준다. check 배열을 만들지 않으면 무한루프에 빠짐 x == N-1 and y == N-1 마지막에 도달하면 지금까지의 비용을 cand 배열에 넣고 최소값을 리턴한다. 뭔가 좀 지저분하게 푼 것 같은데 나중에 다..
[DB] SQL - Join 의 종류 JOIN 이란? 2개 이상의 테이블을 논리적 관계를 기준으로 데이터를 검색하여 연결 Join이 왜 필요한가? 관계형 데이터베이스 정규화를 수행하면 저장 공간의 효율성과 확장성이 향상되지만 서로 관계있는 데이터가 여러 테이블로 나뉘어져 데이터를 효과적으로 검색하기 위해서는 조인이 필요함 Join의 종류 INNER JOIN(내부 조인) : 공통으로 들어가 있는 값을 결과 집합으로 만듦 NATURAL JOIN : 두개 스키마의 교집합의 attribute의 값이 같다면 합쳐줌 OUTER JOIN(외부 조인) :INNER JOIN 문을 포함하고 한쪽에만 내용이 있더라도 지정한 기준 테이블에 있는 모든 데이터를 가져옴(null 밸류로) LEFT, RIGHT, FULL OUTER JOIN CROSS JOIN(교차 조..
[프로그래머스] Summer/Winter Coding(~2018) - 기지국 설치, 파이썬 문제 프로그래머스 기지국 설치 링크 풀이 레벨 3 예전에 나온 문제들은 확실히 쉬운 편이다. 점점 문제도 길어지고 시간이 걸리는 문제가 나오는 것 같다. 컨디션 난조로 집중이 안돼서 그냥 대충 풀었다. 좀 더 고민하면 깔끔한 코드를 구현할 수 있을 것이다. 코드 def solution(n, stations, w): prev = 0 ans = 0 for i, station in enumerate(stations) : pos = station - w - prev - 1 prev = station + w num = 2*w + 1 if pos % num == 0 : ans += pos//num else : ans += pos//num + 1 if i == len(stations) - 1 and station +..

티스토리툴바