본문 바로가기
728x90

Programming/Python46

[자료구조] 큐, 스택, 힙 스택 (Stack)후입선출(LIFO, Last In First Out)사용리스트로 구현# define stackstack = []# addstack.append(item)# pop (가장 마지막에 in된 item return하며 stack에서 제거)stack.pop()큐 (Queue)선입선출(FIFO, First In First Out)사용collections 모듈의 deque 사용하여 구현deque 양방향 연결 리스트로 구성# import libraryfrom collections import deque# define queuequeue = deque()# addqueue.append(item)# add leftqueue.appendleft(item)# insertqueue.insert(idx, ite.. 2023. 11. 16.
[Solved] BOJ: 11725 | 트리의 부모 찾기 문제주어진 연결 상태로 트리를 만들어각 노드의 부모노드 구하기입력첫번째 줄: 트리 길이 t두번째 줄~2+t-1: 노드 연결 상태출력각 노드의 부모 노드 출력접근일단 연결 상태를 가지고 트리를 만든 후dfs로 부모 노드를 구하면 되겠...다?풀이입력 및 트리 만들기n = int(input())tree = {}# make treefor _ in range(n-1): n1, n2 = map(int, input().split()) if n1 in tree: tree[n1].append(n2) else: tree[n1] = [n2] if n2 in tree: tree[n2].append(n1) else: tree[n2] = [n1]dic.. 2023. 2. 2.
[Solved] BOJ: 4963 | 섬의 개수 문제근접해있는 섬들을 이어 하나의 섬으로 침.전체 맵에서 섬 개수 카운트입력첫째줄: 지도의 너비 w, 높이 h, (w, h 둘째줄~2+h번째줄: 지도, 1 == 땅, 0 == 바다출력섬의 개수접근근접해있는거 이어서 하나로 치고 전체 몇개인지 카운트하는 것은bfs 그래프 탐색으로 풀면된다.다만 4방향이 아닌 대각선까지 총 8방향에 대해서 구하면 됨풀이입력while True: w, h = map(int, input().split()) if w == 0 and h == 0: break m = [] for _ in range(H): m.append(list(map(int, input().split())))입력 받아오기0 0 .. 2023. 2. 2.
[Solved] BOJ: 2630 | 색종이 만들기 문제가로 N/2 세로 N/2씩 잘라서 1이나 0으로만 이루어진 정사각형 만들기입력과 출력입력첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.출력첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.문제 해결 요약색종이 전체를 순회하면서 왼쪽상단(맨 처음 인덱스)와 값이 같은지 확인다르다면 가로 세로 길이를 반으로 잘라 4등분 하고, 4개의 색종이에 대해 다시 1 진행 -> 재귀코드 설명im.. 2022. 12. 6.
[Solved] BOJ: 11053 | 가장 긴 증가하는 부분 수열 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하기입력과 출력입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.문제 해결 요약수열의 길이를 카운트하는 dp 테이블 생성(카운트값)전체 순열을 순회하면서 i번째 수에 대해i-1부터 첫번째 인덱스까지 역으로 순회하며i번째 수보다 크다면 해당 수의 카운트값+1로 i번째 카운트값을 갱신코드 설명import 및 입력받기-import sysinput = sys.stdin.readlinen = int(input())seq = [0]seq += list(map(int, input().. 2022. 11. 28.
[Algorithm] Dynamic Programming Dynamic Programming동적 계획법(dynamic programming)이란 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 푸는 방법을 말한다.DP 조건큰 문제를 작은 문제들로 나눌 수 있을 때작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 적용할 수 있을 때작은 문제들이 반복될 때FibonacciF(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2).Recursive# O(2^n)def recur_fibo(n): if n == 0 or n == 1: return n else: return recur_fibo(n-1) + recur_fibo(n-2)# 387 ms ± 7.1 ms per loop (mean ± std. dev.. 2022. 11. 24.
728x90

티스토리툴바