Algorithm202 BOJ 16441 - 아기돼지와 늑대 문제 백준 온라인 저지 - 16441번 풀이 과정 BFS 를 이용해서 아기돼지가 안전하게 위치할 수 있는 장소들을 찾는 문제입니다. 모든 늑대들의 초기 위치를 찾은 다음, 큐에 넣고 초기화시킵니다. 이후 늑대들을 기준으로 BFS 를 수행하며 늑대들이 방문 가능한 위치를 표시합니다. 만약 늑대가 빙판을 만난다면 이동중인 방향을 기준으로 벽이나 잔디를 만날때까지 이동합니다. 코드 import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def preprocess(): wolves = [] for n in range(N): for m in range(M): if board[n][m] == 'W': wolves.a.. 2021. 4. 13. BOJ 1922 - 네트워크 연결 문제 백준 온라인 저지 - 1922번 풀이 과정 모든 컴퓨터를 연결하는 네트워크를 구성하는 최소 비용을 구하는 문제입니다. 크루스칼 알고리즘 을 이용해서 MST 를 구현했으며 union 연산에서는 랭크 최적화와 경로 압축을 사용했습니다. 코드 import sys def union(v1, v2): r1, r2 = find(v1), find(v2) if r1 == r2: return if rank[r1] > rank[r2]: parent[r2] = r1 else: parent[r1] = r2 if rank[r1] == rank[r2]: rank[r2] += 1 def find(v): if parent[v] != v: parent[v] = find(parent[v]) return parent[v] def kr.. 2021. 4. 13. BOJ 20006 - 랭킹전 대기열 문제 백준 온라인 저지 - 20006번 풀이 과정 랭킹 대기열 로직을 구현하는 문제입니다. 먼저 방의 정보를 관리하기 위해 해시 테이블 을 사용했습니다. 이때 해당 방에 방장의 식별자와 참여중인 다른 사람들을 배열 형태로 관리합니다. 여기서 assign_player 함수에서는 플레이어를 기존에 존재하는 방에 할당 가능한지 판단하고 만약 새로운 방이 필요할 경우 방장으로 할당한 뒤 새로운 방을 생성하도록 합니다. 코드 import sys def assign_player(player_id, player_level, rooms): for _, meta in rooms.items(): master_level = players[meta['master']] if master_level - 10 2021. 4. 13. BOJ 2869 - 달팽이는 올라가고 싶다 문제 백준 온라인 저지 - 2869번 풀이 과정 처음에는 해당 문제가 왜 이분 탐색 문제집에 포함되어 있는지 의문이었습니다. 수학적으로 해결할 수도 있을 것 같지만 이분 탐색 으로 해결할 수 있는 방법을 찾고 싶이서 다른 방식으로 접근했습니다. 달팽이는 매일 A 만큼 올라갑니다. 달팽이가 끝에 도달하기 위해서는 마지막 이동 전 위치가 V - A 보다 크거나 같으면 됩니다. 따라서 날짜 * (A - B) >= V - A 가 되는 최소 날짜를 이분 탐색 으로 찾으면 됩니다. 코드 import sys def solution(): move_offset = A - B lo, hi = 0, 1000000000 day = 2e9 while lo = V - A: day = min(day, mid) hi = mid - .. 2021. 4. 13. BOJ 16926 - 배열 돌리기 1 문제 백준 온라인 저지 - 16926번 풀이 과정 배열을 회전하는 로직을 구현하는 문제입니다. python 으로 제출하니 시간초과가 발생하여 pypy3 로 제출했습니다. 코드 import sys def rotate(): x, y = 0, 0 n, m = N, M time = min(N, M) // 2 while time: cache = board[x][y] # 윗쪽 for i in range(m - 1): board[x][y + i] = board[x][y + i + 1] # 오른쪽 for i in range(n - 1): board[x + i][y + m - 1] = board[x + i + 1][y + m - 1] # 아래쪽 for i in range(m - 1): board[x + n - 1][y .. 2021. 4. 13. LeetCode 36 - Valid Sudoku (Medium) 문제 LeetCode - 36번 풀이 과정 스도쿠 를 구현하는 문제입니다. 대신 모든 로직을 구현하는 것은 아니고 채워진 숫자들에 대해서 스도쿠 조건을 만족하는지 판단하는 문제입니다. 먼저 3x3 크기의 서브 박스들에서 19 사이의 숫자들 중 중복이 존재하는지 검사합니다. 이후 각 행과 열을 순회하며 마찬가지로 19 사이의 숫자 중복성을 검사합니다. 코드 /** * @param {character[][]} board * @return {boolean} */ var isValidSudoku = function (board) { const isSubboxRepetition = checkSubboxes(board); if (!isSubboxRepetition) { return false; } for (let .. 2021. 4. 13. 이전 1 ··· 6 7 8 9 10 11 12 ··· 34 다음
