로드 밸런서는 트리로 구성되어 부모 노드로부터 트래픽을 분산받게 되는데 현재 노드는 부모 노드로부터 받을 수 있는 모든 트래픽을 받고 다음 자식 노드로 분배하도록 구현해야 합니다. 예를 들면, 다음의 예시가 있습니다.단순히 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인 부분이 많은 경우 오버헤드가 되어버리는 이유가 아닐까 싶습니다.
2023 삼성 하반기 코딩테스트 오후 1번 문제입니다. 기절된 산타에게 루돌프가 충돌하는 경우 다시 기절하도록 구현해야 하고 산타 이동시 거리가 줄어드는 방향으로 움직여야 합니다. 만약 거리가 줄어드는 방향이 없다면 그 자리에 가만히 있어야 합니다. HTML 삽입미리보기할 수 없는 소스
가장 많이 받은 선물 그냥 구현하면 됩니다. HTML 삽입 미리보기할 수 없는 소스 도넛과 막대 그래프 정점을 찾고 생성된 정점(root)과 연결된 정점들에 대해 dfs로 탐색하면서 8자 그래프, 도넛 그래프인지 판단하고 생성된 정점과 연결된 간선에서 두 그래프의 수를 뺀 값이 막대모양 그래프의 수 입니다. HTML 삽입 미리보기할 수 없는 소스 카카오 블로그에 설명되어 있는 방법으로 풀었다면 더 짧은 코드로 해결할 수 있습니다. HTML 삽입 미리보기할 수 없는 소스 주사위 고르기 A와 B가 주사위를 골라 가능한 모든 수를 저장해두고 A가 B를 이길 수 있는 경우를 binary search로 찾아 누적한 뒤 가장 높은 승률을 가진 주사위 조합을 리턴합니다. HTML 삽입 미리보기할 수 없는 소스 n +..
문제를 그대로 구현하면 됩니다. 회전하는 부분이 있어 코드가 좀 더럽습니다. 예술성을 계산하는 부분에서는 맞닿아 있는 변의 수를 체크하기 위해 map 자료구조를 사용했습니다. 아래 방향과 오른쪽 방향만 체크하여 중복되지 않게 작성했습니다. HTML 삽입 미리보기할 수 없는 소스
2023 삼성 상반기 코딩테스트 오전 2번 문제입니다. 최대 2000마리의 토끼를 빠르게 선택하기 위해 우선순위 큐를 이용했습니다. 이 문제에서 생각해봐야 할 것은 토끼의 이동입니다. 토끼의 이동은 최대 10억을 가질 수 있으므로 한 칸씩 이동할 수 없습니다. 현재 위치와 방향에서 같은 위치와 방향을 가리킬 때까지 토끼가 이동할 거리는 2 * ((N or M) - 1) 이므로 나머지 연산으로 계산량을 줄여야 합니다. HTML 삽입 미리보기할 수 없는 소스
2023 상반기 삼성 코딩테스트 오전 1번 문제입니다. 문제에 나와있는 대로 함수를 구성하고 구현하면 됩니다. 공격자와 희생자 선정은 필요한 값을 저장하여 정렬하는 것으로 찾을 수 있습니다. 공격자와 희생자의 선정 방법이 완전히 반대이므로 정렬 후 공격자는 첫 번째, 희생자는 마지막 값을 리턴하면 됩니다. 레이저 공격이 실패하면 포탄 공격으로 넘어가므로 레이저 공격을 하는 함수에 true / false 리턴값을 넣어 레이저 공격이 성공했는지 실패했는지 알 수 있도록 합니다. 공격시 레이저와 포탄을 사용하는데 레이저 공격은 최단경로를 이용하므로 bfs를 사용하면 됩니다. 이 문제에서 주의할 점은 범위가 넘어가면 반대편이 된다는 것입니다. HTML 삽입 미리보기할 수 없는 소스
2개월 전에 갑자기 뜬금없는 메일이 하나 도착했습니다. 메일을 확인해보니 작년 하반기 SKT T-worx 코딩테스트에서 상위 5%이내 들었다고 하며 탑프로그래머스 인증뱃지를 달 수 있는 기회라고 안내받았습니다. 밑에 설문 링크가 첨부되어 있어 설문을 완료하면 다음날에 프로그래머스 프로필에 탑프로그래머스라는 뱃지가 달리게 됩니다. 따로 돈내는 것도 아니고 단순히 프로그래머스를 이용하는 채용담당자분들에 눈에 띄는 정도로만 알고 있어서 그냥 달아봤습니다. 2개월간 어떤 변화가 있는지 기다렸지만 현재까지 연락이 오거나 하는 것은 없었습니다...