[백준 파이썬] 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

[백준 파이썬] 4485 녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 N*N의 배열에서 [0][0] 에서 [N-1][N-1]까지의 경로중 가장 적은양의 Cost가 필요한 길을 찾는 문제이다. 풀이 가장 작은 Cost를 구하는 BFS문제이므로 다익스트라 알고리즘을 사용하였다. def dijsktra(startCost): q = [] heapq.heappush(q, (startCost, 0, 0)) distance[0][0] = startCost..

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