본문 바로가기

알고리즘

 (54)
15591. Mootube 처음에 MST인가? 라는 생각을 가졌는데 결국 이문제는 탐색을 해야하는 문제이다. 주어진 노드 관점에서 bfs를 진행해야 유사도를 측정해서 개수를 셀 수 있다. 유사도라는 것을 모든 연결들의 유사도중의 최솟값으로 정했으므로 노드와 노드사이의 거리가 k보다 작다면 방문자체를 할 필요가 없다. import sys from collections import deque input = sys.stdin.readline INF = int(1e9) def bfs(start, k): global graph visited = [False] * (N+1) q = deque() q.append(start) count = 0 while q: now = q.popleft() visited[now] = True for n_n, ..
54. Spiral Matrix 유명한 돌아가는 문제이다. (소용돌이 문제 같은 느낌) 이문제는 단순하게 노동하는 방법도 존재하지만 엄청 이쁜 풀이도 존재한다. 우선 이쁜 풀이를 보자. const spiralOrder = function(matrix) { const res = [] while(matrix.length){ const first = matrix.shift() res.push(...first) for(const m of matrix){ let val = m.pop() if(val) res.push(val) m.reverse() } matrix.reverse() } return res };첫라인은 그대로 출력하고 배열에서 없앤다. 두번째 라인부터 마지막 라인까지 마지막꺼 출력하고 뒤집어 놓는다. 그다음에 전체 매트릭스를 뒤집는..
[2021 카카오 채용 연계형 인턴십] 거리두기 확인하기 주요 조건들을 체크하자. - 맨해튼 거리가 2이하이면 탈락 - 테이블도 이동에 포함 - 파티션은 이동에 포함하지 않음 bfs로 접근. from collections import deque def bfs(place): start = [] d = (1,0),(-1,0),(0,1),(0,-1) for i in range(5): for j in range(5): if place[i][j] == 'P': start.append((i,j)) q = deque() visited = [[False] * 5 for _ in range(5)] for s in start: q.append((s[0], s[1], 0)) visited[s[0]][s[1]] = True while q: x, y, dist = q.popleft(..
1914. 하노이 탑 옛날에 하노이 탑을 직접 해봐서 규칙이 있다는 것을 알았다. 하지만 코드로 구현하는데 어려움을 겪었다. 재귀 호출을 통해 구현할 수 있는데 재귀함수 하나를 정의해야한다. f(n,a,b,c) → n개의 원판이 a기둥에 있을 때, c기둥으로 모두 이동 시키는 함수 n-1개의 원판을 2번기둥으로 옮김 1번 기둥에 남아있는 한개의 원판을 3번으로 2번기둥에 있는 n-1개의 원판을 3번 기둥으로 def f(n, a, b, c): if(n == 1): print(a, c, sep = " ") else: f(n-1, a, c, b) f(1, a, b, c) f(n-1, b, a, c) n = int(input()) print(2**n-1) if(n
10819. 차이를 최대로 풀이 방법은 크게 2가지로 생각해 볼 수 있을 것 같다. 첫번째는 파이썬의 permutations를 이용. 두번째는 dfs 가장 직관 적인 풀이는 다음과 같다. import sys from itertools import permutations input = sys.stdin.readline n = int(input()) a = list(map(int, input().split())) cases = list(permutations(a)) answer = 0 for case in cases: mid_sum = 0 for i in range(n - 1): mid_sum += abs(case[i] - case[i + 1]) answer = max(mid_sum, answer) print(answer) 다음으로 ..
22. Generate Parentheses 모든 쌍을 다 찾아야 하므로, dfs를 진행했다. 여는괄호, 닫는 괄호가 둘다 0이 되었을 때, 배열에 푸쉬를 해주었고, 오른쪽 괄호의 개수가 더 작다면 무조건 리턴조건, 왼쪽 괄호의 개수가 0보다 작다면 무조건 리턴 조건에 포함된다. 따라서 풀이는 아래와 같다. const generateParenthesis = function(n) { let res = []; const dfs = (str, left, right) => { if(left === 0 && right === 0) { res.push(str); return; } if(right < left || left < 0) return dfs(str+"(", left - 1, right) dfs(str+")", left, right - 1) } dfs..
33. Search in Rotated Sorted Array 문제에서 O(logn)으로 풀어야 한다고 명시가 되어있다. 이 문제에서 중요한 부분은 두 배열로 나눴을 때 둘중 하나는 무조건 정렬된 상태라는 것이다. 그렇게 생각하면 왼쪽이 정렬되어있다면, 오른쪽은 정렬되지 않았을 것이고, 반대의 경우도 마찬가지이다. 왼쪽이 정렬된 상태일 경우에, 타겟이 그 정렬된 숫자들 사이에 있는 값이라면, right을 mid - 1 로 바꿔주고, 만약 타겟이 그 숫자들 사이에 있지 않다면, 그 left를 mid+1로 바꿔주면서 탐색한다. const search = function(nums, target) { let left = 0; let right = nums.length - 1; while (left
289. Game of Life 각 칸에 이웃하는 주민의 수를 구해야하고, 그 주민수를 저장해놓고 비교할 때 사용해야한다. 따라서 객체에 저장을 해놓고 사용했다. 이웃하는 주민이 2보다 작거나, 3보다 크다면, 그 칸을 0으로 바꿔준다. 만약 3이라면 1로 바꿔준다. const gameOfLife = function(board) { const hash = {}; const directions = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]]; for (let r = 0; r < board.length; r++) { for (let c = 0; c < board[r].length; c++) { let numLiveNeighbors = 0; for (let [x, y] of..

티스토리툴바