[백준 파이썬] 1520 내리막 길

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제  주어진 2차원 배열에서 내리막으로만 갈 수 있는 길의 경우의 수를 계산하는 문제이다. 풀이 가장 먼저 떠오른 방법은 DFS를 이용하여 경로를 찾는 것이었다. 하지만 DFS를 단독으로 사용하면 수많은 경로를 모두 탐색해야 하기 때문에 시간초과가 발생한다. 따라서 DP와 DFS를 같이 사용해야한다. graph = [list(map(int, input().split())) for _ in r..

• format_list_bulleted 알고리즘
• · 2024. 2. 1.
• textsms

[백준 파이썬] 1339 단어 수학

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제  알파벳에 적절한 숫자를 부여하여 합이 최대가 되게 하는 문제이다. 풀이 먼저 최대값을 구하는 방법을 생각해야한다. 예제의 GCF + ACDEB의 경우 783 + 98654 로 계산할 수 있다. 이는 가장 높은 자리의 알파벳에는 높은 숫자를 부여하고 낮은 자리의 알파벳은 낮은 숫자를 부여하는 방법으로 해결할 수 있다. 먼저 단어를 입력받고 해당 단어를 배열로 저장한다. 그러면 ['G'..

• format_list_bulleted 알고리즘
• · 2024. 1. 29.
• textsms

[백준 파이썬] 2293 동전 1

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 주어진 동전을 합해서 원하는 숫자를 만드는 경우의 수를 구하는 문제이다. 풀이 경우의 수를 구해야 하기 때문에 Dp를 사용하여 해결하였다. 1차원 배열에 동전마다 가능한 경우의 수를 누적하면서 구하는 방식으로 해결하였다. DP[N]은 N을 만들기 위해 필요한 경우의 수이다. 예를들어 1로만 이루어진 동전으로 1~N개의 숫자를 만드는 경우의수를 구할 때 DP[1] ~ DP[N] 값은 모두 1이 ..

• format_list_bulleted 알고리즘
• · 2024. 1. 25.
• textsms

[백준 파이썬] 2110 공유기 설치

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 지정된 공유기 개수를 설치했을 때 가장 인접한 두 공유기 사이의 거리를 최대로 하는 문제이다. 아이디어 집의 좌표의 최대 개수가 1,000,000,000이므로 이를 완전탐색으로 풀려고하면 시간초과가 나오게 된다. 따라서 이분탐색을 이용하여 해결하였다. 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 ..

• format_list_bulleted 알고리즘
• · 2024. 1. 23.
• textsms

[백준 파이썬] 1918 후위 표기식

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 문제 중위표기식으로 표현된 식을 후위 표기식으로 바꾸는 문제이다. 풀이 우리가 흔히쓰는 식은 모두 중위표현식이다. 이를 후위표기식으로 바꾸는 예시는 다음과 같다. A*(B+C) -> ABC+* A+B -> AB+ 이런식으로 후위표기식으로 바꾸기 위해서는 다음의 조건을 만족해야한다. 1. 피연산자는 그대로 출력한다. 2. 연산자는 스택에 추가한다. 2.1 이 때 스택의 가장 위에있는 연산자가 자..

• format_list_bulleted 알고리즘
• · 2024. 1. 20.
• textsms

[백준 파이썬] 12919 A와 B 2

12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 문제 처음 제시된 문자열 S에 A를 더하거나 또는 B를 더한 후 뒤집는 과정을 반복해서 나중에 제시된 문자열 T로 만들 수 있는지 확인하는 문제이다. 풀이 처음에는 문제에 제시된 대로 S를 T로 만드는 코드를 작성해서 해결하려 했다. 하지만 시간초과가 나서 게시판을 확인해보니 S에서 T로 만드는게 아닌 T에서 S로 만들어야 한다는 글이 있었다. 따라서 T에서 S로 만드는 방법을 사용했다. 먼저 조건문을 만들어서 분기를 나누..

• format_list_bulleted 알고리즘
• · 2024. 1. 18.
• textsms