본문 바로가기

Algorithm202

BOJ 1303 - 전쟁 - 전투 문제 백준 온라인 저지 - 1303번 풀이 과정 두 세력간의 규모를 측정하는 BFS 문제입니다. W 와 B 로 나누어진 컴포넌트의 크기를 구하면 되는데 이때 BFS 를 활용하고 각 컴포넌트의 크기를 구할때마다 제곱한 값을 세력 규모에 더해주면 됩니다. 코드 import sys from collections import deque N, M = list(map(int, sys.stdin.readline().split())) board = [list(sys.stdin.readline().strip()) for _ in range(M)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def in_range(x, y): return 0 2021. 3. 18.
BOJ 1260 - DFS와 BFS 문제 백준 온라인 저지 - 1260번 풀이 과정 DFS 와 BFS 연산을 구현하는 간단한 문제입니다. 먼저 입력으로 받은 간선 정보로 그래프를 생성하고 이후 DFS 와 BFS 함수를 통해 탐색을 수행합니다. 코드 import sys from collections import deque sys.setrecursionlimit(10 ** 6) def bfs(graph, start): q = deque() visit = [0] * (N + 1) order = [] q.append(start) visit[start] = 1 while q: here = q.popleft() order.append(here) for there in sorted(graph[here]): if not visit[there]: visi.. 2021. 3. 18.
BOJ 6550 - 부분 문자열 문제 백준 온라인 저지 - 6550번 풀이 과정 두 개의 문자열이 주어질 때 한 문자열이 다른 문자열에 포함되는지 판단하는 문제입니다. 문자가 연속으로 나타나야한다는 조건이 없기 때문에 검사할 조건이 되는 문자열의 인덱스를 하나씩 증가시키면서 다른 문자열에 해당 인덱스에 해당하는 문자가 존재하는지 판단하면 됩니다. 코드 import sys def solution(s, t): si = 0 for ti in range(len(t)): if t[ti] == s[si]: si += 1 if si == len(s): return 'Yes' return 'No' if __name__ == '__main__': while True: line = sys.stdin.readli.. 2021. 3. 18.
BOJ 10819 - 차이를 최대로 문제 백준 온라인 저지 - 10819번 풀이 과정 수열 을 생성해서 모든 가능한 경우의 수들을 만들어보는 완전 탐색 문제입니다. 이후에 문제에서 제시된 수식을 이용해서 값을 계산하고 이 중 최대값을 답으로 반환하면 됩니다. 코드 import sys from itertools import permutations def solution(): max_value = 0 for perm in permutations(numbers): acc = 0 for i in range(N - 1): acc += abs(perm[i] - perm[i + 1]) max_value = max(max_value, acc) return max_value if __name__ == '__main__': N = int(in.. 2021. 3. 18.
BOJ 15240 - Paint bucket 문제 백준 온라인 저지 - 15240번 풀이 과정 pixels 라는 이차원 배열을 생성한 다음, 시작 지점에서 BFS 를 통해 방문을 수행합니다. 이때 방문처리 하기 전에 이전 위치의 픽셀 값을 저장해서 비교하는 것에 유의합니다. 코드 import sys from collections import deque dr = [0, 0, 1, -1] dc = [1, -1, 0, 0] def bfs(r, c, color, pixels): q = deque() visit = [[0] * C for _ in range(R)] q.append([r, c]) visit[r][c] = color while q: r, c = q.popleft() before = pixels[r][c] pixels[r][c] = color f.. 2021. 3. 18.
BOJ 1449 - 수리공 항승 문제 백준 온라인 저지 - 1449번 풀이 과정 테이프를 겹치는 것이 가능하므로 탐욕 알고리즘 을 사용해서 최소 테이프 개수를 구할 수 있습니다. 항상 최대 길이의 테이프를 사용하기 때문에 물이 새는 구간을 오름차순 정렬하면 맨 앞부터 테이프를 붙이면 되는 것입니다. 이때 문제 조건에 입력 값이 정렬되어있다는 언급이 없으므로 따로 정렬시켜주도록 합니다. 코드 import sys N, L = list(map(int, sys.stdin.readline().split())) pipe = list(map(int, sys.stdin.readline().split())) def solution(): fixed = [0] * N ans = 0 # 물 새는 곳 정렬 pipe.sort() for spot in range.. 2021. 3. 18.

티스토리툴바