로드 밸런서는 트리로 구성되어 부모 노드로부터 트래픽을 분산받게 되는데 현재 노드는 부모 노드로부터 받을 수 있는 모든 트래픽을 받고 다음 자식 노드로 분배하도록 구현해야 합니다. 예를 들면, 다음의 예시가 있습니다.단순히 DFS로 구현했을 때, 1번에 999가 들어온다면 9번과 10번에는 223, 221개씩 분배하게 됩니다. 왜냐하면 2번이 처리할 때, 1번으로부터 오는 333번을 9번과 10번에 분배하면 167, 166번이 들어가고 다음 5번으로부터 오는 111개는 56번과 55번으로 나눠지기 때문에 최종 223, 221로 나눠 원하는 정답을 얻을 수 없게 됩니다. 따라서 위상 정렬 아디이어를 이용하여 코드를 구현하는 방법으로 문제를 해결할 수 있습니다. indegree 배열을 이용하여 현재 노드의 ..
N x N 배열을 클러스터링할 때는 BFS를 사용했고 클러스터를 선택하는 탐색은 DFS를 사용했습니다. 3N줄에 걸쳐 입력되는 값을 열단위로 저장해 사용하면 자동차를 떨어뜨리는 로직을 구현하는데 매우 편해집니다.특히, 39번, 40번 테스트케이스에서 시간초과가 잘 발생하는데, 해설강의(https://www.youtube.com/watch?v=K4TWAtHuRNw)로부터 힌트를 얻었습니다. 아래 코드에선 near_same_color라는 함수를 추가하여 BFS 코드에서 사이즈가 1인 경우를 스킵하여 TLE를 피할 수 있었습니다. 제 생각으로는 BFS에서 적어도 한 번은 4번의 방향을 탐색해야 하는데 클러스터 사이즈가 1인 부분이 많은 경우 오버헤드가 되어버리는 이유가 아닐까 싶습니다.
가장 많이 받은 선물 그냥 구현하면 됩니다. HTML 삽입 미리보기할 수 없는 소스 도넛과 막대 그래프 정점을 찾고 생성된 정점(root)과 연결된 정점들에 대해 dfs로 탐색하면서 8자 그래프, 도넛 그래프인지 판단하고 생성된 정점과 연결된 간선에서 두 그래프의 수를 뺀 값이 막대모양 그래프의 수 입니다. HTML 삽입 미리보기할 수 없는 소스 카카오 블로그에 설명되어 있는 방법으로 풀었다면 더 짧은 코드로 해결할 수 있습니다. HTML 삽입 미리보기할 수 없는 소스 주사위 고르기 A와 B가 주사위를 골라 가능한 모든 수를 저장해두고 A가 B를 이길 수 있는 경우를 binary search로 찾아 누적한 뒤 가장 높은 승률을 가진 주사위 조합을 리턴합니다. HTML 삽입 미리보기할 수 없는 소스 n +..
돌 게임 문제는 DP로 쉽게 풀 수 있지만 미니맥스 알고리즘을 사용한 풀이도 가능합니다. 미니맥스 알고리즘 풀이를 찾아봤지만 없어서 직접 구현했습니다. 미니맥스 알고리즘은 서로 게임에 최선을 다하는 알고리즘입니다. 나는 상대방에게 이득이 되는 행동을 하지 않고 상대방도 나에게 이득이 되는 행동을 하지 않도록 탐색하는 알고리즘입니다. minimax(stone, player) 함수는 남은 돌의 개수(stone)과 나 또는 상대방인지를 알 수 있는 player 인자를 갖습니다. 마지막 돌을 가져가는 사람이 지는 것이므로 내가 마지막 돌을 가져가면 0(내가 지면), 상대방이 가져가면(내가 이기면) 1을 반환하도록 작성했습니다. 이제 내가 돌을 (1 or 3 or 4)개를 가져간 후 상대방의 리턴 값은 0(내가 ..
성격 유형 검사하기 그냥 구현하면 됩니다. HTML 삽입 미리보기할 수 없는 소스 두 큐 합 같게 만들기 생각보다 헷갈릴 수 있는 문제라고 생각합니다. queue1, queue2의 길이가 최대 300,000이므로 이중for문으로 탐색하면 TLE를 발생시킵니다. 따라서 두 큐를 합쳐 투포인터로 탐색하여 문제를 해결할 수 있습니다. i와 j 포인터는 i ≤ j < len(queue1+queue2)의 조건을 가지고 탐색하는데 이때 몇 가지 경우를 생각해볼 수 있습니다. 첫 번째는 두 포인터가 queue1에서 모두 위치한 경우입니다. 뒤쪽의 j 포인터가 가리키는 값까지 모두 queue2로 옮기고 원래 queue2에 있던 값들과 queue1의 i 포인터 앞까지 queue1으로 옮겨야 하므로 (j+1)+i+len..
신고 결과 받기 그대로 구현하면 됩니다. HTML 삽입 미리보기할 수 없는 소스 k진수에서 소수 개수 구하기 문제에서 주어진대로 n을 k진수로 변환하고 0과 0사이의 수가 소수인지 판별하면 됩니다. python에서 int(), bin() 등과 같이 k진수법으로 표현된 수를 10진수로 변환하는 함수는 있지만 10진수를 k진법으로 표현하는 함수는 없으므로 직접 구현해야 합니다. 변환하는 방법은 10진수를 2진수로 바꾸는 방법처럼 계속 나눠 나머지를 뒤에 추가하여 구현할 수 있습니다. def conv(n,k): base = '' while n > 0: n, mod = divmod(n, q) base += str(mod) return base[::-1] """ tc1 : n = 437674, k = 3 ----..
개인정보 수집 유효기간단순 구현 문제이고 "년.월.일" 형태를 "일"로 바꿔 계산합니다. 문제를 풀면서 날짜 계산에 주의해야 합니다.HTML 삽입미리보기할 수 없는 소스택배 배달과 수거하기문제가 지금도 잘 이해가 되지 않지만 "각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다." 라는조건을 통해 물건을 나눠 배달하거나 수거할 수 있다고 생각하여 다음과 같이 구현했습니다.HTML 삽입미리보기할 수 없는 소스이모티콘 할인행사각각의 케이스마다 완전탐색하여 구현할 수 있습니다.HTML 삽입미리보기할 수 없는 소스표현 가능한 이진트리어떠한 트리가 존재하고 완전이진트리가 될 수 있는 길이만큼 0으로 패딩했을 때 완전이진트리를 형성할 수 있는지 물어보는 문제입니다.이 문제의 중요한 ..
