코딩관계론

아이디어 도출 방법 나는 힌트를 k와 room_number의 숫자 차이로 알았다. k의 max는 10^12지만, room_number는 최대 20만이기 때문이다. 다음으로는 방의 점유 여부를 표시하기 위해서 해당 room_number을 key로 하고 value는 [점유여부, 다음 방 번호]를 가지는 dict 클래스를 생성했다. 해당하는 방 번호에 사용자가 있는지 확인하는 방법은 두 가지가 있다. 최대 O(K)만큼 돌면서 dict [room_number]을 호출하는 방식 union find 알고리즘을 사용해 O(1)에 확인하는 방법 이번 문제의 KEY는 union find short path 알고리즘을 아느냐가 제일 중요했다. Union Find short path 문제에서 초기 상태는 아래와 같이 구성된..

아이디어 도출 방법 해당하는 문제를 읽다가 보면 양방향 연결 리스트 느낌을 받을 수 있다. 왜냐하면 양방향 연결 리스트의 특징을 생각해보면 노드를 찾는 과정에서 o(n), 삭제 및 삽입 과정에서는 o(1)이 되도록 구현할 수 있기 때문이다. 또한 이번 문제에서는 특정 노드를 탐색하는 과정 없이, 지시에 따라서 현재 무슨 노드(파란색)에 위치하고 있는지만 체크하면 된다. 문제에서 원하는 복구 과정 역시 스택을 떠올리면 쉽게 해결할 수 있다, 스택은 선입 후출의 자료구조로 나중에 들어오는 것이 빨리 나간다. 한 가지 까다로운 점은 복구하는 과정이었다. 처음에는 삭제한 노드에서 가장 가까이 살아있는 노드를 찾는 방법을 사용해 삭제된 노드를 다시 삽입하려고 했지만 시간 초과가 발생했다. 하지만 다시 생각해보니 ..

아이디어 도출 방법 1. 항상 시간문제는 단위 통일하는 것이 핵심이다. 제일 작은 단위인 초로 통일하는 것을 추천합니다. 2. 초를 사용하면 시간순으로 정렬할 수 있으니 사람들이 도착하는 시간과 버스가 출발하는 시간을 비교해서 버스에 탑승 가능한 승객들을 deque에서 삭제해준다. #탑승객과 미잠 while time_table and bus_go < n: """마지막 버스전까지 모든 탑승객을 태운다. """ arrive_time = time_table.popleft() if arrive_time

아이디어 도출 방법 1. 주어진 입력에서 트리를 구성하는 방법은? 트리는 root node가 하나만 존재함으로 y축이 제일 높은 node가 root일 수 밖에 없다. nodeinfo.sort(key=lambda nodeinfo:(-nodeinfo[1], nodeinfo[0])) root 노드를 기준으로 x 값이 root보다 작으면 왼쪽, 크다면 오른쪽으로 분리해주면 된다. root_node = nodeinfo.pop(0) make_tree([node for node in node_list if node[0] root_node[0]]) 증명 y축으로 정렬하면 아래와 같은 그림이 형성되어..

아이디어 도출 방법 1. 먼저 효율성을 생각하지 않고 정확성 위주로 문제를 해결하려고 했다. 방송이 중단된 시간(k)만큼 돌면서 food_time[index]의 시간을 1초씩 감소시켜준다. idx = 0 for i in range(k): remove_food_time(food_time[idx]) idx += 1 2. 순차적으로 1초씩 줄이면 탈락하는 문제로 한번에 하나씩 삭제할 수 없을까 생각을 했다. 한 번에 FOOD_TIME [idx]의 시간을 0으로 만들 수 있다면 연산의 복잡도가 배열 길이에 따라 변한다. 그럼 어떤 Index가 먼저 0이 될까? 답은 간단하게 FOOD_TIME 중 최소 값이 먼저 사라진다 그럼 해당 Index를 0으로 만들 때 필요한 시간 계산은 어떻게 할 까? FOOD_TIME..

아이디어 도출 방법 1. 먼저 방향성, 최단 거리등의 키워드를 통해서 BFS 탐색이 떠올랐다. 하지만 이동 타입이 두 개라는 점이 생각을 어지럽게 했다. 언제는 cntrl 키를 눌러서 이동해야 하고, 언제는 한 칸만 이동하면 될까 -> 결국 4*4의 맵임으로 완전 탐색으로 진행하기로 했다. 2. 같은 카드가 두 개 있는데 무엇부터 시작해야 할까? (A:어파치 카드1, A1:어파치 카드2) 처음에는 그리디 하게 X- > A와 X -> A1 비용 중 싼 이동 가격으로 완전 탐색을 진행했다. 하지만 틀렸다. 그리디는 최적이 아니다. 따라서 모든 순서에서 시작해야 한다. X -> A -> A1로 가는 것과 X -> A1-> A로 가는 것은 종료 위치가 달라지기에 결과 값에 영향을 미칠 수 있다. 아이디어는 어렵..

