__Python/__Algorithm
-
[Python] 백준 - 1927 최소 힙__Python/__Algorithm 2022. 1. 7. 17:00
# 실버 1 [문제] 링크 : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 풀이 힙(heapq) 최소힙 우선순위 큐 x = 0: 비어있으면 0, 아닐 경우 최솟값 출력 x != 0: 최소힙에 삽입 구현 코드 import sys import heapq N = int(sys.stdin.readline()) inputs = [int(sys.stdin.readline()) for _ in range(N)] heap = []..
-
[Python] 백준 - 2667 단지번호 붙이기__Python/__Algorithm 2022. 1. 7. 16:51
# 실버 1 [문제] 링크 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 그래프탐색 BFS 구현 코드 import sys from collections import deque def bfs(i,j): cnt = 0 queue = deque([[i,j]]) chk[i][j] = 1 while queue: x, y = queue.popleft() cnt+=1 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] for ..
-
[Python] 백준 - 9020 골드바흐의 추측__Python/__Algorithm 2022. 1. 7. 16:42
# 실버 1 [문제] 링크 : https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 풀이 소수 판별 두 소수의 합계이며 값의 차이가 최소 > N값의 절반부터 반복문을 실행 > i, N-i가 모두 소수일 경우 출력 정답 풀이 후 다른 풀이 방식이나 코드 축소를 참고하고자 숏코딩을 보는 편인데, 이 문제는 다른 사람의 풀이(숏코딩) 이해 어려움. 구현 코드 import math import sys def sosu(n): for ..
-
[Python] 백준 - 2178 미로 탐색__Python/__Algorithm 2022. 1. 7. 16:24
# 실버 1 [문제] 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 그래프탐색 BFS 최단 경로를 찾아야하기 때문에, DFS는 불가 갈림길이 있을 경우, 최단 경로를 어떻게 판단할지 고민 처음에는 길이 막혔을 경우, 되돌아오도록 짬 => 실패(출구까지 막힌 길이 없을 경우) 기본 BFS, 미로 진입 시 cnt =1부터 다음 진행할 때마다 cnt + 1으로 갱신 => 1번과 같은 사유로 실패(cnt값이 엄청나게 커짐) 최종) 2번 변형, 다음 진행방향의 c..
-
[Python] 백준 - 1904 01타일__Python/__Algorithm 2021. 12. 21. 18:33
더보기 # 백준 Silver3 # 1904 01타일 [문제] 링크 : https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net [문제 풀이] 동적계획법 - 규칙 : 점화식이 피보나치 수열 [구현 코드] import sys N = int(sys.stdin.readline()) tile = [0]*(N+1) for i in range(N+1): if i
-
[Python] 백준 - 9184 신나는 함수 실행__Python/__Algorithm 2021. 12. 21. 12:43
더보기 # 백준 Silver2 # 9184 신나는 함수 실행 [문제] 링크 : https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net [문제 풀이] 동적계획법 메모이제이션 - 재귀를 사용할 경우, 동일한 계산의 반복으로 시간 효율이 떨어진다. - 계산한 결과를 메모리에 저장해두어 중복 계산을 방지할 수 있다. [구현 코드] import sys MAX = 21 res = [[[0]*MAX for _ in range(MAX)] for _ in range(MA..
-
[Python] 백준 - 1003 피보나치 함수__Python/__Algorithm 2021. 12. 21. 12:37
더보기 # 백준 Silver3 # 1003 피보나치 함수 [문제] 링크 : https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [문제 풀이] 동적계획법 메모이제이션 - 재귀를 사용할 경우, 동일한 계산의 반복으로 시간 효율이 떨어진다. - 계산한 결과를 메모리에 저장해두어 중복 계산을 방지할 수 있다. [구현 코드] import sys N = int(sys.stdin.readline()) cases = list(int(sys.stdin.readline()) for _ in range(N)) fibo = [[1,0],[0,1]]+[[0,0] fo..
-
[Python] 백준 - 11047 동전 0__Python/__Algorithm 2021. 12. 20. 20:04
더보기 # 백준 Silver2 # 11047 동전 0 [문제] 링크 : https://www.acmicpc.net/problem/11047 [문제 풀이] 그리디 [구현 코드] import sys N,K = map(int,sys.stdin.readline().split()) coins = [int(sys.stdin.readline()) for _ in range(N)] ans = 0 coins.sort(reverse=True) for i in range(len(coins)): if coins[i]
