백준(19)
-
[Python] 백준 알고리즘 18405 - 경쟁적 전염
[Python] 백준 알고리즘 18405 - 경쟁적 전염 18405번: 경쟁적 전염 (acmicpc.net) 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 과정 문제에서 입력하는 값 n, k / 실험관의 크기와 바이러스의 종류 시험관 s, ( x , y ) / 실험 시간과 실험 후 추출하고자 하는 좌표 사용 개념 우선순위 큐, 덱 너비 우선 탐색 그래프 풀이 접근방법 문제에 해당하는 입력값을 입력받는다 실험관에서 바이러스의 종류(vn), 해당 바이러스의 위치(x, y), 실..
2022.11.09 -
[Python] 백준 알고리즘 15650번 - N과 M(2)
[Python] 백준 알고리즘 15650번 - N과 M(2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근 방법 n과 m(1)과 동일한 접근이다. 하지만 중복은 없어야 한다는 게 문제의 조건이다. https://skyriv312079.tistory.com/63 [Python] 백준 알고리즘 15649번 - N과 M(1) [Python] 백준 알고리즘 15649번 - N과 M(1) https://www.acmicpc.net/problem..
2022.10.06 -
[Python] 백준 알고리즘 15649번 - N과 M(1)
[Python] 백준 알고리즘 15649번 - N과 M(1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근 방법 숫자 입력 → 문제의 요구사항 입력 n. m 입력 / 정답 기록용의 s 리스트 생성 메서드 구현 주어진 n까지 중복 없이 m개를 골라 출력 리스트 s의 길이가 m과 동일해지면 해당 반복문을 멈추고 출력 후 종료 join 및 map 활용 동일하지 않은 경우 for 반복문 실행( 1 ~ n + 1까지), i는 반복문에 할당된 변..
2022.10.06 -
[Python] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분 수열
[Python] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분 수열 문제 출처 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 접근방법 가장 긴 증가하는 부분수열 이번에는 메모이제이션 기법을 이용해서 기존 수열과의 길이 비교에 사용된다. 메모이제이션을 사용하는 동적계획법의 이번 문제의 시간복잡도는 for문의 반복 첫번째 반복문에서 n번 그 다음 반복문은 i..
2022.07.31 -
[Python] 백준 알고리즘 1010번 - 다리 놓기
[Python] 백준 알고리즘 1010번 - 다리 놓기 문제 출처: 1010번: 다리 놓기 (acmicpc.net) 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 접근 방법 접근은 조합으로 접근을 하였다. 1 ) 파이썬 자체 내장 팩토리얼 메서드 이용 2 ) 팩토리얼을 동적계획법으로 구하고 그 나온 수를 이용해서 조합의 구조로 답출력 동적계획법을 넣기 위해 2번의 방식을 선택했다. 문제에서 주어진 숫자의 범위는 0
2022.07.30 -
[Python] 백준 알고리즘 11726 - 2 x n 타일링
백준 알고리즘 11726 - 2 x n 타일링 문제 출처 : 11726번: 2 ×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근 다이나믹 프로그래밍, 즉 동적 계획법을 바탕으로 접근을 해야 하는 문제이다. n이 늘어나는 경우에 맞춰 점화식을 세우고 그에 맞춰서 코드를 진행하였다. 점화식에 대해 접근을 해보자. 해당 점화식의 경우 피보나치 수열과 유사한 점화식이 등장한다. 점화식의 경우 본인의 인덱스를 i라고 하자. 그럼 i - 2 와 i - 1의 경우의 수를 합산하면 해당 인덱스의 경우의 수..
2022.07.30