본문 바로가기

알고리즘

[programmers] 더 맵게 로직 1. 우선순위큐를 이용해서 가장 작은 값, 두번째로 작은 값을 뺀 후, heappush를 이용해서 넣으면 값의 크기를 기준으로 들어간다. 2. 이때, 값을 두개를 빼야하기 때문에 scoville 리스트에 값이 두개 이상 들어가있어야 first, second로 뺄 수 있고, heapq구조이므로 첫번째 값이랑 K랑 비교해서 크면 뒤에 값들은 다 큰것이다. heapq구조이므로, 마지막으로 값이 하나 남아 있을 때, K보다 작으면 -1을 리턴한다. 코드 주의할 점 1. heapq 이해가 필요하다. heappop, heappush를 사용하기 위해서는 우선 리스트가 heapify로 정렬되어있어야한다. 더보기
[baekjoon] 15686. 치킨 배달 로직 1. 치킨집과 집을 구분한 다음에 M개의 치킨집을 combination으로 조합을 구한다. 2. 치킨집 조합과 집의 거리를 구할 것인데, 최종적으로 치킨집 조합의 최소값을 구하는 것이다. 그러면 집을 돌면서 치킨집과의 거리를 구한다. 각 집마다 최소 길이가 되는 치킨집을 택할 것이다. 그 합이 최소가 되는 거리가 답이다. 코드 더보기
[programmers] N으로 표현 로직 1. 계산된 값들을 저장하면서 그 값들을 가지고와서 계산한다. -> DP사용 1번 사용 : 5 2번 사용 : 55, 5+5=10, 5-5=0, 5*5=25, 5/5=1 3번 사용 : 555, 5+5+5=15, 5+5-5=5, 5+5*5=30, 5+5/5=6, 5-5+5=5, 5-5-5=-5, 5-5*5=-20, 5-5/5=4, 5*5+5=30, 5*5-5=20, 5*5*5=125, 5*5/5=5, 5/5+5=6, 5/5-5=-4, 5/5*5=5, 5/5/5=0, 555 + 1번사용->2번사용, 2번사용->1번 사용(중복은 제거) 4번 사용 : 555 + 1번사용->3번사용, 2번사용->2번 사용, 3번사용->1번 사용(중복은 제거) 코드 주의할 점 1. num_ls에 넣을 때, x-y, y-x를 동.. 더보기
[programmers] 가사 검색 로직 1. 만약 'fro??' 을 찾는다고 하자 (1) 길이가 5 인 곳으로 들어간다 (2) 거기서 f 로 들어간다. cnt에는 f로 시작하는 단어가 4개있다는 것을 저장한다. (3) r 로 들어간다. cnt에는 r로 시작하는 단어가 4개 있다는 것을 저장한다. (4) o 로 들어간다. cnt에는 o로 시작하는 단어가 3개 있다는 것을 저장한다. (5) ? 를 만나면 cnt 를 리턴. (6) fro 로 시작하면서 길이가 5인 단어는 마지막에 저장된 3개이다. 2. ** 문제점 : 이렇게 하면 효율성 3번에서 틀린다! why? 쿼리가 모두 ?로 구성된 경우 있음 ** 해결책 : 단어의 길이가 최대 1만까지이므로 1만까지의 배열을 만들고, 각 단어의 길이마다 몇개인지 저장 쿼리가 모두 ?로 구성 -> 찾지말.. 더보기
[programmers] 경주로 건설 로직 1. board를 돌면서 direction, cost를 함께 가지고 이동한다. 2. (0, 0)에서 밑으로 가는 것과 오른쪽으로 가는 것 두개를 각각 bfs를 사용해 가격을 확인한다. 3. x = y = len(board) - 1 이 되면 answer에 넣고, answer중에 최소값을 구한다. answer에 들어가는 값은 (0, 0, down)과 (0, 0, right)에서 각자 bfs를 돈 결과이다. 4. near에 (dx, dy, direction)을 넣은 다음에 (x, y)에서 near을 돌면서 xi, yi, new_cost를 구한다. 다음칸이 0이면서 visit[xi][yi]이 0이거나(아직 지나가지 않음) 기존의 값보다 작은 경우 새 가격으로 갱신해준다. 코드 주의할 점 1. bfs를 돌때.. 더보기
[programmers] 길찾기 게임 로직 ** 이 문제는 트리문제이다 ** 1. 트리를 순회하는 방법은 검색을 통해 쉽게 알 수 있으므로 문제가 되지 않습니다. 2. 이 문제의 핵심은 좌표 값으로 주어지는 노드들을 트리로 구성하는 부분입니다. 3. 트리를 만들기 위해 y값을 이용해서 각 노드의 level을 분리하고, 현재 노드의 자식노드가 가질 수 있는 x값을 이용해서 현재노드의 왼쪽, 오른쪽 자식을 정확하게 찾는 것이 중요하다 4. 각 노드의 왼쪽, 오른쪽 자식노드 찾기 - 먼저 노드 P의 x의 값을 Px, 현재노드의 자식노드가 가질 수 있는 x의 범위를 Lx, Rx(Lx 만약 현재 노드의 바로 다음 레벨에 Lx ≤ Kx K는 노드 P.. 더보기
[programmers] 자물쇠와 열쇠 로직 1. (key-1)*2+lock길이만큼의 board를 만든다. 2. key를 한칸씩 이동하면서 넣고, lock도 넣는다. 이때, board[i][j] != 1이면 멈춘다. 3. key 이동이 (0,0)부터 끝까지 갔으면, key를 90도 돌린다(함수만들기) 4. 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 코드 주의할 점 - for문을 돌릴 때 범위 설정이 중요!! (4중 for문을 돌지만, N, M 숫자가 작아서 괜찮다.) 더보기
[programmers] 셔틀버스 로직 - 일단 shuttle시간을 다 구한다(shuttle_time함수) - 사람들이 기다리고 있는 시간을 sort시켜서 순서대로 정렬하고 - 만약에 timetable이 m보다 작으면 굳이 계산할 필요없으니까 return shuttle[-1]을 하고 - 이제 각 shuttle마다 사람을 태울껀데, 셔틀 시간보다 빨리오거나 셔틀시간에 온 사람을 m명만 태우고, 태우게 되면 그 사람을 timetable에서 지운다(맨밑에 for j문) - 그러면 마지막 셔틀에 도착할꺼고 마지막 셔틀에서 cnt는 shuttle시간보다 빨리온사람, same은 shuttle시간에 맞춰온사람, check는 shuttle시간보다 빨리온사람의 index값으로 지정하고, cnt + 1할 때 cnt > m:이면 break시킨다. (이때, .. 더보기

티스토리툴바