분류 전체보기657 [Codejam][2021][Round 1A] 1. Append Sort 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007549e5 이전 숫자를 prev, 현재 탐색 중인 숫자를 now라 하자. now > prev가 되도록 숫자를 now뒤에 추가해야 한다. 만약 prev가 now보다 작다면 추가 digit 없이 조건을 만족하므로 다음 숫자를 탐색한다. prev의 자리수가 now 자리수보다 작다면 반드시 prev가 now보다 작으므로 이 경우에 속한다. ex) prev = 10, now = 8 prev와 now의 자리수가 동일하다면 now 뒤에 숫자 0을 추가한다. ex) prev = 10, now = 10 => 100 이 외의 경우는 prev의 자리수가 now 자리수.. 2022. 3. 1. [테트리스] 21. 블록 이동, 바닥에 도달했을 때 로직 개선 https://github.com/fpdjsns/Tetris/issues/18 오늘의 이슈. 아주 묵혀있던 이슈를 처리했다. 바닥 도달 시 블럭을 회전했을 때 정상작동하지 않음. 기존에는 (x, y)로 이동할 때, 이동가능한지 체크(1), 가능하다면 해당 좌표로 블럭 좌표 갱신(2), 화면에 출력(3). 을 따로 하고 있었다. 블럭이 바닥에 완전히 도달했을 때 호출되는 함수는 timer에서 콜백함수로 따로 주입받았는데 로직은 아래와 같다. // gamescreen 배열에 nowBlock의 좌표를 세팅 setBlockInGameScreen(nowBlock); // 삭제가능한 행이 있다면 삭제 후 gamescreen 갱신 & 캔버스 그리기 nowBlock.checkRowsAndErase(); // 새로운 블.. 2022. 2. 28. [220228] 포켓몬스터 9세대 스칼렛, 바이올렛 발매예정?! 2022년 겨울 발매예정..!! 아르세우스는 안샀어도 새로운 지방은 못참지 두근두근 2022. 2. 28. [Leetcode] 662. Maximum Width of Binary Tree 문제 : https://leetcode.com/problems/maximum-width-of-binary-tree/ 이진 트리의 루트가 주어지면 트리의 최대 너비를 구하라. 최대 너비는 모든 레벨 중 최대 너비이며, 한 레벨의 너비는 가장 왼쪽 노드와 가장 오른쪽 노드의 길이이다. 만약 노드들 사이에 null 노드가 존재한다면 null 노드도 길이에 포함시킨다. 이진트리의 인덱스를 구해보면 위와 같다. 특정 노드의 왼쪽 자식 노드의 인덱스는 2 x 인덱스. 오른쪽 자식 노드의 인덱스는 2 x 인덱스 + 1 이다. 이를 이용하여 루트 노드부터 자식 노드들을 탐색해가며 각 레벨에서 가장 왼쪽에 존재하는 노드와 가장 오른쪽에 존재하는 노드의 인덱스 차이가 너비가 된다. 구한 너비들 중 최대값이 정답이 된다. .. 2022. 2. 27. [Leetcode] 847. Shortest Path Visiting All Nodes 문제 : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/ 우선 플로이드 워셜 알고리즘으로 모든 정점간 최단거리(dist)를 구한다. 구한 dist 배열로 플로이드 워셜 알고리즘이랑 비슷하게 정답을 구한다. 기본 알고리즘은 다음과 같다. 여기서 상태란 node들이 포함된 상태를 의미한다. (참고) 즉, 플로이드 워셜 알고리즘 처럼 3중 for문을 돌린다. 중간 지점을 중간에 거치는 상태로 두고 시작 노드에서 종료 노드로 갈 때 거치는 최소 간선의 수를 구한다. 조건문에 시작노드가 포함되고 종료노드는 포함되지 않은 상태가 중간상태가 되야 하는 이유는 중간상태에 시작노드가 있어야만 시작 상태가 될 수 있고, 중간상태에 종료.. 2022. 2. 26. [Leetcode] 1781. Sum of Beauty of All Substrings 문제 : https://leetcode.com/problems/sum-of-beauty-of-all-substrings/ 문자열의 beauty는 가장 자주 사용되는 문자와 가장 자주 사용되지 않는 문자 사이의 빈도 차이이다. 문자열 s가 주어졌을 때 모든 하위 문자열의 beauty 합을 구해라. s.length가 500 이므로 완탐을 돌린다. 2차원 반복문을 돌려서 s[start~end]에서 문자의 등장횟수를 갱신하며 탐색당시의 beauty 값을 구해 정답에 더해나간다. for start = [0, |s|) 문자의 등장횟수를 저장하는 map 갱신 for end = [start, |s|) s[end] 횟수 + 1 등장횟수 map을 탐색하며 최대등장횟수, 최소등장횟수를 구해서 차이를 정답에 더한다. 시간복잡.. 2022. 2. 24. 이전 1 ··· 8 9 10 11 12 13 14 ··· 110 다음
