날짜: 2022년 5월 24일 오후 7:27 코드 Algorithm/92345.py at main · Junroot/Algorithm 풀이 모두가 이상적인 플레이를 했을 때 승자와 패자가 이미 결정되어있는 31게임이 생각났다. 31게임의 전략에서 힌트를 얻어서 구현을 했다. 31게임의 승자의 기본전략은 마지막으로 30, 26, 22, 18, …., 2를 말하는 것이다. 이를 dicision tree로 그려볼면 이렇게 된다. 여기서 빨간색 테두리는 승자가 항상 승리할 수 있는 전략이 있는 상태를 표시해둔 것이다. 이를 승자 노드에서 보면 다음으로 가는 노드에 항상 승리할 수 있는 상태인 것이 최소 하나만 있으면 된다....
날짜: 2022년 5월 25일 오후 6:31 오답: o 코드 Algorithm/92344.py at main · Junroot/Algorithm 풀이 잘못된 풀이 처음에 접근한 방법은 중복된 연산(덧셈, 뺄셈)을 피하기 위해서 배열의 표현을 자신의 왼쪽 또는 위쪽의 차이로 나타내려고 했다. 만약 자신의 왼쪽의 차이로 표현하면 아래 사진과 같다. 이렇게 하고 배열의 가로 길이가 더 길도록 transpose 하면 해결될 것이라고 생각했다. O(배열 세로 길이 * skill 길이)로 최악의 경우는 31 * 250000지만 시간초과가 발생했다. 맞는 풀이 결국 다른 사람 풀이를 확인했다....
날짜: 2022년 3월 19일 오전 1:59 코드 Algorithm/92343.py at main · Junroot/Algorithm 풀이 단순한 백트래킹 문제였다… 트리의 특성을 이용하는 건줄 알고 너무 어렵게 생각했다. 데이터의 개수가 적으면 단순 탐색도 가능하다는 것을 신경써야되는데 이 부분을 놓쳤다.
날짜: 2022년 5월 18일 오후 10:09 코드 Algorithm/92342.py at main · Junroot/Algorithm 풀이 두 가지 문제로 나눠서 생각할 수 있다. 어피치와 라이언의 점수 차이 계산하기 점수차이를 최대로 나도록 라이언이 쏘는 방법 구하기 어피치와 라이언 점수 차이를 계산하기 위해서 어피치가 점수를 얻은 영역에 더 많이 맞추면 점수를 2배로 얻는 것으로 구현을 했다. 어피치가 점수를 잃고 라이언이 점수를 얻는 것이 결국 라이언이 점수를 2배로 얻는 것과 같기 때문이다. 점수차이를 최대로 나는 경우를 찾기 위해서 dfs를 이용해서 모든 경우를 탐색하도록 구현했다....
날짜: 2022년 5월 16일 오후 2:40 코드 Algorithm/92341.py at main · Junroot/Algorithm 풀이 단순 구현 문제다. record 정보를 파싱해서 원하는 데이터 형태로 저장한다. 시간 정보는 0시 0분을 기준으로 지나간 시간을 분 단위로 저장했다. 차량 정보는 dictionary를 통해서 저장을 해두고 최종적으로 반환을 할 때는 정렬을 시켰다.
날짜: 2022년 5월 9일 오후 2:14 코드 Algorithm/92334.py at main · Junroot/Algorithm 풀이 자신을 신고한 유저들을 저장해서 개수를 세면된다.
날짜: 2022년 5월 13일 오후 2:37 오답: o 코드 Algorithm/81305.py at main · Junroot/Algorithm 풀이 문제 해석을 다르게 해야되는 과정이 어려웠다. 모든 간선을 잘라보는 것은 당연히 시간초과가 발생한다. 각 그룹의 인원을 L명 이하로 만들기 위해서 몇 개의 그룹이 필요한지 구하는 문제로 바꾸고, 이 그룹의 수가 처음으로 k가되는 L을 바이너리 서치로 풀어야된다. L의 범위가 (총 인원/ k)~(총 인원) 사이라는 것을 알면 바이너리 서치로 접근할 수 있다. 1번 소문제를 해결하기 위해서 dfs를 이용했다....
날짜: 2022년 5월 3일 오후 5:57 오답: o 코드 Algorithm/81304.py at main · Junroot/Algorithm 풀이 처음에 문제를 이해하는데 시간이 걸렸다. 똑같은 함정 방에 돌아가면 모든 간선의 방향이 원래대로 돌아가는 문제로 이해했다. 현재 방문했던 함정방으로 비트마스크로 표현하는 것까지는 쉽게 접근했다. 하지만 n의 크기가 1000이여서 int 범위 밖의 비트마스크 표현에 문제가 있었다. 이부분은 함정방이 10개이하이므로 좌표 압축을 통해 해결했다. 현재 노드와 이동할 노드에 함정 활성화가 모두 켜저있거나 모두 꺼져있으면 정방향, 하나만 켜져있으면 역방향으로 이동하도록 구현했다....
날짜: 2022년 5월 2일 오후 5:05 코드 Algorithm/81303.py at main · Junroot/Algorithm 풀이 가장 최근에 삭제된 행을 복구하는 기능을 쉽게 구현하기 위해서 처음에는 array를 만들어 soft delete 와 형식으로 구현하려고 했다. 하지만, 이럴 경우 삭제된 행이 많을 때 행을 이동하면 soft delete되어있는 행은 이동한 것으로 간주하면 안되므로 계산량이 늘어나는 문제가 있었다. 이를 해결하기 위해서 LinkedList를 만들어서 문제를 해결했다.
날짜: 2022년 5월 2일 오후 5:01 코드 Algorithm/81302.py at main · Junroot/Algorithm 풀이 대기실의 크기가 5*5로 고정이고 대기실의 개수 또한 5개로 고정이므로 시간복잡도를 크게 고려하지 않아도 해결이 가능하다. 응시자가 앉아 있는 자리를 기준으로 BFS를 통해 길이가 2인 지점 이내에 다른 응시자가 있는지 확인한다.
날짜: 2022년 5월 2일 오후 4:59 코드 Algorithm/81301.py at main · Junroot/Algorithm 풀이 문자열의 길이가 최대 50이므로 어렵지 않다. 문자열을 하나씩 확인해서 숫자로 바꾸면 된다.
날짜: 2022년 3월 11일 오후 11:20 코드 Algorithm/77486.py at main · Junroot/Algorithm 풀이 위상 정렬을 사용했다. 위상 정렬을 사용하기 위해서 멤버 이름으로 id를 찾거나 id로 이름을 찾아야되는 경우가 있어서, dictionary를 2개 사용했다. 위상 정렬로 수수료를 계산할 때 2가지 문제가 있었다. 현재 멤버의 수익의 10%를 그대로 부모 멤버에게 주면 오답이 된다. 자신의 자식 멤버에게서 받은 수수료를 각각 10%씩 구하고 일의자리 아래는 버림해야되기 때문에, 자식으로부터 받은 수수료를 바로 더하지 않고, 리스트로 관리해야됐다....
날짜: 2022년 3월 23일 오후 10:09 코드 Algorithm/77485.py at main · Junroot/Algorithm 풀이 시뮬레이션 문제기 때문에 복잡한 알고리즘은 필요없다. 나는 움직여야되는 방향이 같은 숫자끼리 묶어서 한번에 움직이도록 처리했다. 다른 사람 풀이 다른 사람 풀이를 보니 stack을 활용했다. 시계방향으로 숫자들을 stack에 넣으면서 stack의 제일뒤보다 한 칸앞의 숫자로 행렬의 값을 변경하면 시계방향으로 한 칸씩 이동한 모습이 된다. 최소값은 stack 내부의 최소값만 생각하면 되므로 훨씬 깔끔했다.
날짜: 2022년 6월 21일 오전 11:00 코드 Algorithm/72416.py at main · Junroot/Algorithm 풀이 DP를 이용해서 문제를 풀었다. 점화식을 구하는 과정이 이 문제의 가장 어려운 부분이다. get_min_cost(leader_index): leader_index의 하위 직원들의 최소 비용 리더를 워크샵에 참여 시키는 경우: 해당 리더가 팀장으로 속해있는 팀의 팀원들을 기준으로 다시 계산. 리더가 속해있는 팀의 팀원이 워크 샵에 참여시키는 경우: 해당 팀원이 팀장으로 속해있는 팀은 계산할 필요가 없어진다. 이 점화식을 이용해 계산을 하고 메모이제이션을 적용하면 제한 시간내에 해결할 수 있다....
날짜: 2022년 5월 30일 오후 3:02 코드 Algorithm/72415.py at main · Junroot/Algorithm 풀이 여러개의 소문제로 나눠서 해결했다. 카드 쌍을 지우는 순서를 모두 탐색해보는 백트래킹 A위치에서 B위치로 이동하는 최단 경로 구하기 1번은 재귀함수를 이용해서 구현하면되고, 2번은 bfs를 사용했다.
날짜: 2022년 6월 1일 오후 9:38 오답: o 코드 Algorithm/72414.py at main · Junroot/Algorithm 풀이 틀린 풀이 시간이 최대 99시간 59분 59초로 360000초 까지 밖에 없다는 것을 인지했지만, 모든 로그를 360000크기의 배열에 값을 더해주는 것은 360000 * 300000 라는 시간복잡도가 발생할 것으로 보여 이 방법을 사용하지 않았다. 그래서 처음에는 로그들을 시작시간으로 정렬하여 시작 시간마다 누적 재생시간을 계산했는데 이 방법은 누적 재생시간을 매번 새로 계산해야돼서 시간 초과가 발생헀다. 맞는 풀이 결국 다른 사람 풀이를 봤는데, 처음에 언급한 방법을 활용하는 것이었다....
날짜: 2022년 5월 26일 오후 7:39 코드 Algorithm/72413.py at main · Junroot/Algorithm 풀이 플로이드 워셜을 사용해서 각 지점 사이의 요금을 계산해두고, 무지와 어피치가 택시를 따로 타는 모든 경우를 비교해서 최소값을 찾으면 된다.
날짜: 2022년 5월 26일 오후 7:37 코드 Algorithm/72412.py at main · Junroot/Algorithm 풀이 처음에는 db를 생각해서 점수를 기준으로 데이터를 한번 거르고, 그 중에서 값을 필터링했다. 하지만 이 방법은 시간 초과가 발생했다. 두 번째로 생각한 것은 개발언어, 직군, 경력, 소울푸드의 조합이 3_2_2*2 밖에 되지 않기 때문에 이를 이용해서 1차적으로 분류하고 점수별 필터링을 바이너리 서치로 구하는 방법을 사용했다. 이방법을 사용하면 각 속성별로 분류하는 과정을 꽤 줄일 수 있어서 시간초과가 발생하지 않았다.
날짜: 2022년 5월 26일 오후 7:35 코드 Algorithm/72411.py at main · Junroot/Algorithm 풀이 course 에 주어진 길이들의 조합을 dictionary를 이용해 개수를 센다. 길이별로 나눠서 세면 쉽게 구할 수 있다.
날짜: 2022년 5월 25일 오후 6:23 코드 Algorithm/72410.py at main · Junroot/Algorithm 풀이 단순 구현 문제다. 문제 조건에 맞게 구현해주면 된다.