본문 바로가기

분류 전체보기

 (328)
[백준] 17141번 : 연구소 2 17141번: 연구소 2 해당 문제는 완전 탐색 + 조합 + BFS 문제로 해결 하였습니다. 바이러스 후보들을 조합하여 그래프에 적용하고 퍼트립니다. BFS를 사용한 이유는 모든 바이러스 후보들을 queue에 넣고 BFS 탐색을 시작하면 최단 거리로 탐색이 시작되기때문에 퍼지는 시간을 구할 수 있습니다. 조합은 파이썬의 내장라이브러리를 사용하지않고 DFS로 조합을 만들었습니다. from collections import deque from copy import deepcopy import sys from pprint import pprint input = sys.stdin.readline N, M = map(int, input().split()) moves = [(1,0), (-1,0), (0,1), (..
[백준] 10686번 - 최소값 10868번: 최솟값 해당문제는 세그먼트 트리로 문제를 해결 할 수 있습니다. M개의 쿼리가 주어진다면 Mlog(n)의 시간 복잡도로 문제를 해결 할 수 있습니다. 초기화 세그먼트 트리를 초기화를 통하여 세그먼트 트리를 만듭니다. 초기화 하는 과정은 재귀로 각각의 Leaf Node까지 방문한뒤 Leaf Node로부터 다시 올라가면서 Node위치에 자기자신의 최소값을 업데이트 합니다. 쿼리 구간의 최소값을 검색하는 쿼리로 log(n)의 시간복잡도로 구간 최소값을 구합니다. 쿼리를 할때의 조건은 3가지로 나누어 질수 있는데 (start,end) 가 쿼리의 범위이고, (left,right)가 찾는 범위라고 한다면 범위안에 없는경우 : 해당값은 찾을 수 없음 범위안에 있는경우 : 바로 tree[node]값을 리..
[백준] 17070번 : 파이프 옮기기1 17070번: 파이프 옮기기 1 해당 문제는 다이나믹 프로그래밍으로 문제를 해결 할 수 있습니다. 💡 중요한것은 파이프의 방향에 따라서 경우의 수가 달라 질 수 있으므로 3차원 배열이 필요합니다. 예를들어 3,3 에 도착했을때의 방향이 가로방향이었다면 갈 수 있는 경우의수가 세로방향일때와 대각선 방향일때가 각 각 다르기때문에 모든 경우의수를 구해줘야한다. 해당 문제는 탑다운 재귀방식으로 문제를 해결하는것이 구현하기 가 쉽다. 탑 다운 방식 import sys sys.setrecursionlimit(1000000) type = ['H','V','C'] # 가로, 세로, 대각선 movetype = dict() movetype['H'] = (((0,1, 'H'), (1,1, 'C'))) # 가로일때 movet..
[백준] 2357번 : 최솟값과 최댓값 2357번: 최솟값과 최댓값 이문제도 마찬가지로 바이너리 인덱스트 트리로 문제를 해결 할 수 있다. 최소값과 최대값을 갖는 배열을 선언하여 업데이트/쿼리시 동시에 찾을 수 있다. import math import sys input = sys.stdin.readline N, M = map(int, input().split()) treesize = int(pow(2,(math.ceil(math.log2(N)))+1)) tree = [[0 for _ in range(2)] for _ in range(treesize)] # 최대값과 최소값을 담을 배열 INF = int(1e10) arr = [0 for _ in range(N+1)] for i in range(1,N+1): arr[i] = int(input())..
[백준] 4195번 : 친구 네트워크 4195번: 친구 네트워크 해당 문제는 서로소 집합 문제로 해결할 수 있습니다. 왼쪽 친구의 부모로 계속 합치면서 현재 친구상황을 파이썬의 set자료구조에서 union을 통하여 친구네트워크를 업데이트 합니다. import sys input = sys.stdin.readline def find(name): if parent[name] == name: return parent[name] else: parent[name] = find(parent[name]) return parent[name] def union(name1, name2): p1 = find(name1) p2 = find(name2) if p1 == p2: return parentset[p1] = parentset[p1].union(parents..
[백준] 2042번 : 구간합구하기 2042번: 구간 합 구하기 해당 문제는 세그먼트 트리 문제로 구간의 합을 빠르게 쿼리하여 구하는 문제이다. 💡 업데이트 함수를 주목해보면, Index를 기준으로 양쪽으로 나누어서 범위가 벗어나는 경우는 무시하고, 범위 안에있는 애들은 업데이트 해준다. start, end 가 index 의범위 안에 있어야하고, Leaf 노드가 아닌경우에만 나누어서 탐색해가며 업데이트 해준다. import sys input = sys.stdin.readline N, M, K = map(int, input().split()) tree = [0 for _ in range(4*N)] arr = [0 for _ in range(N+1)] for i in range(1, N+1): arr[i] = int(input()) def i..
[백준] 1935번 : 후위 표기식2 1935번: 후위 표기식2 해당 문제는 스택자료구조를 활용 하여 문제를 해결할 수 있다. 주어진 문자열을 for 문으로 순회를 돌면서 숫자가 나오면 스택에 숫자를 저장하고, 연산자가 나온다면 숫자 2개를 pop 하여 연산한뒤 다시 저장한다. for문을 다 돌고난뒤 스택에 남아있는 하나의 숫자가 결과 값이다. N = int(input()) number = [0 for _ in range(N)] expression = input() stack = [] for i in range(N): number[i] = int(input()) for char in expression: if char.isalpha(): stack.append(number[ord(char) - ord('A')]) else: cost = 0 ..
[백준] 18428번 : 감시 피하기 18428번: 감시 피하기 해당문제는 완전탐색 문제로, 그래프에서 장애물을 3개를 놓을 수 있는 조합을 만들고 그 조합을 가지고 선생님들이 감시하여 학생이 감지될경우 “NO”, 학생이 감지되지 않았을경우 “YES”를 출력하면된다. 장애물을 3개 놓을 수 있는 조합 생성 깊이우선탐색을 통하여 장애물을 놓을 수 있는 조합을 생성한다. “순열”이 아닌 “조합”을 찾아야 하는게 문제의 포인트 ( 순열을 찾게되면 경우의 수가 중복 ) 선생이 학생을 감시하는 로직 깊이우선탐색을 통하여 학생을 감시하는 로직을 구현한다. 상,하,좌,우로 이동하면서 장애물이나 경계의 끝을 만나면 종료, 그전에 학생을 만난다면 학생 발견 N = int(input()) table = [[None for _ in range(N)] for _..

티스토리툴바