본문 바로가기
728x90

Programming56

[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.
[Solved] BOJ: 2467 | 용액 문제합이 0에 가장 가까운 두 용액 조합 구하기입력과 출력입력첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.출력첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.문제 .. 2022. 11. 20.
[Solved] BOJ: 1389 | 케빈 베이컨의 6단계 법칙 문제케빈의 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임한 사람이 나머지 모든 사람들에 대해 베이컨 게임을 진행해서 나오는 단계들의 총합을 베이컨 수라고 한다.모든 사람들의 베이컨 수를 구해 그 중 최소의 베이컨 수를 갖는 사람을 구하자.입력과 출력입력첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어.. 2022. 11. 15.
728x90

티스토리툴바