[파이썬] 백준 3184 : 양

[파이썬] 백준 3184 : 양 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 실버 2 그래프, DFS, BFS 접근 울타리의 경계를 만날 때까지 영역 내의 다른 좌표들을 탐색해야 하므로 bfs가 적합하다. 좌표를 움직이되, 설정한 경계값을 넘지 않았는지, 방문하지 않았는지, 해당 좌표에 울타리가 존재하지 않는지 확인하고 만약 늑대가 있다면 늑대의 수를, 양이 있다면 양의 수를 더해준다. bfs의 탐색이 끝나는 경우는 울타리 내의..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 30.
• textsms

[파이썬] 백준 2210 : 숫자판 점프

[파이썬] 백준 2210 : 숫자판 점프 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 실버 2 그래프, DFS, 브루트포스 접근 방문처리를 할 필요가 없으므로 브루트포스와 같은 접근을 해야 한다. 모든 좌표에 대한 DFS를 진행하고, 글자 수를 하나씩 채우다가 길이가 6이 되는 경우 그 문자열이 기존에 추가했던 적이 있는지 없는지를 확인하고 리스트에 추가한다. 마지막으로 해당 리스트의 길이를 출력한..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 28.
• textsms

[파이썬] 백준 1260 : DFS와 BFS

[파이썬] 백준 1260 : DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 실버 2 그래프, DFS, BFS DFS, BFS의 구현 방법을 알고 있는 것을 전제로 제시된 문제이다. 다만 정점을 방문은 반드시 오름차순 순서로 이루어져야 하기 때문에, 인접한 정점들을 오름차순으로 정렬한 후에 접근할 수 있도록 구현해야 한다. bfs구현을 할 때는 시간 복잡도가 O(1)인 deque을 이용하는 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 27.
• textsms

[파이썬] 백준 11727 : 2xn 타일링 2

[파이썬] 백준 11727 : 2xn 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 실버 3 DP 도저히 규칙을 못 찾아서 노가다로 경우의 수를 구해봤다. 1 : 1 2 : 3 3 : 5 4 : 11 5 : 21 ... 3번째 의 5는 1번째의 1에 2를 곱한 값과 2번째의 3을 더한 값과 같다는 사실을 발견했다. 이를 점화식으로 나타내면 dp[i] = dp[i-2]*2 + dp[i-1]가 된다. 코드 import sys n = int(sys.stdin.read..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 26.
• textsms

[파이썬] 백준 1012 : 유기농 배추

[파이썬] 백준 1012 : 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 실버 2 그래프 이론, DFS, BFS 런타임 에러가 발생할 수 있으므로 sys.setrecursionlimit(10 ** 6) 와 같은 값을 넣어주는 것이 좋다. DFS의 방법을 활용해서 구하는 문제로, dfs기능을 하는 함수 내에서 좌표를 이동하는 방법을 고안해야 한다. 코드 import sys; input = sys.stdin.readline sys.setrecu..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 26.
• textsms

[파이썬] 백준 22659 : 구간 합 구하기4

[파이썬] 백준 22659 : 구간 합 구하기4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 실버 3 누적 합 입력받는 리스트의 범위가 100000이나 되므로 반복문으로 단순구현하면 시간초과가 난다. 따라서 각 인덱스까지의 값을 따로 저장할 리스트를 구현하고 필요한 값을 뽑아쓰는 방식으로 접근해야 한다. 반복문을 사용해 이를 만들어 낼 수 있지만, itertools의 accumulate를 사용하면 해당 리스트의 누적합..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 24.
• textsms