저울의 무게 비교를 그래프로 바꿔서 최단 거리 알고리즘으로 해결(플로이드 워셜, 그래프 탐색)

1. 문제 10159번: 저울 (acmicpc.net) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 2. 풀이 그냥 보면 어떻게 해야할지 감 잡기가 쉽지 않다.. 하지만 "2 > 3, 3 > 4로부터 2 > 4라는 것을 알 수 있다"를 봤을때, 1 > 2, 2 > 3, 3 > 4, 5 > 4, 6 > 5를 마치 방향 그래프에서 간선으로 보면 2에서 4로 도달할 수 있는가? 아닌가를 체크하면 되는 문제이다. 사실 뭐 최단 거리를 묻는 것은 아니므로 BFS나 DFS로 탐색하면 해결할 수..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 9. 7.
• textsms

다이나믹 프로그래밍+BFS+그리디 - 정확히 K번만에 목표에 도달할 수 있는가?

1. 문제 28069번: 김밥천국의 계단 (acmicpc.net) 28069번: 김밥천국의 계단 첫 번째 줄에 계단 개수에 해당하는 $N$, 계단을 오르는 횟수 $K$가 주어진다. $(1 \leq N, K \leq 1\,000\,000)$ www.acmicpc.net 2. 풀이1 그냥 보면 두가지 행동중 하나를 할 수 있는 전형적인 BFS문제 1) 한칸을 올라간다 2) $\left \lfloor \frac{i}{2} \right \rfloor$만큼 올라간다 0번부터 시작한다고 명시되어 있으니 BFS처럼 풀어보면.. 정확히 K번 행동해야하면서 매 행동마다 queue의 길이만큼 순회시키는데 해당 좌표 i가 i+1과 i+i//2를 이동할 수 있으면 queue에 넣어주고.. K번 행동한 후에 n이 queue에 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 6. 20.
• textsms

탐욕적인 사람 되기 -정수 a를 k로 만들기 문제-

1. 문제 25418번: 정수 a를 k로 만들기 (acmicpc.net) 25418번: 정수 a를 k로 만들기 7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다. www.acmicpc.net 정수 a에 1을 더하거나 2를 곱해서 k를 만들때, 연산 횟수의 최솟값을 구하는 문제 2. 풀이1(BFS) 이 문제의 기본은 BFS로 푸는 것이다 정수 a에서 시작해서, delta 배열은 1,2가 있고 1이 나오면 a + 1에 가서 범위를 벗어난건지, 이미 방문했는지 검사 2가 나오면 2a에 가서 범위를 벗어난건지, 이미 방문했는지 검사 from collections import deque def bfs(..

• format_list_bulleted 그리디 알고리즘
• · 2023. 1. 5.
• textsms

이분 그래프 판별하는 알고리즘 분석

1. 문제 그래프의 정점의 집합을 둘로 분할하는데 각 집합에 속하는 정점끼리는 서로 간선이 존재하지 않도록 분할하고 싶다. 이것이 가능한지를 판별하는 프로그램을 작성해본다면? 2. DFS 알고리즘 무방향 그래프라고 가정함 어떤 정점을 방문하면서 방문한 정점에 그룹 1을 할당 인접한 정점을 순회하면서, 인접한 정점이 방문하지 않은 정점이면 그룹 -1을 할당하고 방문 하지만 인접한 정점이 이미 방문한 정점이라면, 현재 정점의 그룹(현재 그룹이 할당됨)과 이미 방문한 정점(이미 그룹이 할당됨)이 서로 같은 그룹이면 이분 그래프가 아니다 3. 예를 들어서 생각해보기 다음과 같은 그래프가 이분 그래프인지 생각해보자 임의의 정점 아무거나 하나를 선택하고 방문을 시도 방문하면서 파란색을 부여한다 현재 방문한 정점과 ..

• format_list_bulleted 이분 매칭
• · 2022. 11. 5.
• textsms

DFS/BFS 정복하기 -영역을 구분하는 BFS의 성질 응용-

1. 문제 16234번: 인구 이동 (acmicpc.net) 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net N*N 크기의 배열에서 인접한 두 칸의 크기 차이가 L이상, R이하이면 연합을 이룬다. 모든 연합을 이루게 하고, 크기를 조절한 다음에 이러한 과정을 반복할때, 몇번이나 가능한지 구하는 프로그램을 작성 2. 풀이 문제를 잘 읽어보면 시뮬레이션을 수행해야한다 주어진 배열에서 인접한 두 칸의 차이가 L 이상, R 이하인지를 파악한다. 그러한 두 칸을 서로 연결하고, 이것을 배열의 모든 칸에 대..

• format_list_bulleted DFS BFS 정복기
• · 2022. 9. 23.
• textsms

BFS/DFS 정복기 -memoization을 이용한 효율적인 탐색-

1. 문제 1861. 정사각형 방 ttps://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE&problemTitle=정사각형+방&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 $n^{2}$개의 방이 $N*N$ 형태로 늘어서있고, 각각은 1부터 $n^{2}$이하까지 전부 서로 다른 수로 순서와 무관하게 적혀있다. 어떤 방에 있을때, 정확히 현재 방보다 1 더 큰 수가 적힌 방으로만 이동할 수 있다고 할때, 처음에 어떤 수가 ..

• format_list_bulleted DFS BFS 정복기
• · 2022. 9. 18.
• textsms