본문 바로가기

알고리즘/백준

 (263)
[백준] 1915번 : 가장 큰 정사각형 해당 문제는 다이나믹 프로그래밍 문제로 해결 합니다. 어떠한 위치 i,j에서 크기 S의 정사각형을 찾는다고 한다면 (i-1)(j-1), (i-1)(j), (i)(j-1) 가 이미 크기가 S인 정사각형이고 (i ,j)가 1인경우에 정사각형입니다. 따라서 작은 크기의 정사각형부터 구해나가면서 가능한 정사각형의 크기를 구합니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) map = [input()[:-1] for _ in range(N)] square = 0 chk = [[0] * M for _ in range(N)] for y in range(N): for x in range(M): if (y == 0 or x == 0) a..
[백준] 1062번 : 가르침 1062번: 가르침 가능한 알파벳을 모두 만들어본뒤, 해당 알파벳을 비트 단위로 본다. 즉 비스마스킹을 한다. 예를들어 알파벳이 4개 존재햇을때 abcd라는 단어인경우 0x1111 로 표현 할 수 있고, abc인경우 0x0111로 표현 할 수 있다. 우리는 알파벳 a~z까지 있는 경우이니 0x00000..00 이 필요하다. 그래서 가능한 모든 알파벳을 구한뒤, 해당 알파벳이 있는지 없는지 여부는 비트연산을 통하여 문제를 해결 할 수 있다. import sys from itertools import combinations input = sys.stdin.readline N, K = map(int, input().split()) words = [0 for _ in range(N)] for i in range..
[백준] 2096번 : 내려가기 2096번: 내려가기 해당 문제는 다이나믹 프로그래밍 문제로 메모리 제한이 4MB이다 따라서 2차원 배열이 아닌 1차원 배열로 문제를 해결해야한다. current 변수에 최대값과 최소값이 저장될 값이고 temp로 받아서 한 단계씩 내려갈때마다 정수삼각형을 구하는 문제처럼 최소값과 최대값을 갱신하면서 내려가면 된다. N = int(input()) current = [[0,0] for _ in range(3)] # maxValue, minValue for _ in range(N): a,b,c = map(int, input().split()) # 최대값 구하기 temp = [0 for _ in range(3)] temp[0] = a + max(current[0][0], current[1][0]) # 첫번째 수..
[백준] 2493번 : 탑 2493번: 탑 해당문제는 스택자료구조를 활용하여 문제를 해결 할 수 있습니다. 배열을 순회하면서 아래의 내용을 반복 수행하면 됩니다. 자기자신보다 큰 탑을 출력한다. 4번으로 이동 만약자기자신보다 작은 탑이 발견되면 큰 탑이 나올때까지 pop한다 큰탑이 나오면 출력하고 없다면 0을 출력한다. 자기자신을 push 한다. N = int(input()) table = list(map(int, input().split())) result = [] stack = [] stack.append([table[0], 1]) result.append(0) # 첫번째 인덱스는 레이저를 수신할 탑이 없다. for i in range(1, len(table)): idx = stack[-1][1] while stack and ..
[백준] 1005번 - ACM Craft 1005번: ACM Craft 해당 문제는 위상정렬 문제로 해결 할 수 있습니다. 진입차수 가중치를 넣고, 진입차수가 0인 루트노드부터 방문해가면서 거리를 계산하면 됩니다. import sys input = sys.stdin.readline def dfs(node): global ans for child in graph[node]: cost[child] -= 1 # 진입차수를 줄인다. ans[child] = max(ans[node] + distance[child], ans[child]) if cost[child] == 0: # 진입차수가 0이면 이제 방문한다. dfs(child) T = int(input()) for _ in range(T): N, K = map(int, input().split()) d..
[백준] 1018번 : 채스판 다시 칠하기 1018번: 체스판 다시 칠하기 해당 문제는 완전탐색문제로 8x8 채스판을 뒤집을 수 있는 최소 개수를 구하는 문제입니다. 깊이 우선탐색으로 문제를 해결하였으며 전체 채스판에서 모든 8x8 채스판을 확인합니다. 0x0이 ‘W’일때와 0x0이 ‘H’ 일때 2가지 경우를 모두 탐색합니다. # move = ((0,1), (1,0), (0, -1), (-1, 0)) N, M = map(int, input().split()) graph = [] CHAR = ["W", "B"] WHITE = 0 BLACK = 1 def dfs(i, j, cur, visited): global cnt, h, w, h2, w2 if graph[i][j] != cur: cnt += 1 for dy, dx in move: ny, nx =..
[백준] 1027번 : 고층건물 1027번: 고층 건물 해당 문제는 완전탐색 문제로 해결하였습니다. 문제의 요점은 각각의 좌표의 기울기를 구하여 기울기 크기를 비교하여 문제를 해결하였습니다. 파이썬에서 나누기 연산 주의 “//” 는 정수 결과 값만 나온다. “/”연산을 활용하여 문제를 해결해야합니다. 현재의 점에서 오른쪽과 왼쪽을 모두 탐색 하였습니다. import sys si = sys.stdin.readline N = int(si()) arr = list(map(int, si().split())) ans = 0 for i in range(N): # 가능한 모든 빌딩을 가본다. # 오른쪽으로가본다. rbuilding = [] start = i+1 while N > start: if rbuilding: incline = rbuildin..
[백준] 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), (..

티스토리툴바