이 풀이를 읽기 전 태상이의 훈련소 생활 문제를 푸시는 것을 추천드립니다(풀이:https://bjwan-career.tistory.com/4) 풀이 "재생 시간을 간단하게 구하는 방법이 없을까?" 10:43:20 ~ 12:22:57의 재생 시간을 원본 문자열 그대로 구하려면 상당히 힘들다. 한 가지 방법은 초로 통일하여 계산하면 간단하게 재생 시간을 구할 수 있다. 또한 다른 이점은 구간을 나눠서 재생 시간을 계산하지 않아도 된다. 해당 초에 몇 명이 봤는지 알 수 있다면 최종 재생시간을 구할 수 있다. '해당 초에 몇 명이 동영상을 시청하고 있다'를 빠르게 구할 수 있는 방법은 없을까?" 누적합을 사용하면 해당 초에 몇 명이 시청하는지 알 수 있다 동영상의 시작 부분과 종료 시간을 초로 변경한 후 해당..

링크 순위검색 풀이 "주어진 문자열을 어떤 방식으로 split할 것인가?" 완전탐색을 이용해 풀려고 했으니 특정 문자열을 내가 원하는 형식으로 만드는 것이 가장 중요하다. 먼저 주어진 query가 info 형식으로 변환될려면 " and" -> ""로 변경한 후 split(" ")을 하면 된다. "후보 쿼리는 어떤 방식으로 생성한 것인가?" 먼저 후보 쿼리를 직접 만들면 몇 개의 후보가 나올 수 있을지 생각을 해보자. 경우의 수는 두 가지 임으로 2 x 2 x 2 x 2 = 16개의 후보가 생성된다. 그럼 어떤 방식으로 생성할 것인가 조합함수를 이용해서 해당하는 인덱스를 '-' 문자열로 변경하면 모든 후보군을 생성할 수 있다. "정렬된 리스트에서 특정 값을 빠르게 찾는 방법" 이분 탐색을 수행하면 된다. ..

1. 문제 상황프로젝트가 example 도커 이미지를 빌드하기 위해선 기반 파일인 src 파일을 빌드해야 한다. example 코드를 수정하던 중에 src 코드 수정이 필요하다면 src 파일을 --no-cache로 빌드했다.  src의 환경이 변하는 것이 아니라 코드만 변했을 뿐인데 기존 pkg를 다운하고 다시 설치하는 것은 불필요한 시간을 잡아먹고 있었다. FROM nvcr.io/nvidia/l4t-base:r32.6.1# Keeps Python from generating .pyc files in the containerENV PYTHONDONTWRITEBYTECODE=1# Turns off buffering for easier container loggingENV PYTHONUNBUFFERED=1A..

결론부터 말하자면 Thread 문제가 아니라 이 액션과 상관없는 네트워크 타임에 의해서 발생하는 문제였다. 해결 방법1. time.time모듈을 이용해 각 구간의 프로그램 실행 시간을 체크함2. request에서 매번 필요한 keyword를 파싱하는 방법이 아니라 request를 한번만 파싱하고 default dict을 이용하는 방법을 사용함dev_name = self._parsing_keyword(request, "dev_name")cmd = self._parsing_keyword(request, "cmd")min_threshold = self._parsing_keyword(request, "min")max_threshold = self._parsing_keyword(request, "max")----..

풀이 각 메뉴들을 조합하여 리스트에 저장하고, 각 course 개수의 best like를 구해주면 된다. 코드 from collections import Counter from collections import defaultdict import itertools def solution(orders, course): answer = [] cand_comb_menu = [] for num in course: for order in orders: comb_menues = list(itertools.combinations(order, num)) #AC, AD, AE for comb_menu in comb_menues: comb_menu = sorted(comb_menu) cand_comb_menu.append(..

풀이 연속된 문자열의 깔끔한 처리 코드 "연속된 문자를 복잡하게 처리하는 코드" def get_rule2(id): new_id = "" for i in range(len(id)): if not id[i].isalpha() and not id[i].isdigit(): if not id[i] in ['.', '-', '_']: continue new_id += id[i] return new_id def get_rule3(id): new_id = "" end = -1 for i in range(len(id)): if not id[i].isalpha(): if id[i] == '.': end = i for j in range(i + 1, len(id)): if id[j] != '.': break end = j ..