본문 바로가기

Algorithm706

[동적계획법/DP] 백준 9251 LCS - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2. 문제 풀이 ACAYKP CAPCAK 두 문자열의 LCS(Longest Common Subsequence, 최장 공통 부분 수열)을 구하는 문제입니다. 단순히 부분 문자열을 구하는 게 아니라, 떨어져 있어도 순서만 맞으면 공통 부분 수열이 될 수 있습니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래.. 2022. 9. 24.
[구현/수학] 백준 8723 Patyki - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 8723번: Patyki Pierwszy wiersz wejścia zawiera trzy liczby całkowite a, b, c (1 ≤ a, b, c ≤ 1000), oznaczające odpowiednio długości pierwszego, drugiego i trzeciego patyka. www.acmicpc.net 2. 문제 풀이 세 변의 길이가 주어집니다. 해당 삼각형이 정삼각형인지, 직각삼각형인지, 둘 다 될 수 없는지를 판별해야 합니다. 정삼각형의 조건: 세 변의 길이가 모두 같음 직각삼각형의 조건: (긴 변)**2 = (짧은 변)**2 + (짧은 변)**2 참고로, 삼각형이 성립하는 조건은 '긴 변 < 짧은 변 + 짧은 변'으로 .. 2022. 9. 23.
[구현/수학] 백준 15051 Máquina de café - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 15051번: Máquina de café A entrada consiste em 3 números, A1, A2, A3 (0 ≤ A1, A2, A3 ≤ 1000), um por linha, onde Ai representa o número de pessoas que trabalham no i-ésimo andar. www.acmicpc.net 2. 문제 풀이 1 ~ 3 층 중 어느 곳에 커피머신을 두는 게 좋은지 고르는 문제입니다. 각 층별 사원 수가 입력으로 주어지며, 사원들은 매일 1잔씩 커피를 마십니다. 계단을 한 번 오르거나 내릴 때 1분이 소요되며, 이를 감안하여 최소의 소요시간을 구해야 합니다. 3. 코드 # 입력 A1 = int(input().. 2022. 9. 22.
[탐색/자료구조] 백준 1991 트리 순회 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 2. 문제 풀이 주어진 트리를 '전위', '중위', '후위' 탐색하는 문제입니다. 전위 순회: 중간 -> 왼쪽 -> 오른쪽 중위 순회: 왼쪽 -> 중간 -> 오른쪽 후위 순회: 왼쪽 -> 오른쪽 -> 중간 자료구조 단골 시험문제죠. "주어진 트리를 전위/중위/후위 순회하시오." 전위와 중위는 탐색 경로는 같으나, '방문'하는 시점이 다릅니다. '전위'는 루트부터 찍고 왼쪽 오른쪽을 탐색하고, '중위'는 .. 2022. 9. 21.
[구현/수학] 백준 21335 Another Eruption - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 21335번: Another Eruption A volcano has recently erupted in Geldingadalur, Iceland. Fortunately this eruption is relatively small, and---unlike the infamous Eyjafjallajökull eruption---is not expected to cause delayed international flights or global outrage. There is some concern www.acmicpc.net 2. 문제 풀이 원의 넓이가 주어집니다. 이를 통해서 원주의 길이를 구해야 합니다. 3. 코드 from math import pi # .. 2022. 9. 20.
[구현/수학] 백준 8710 Koszykarz - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 8710번: Koszykarz W pierwszej linii wejścia 3 liczby całkowite: k, w, m (1 ≤ k ≤ 200, 1 ≤ w, m ≤ 109), oznaczające odpowiednio wysokość Kozika, wymaganą przez trenera wysokość oraz wartość powiększania się guza po każdym uderzeniu. www.acmicpc.net 2. 문제 풀이 원하는 키(k)만큼 되기위해, 머리를 후려칩니다. 머리를 후려칠 때마다, 혹이 m cm씩 자라납니다. 몇 번 때려야 k이상이 될 수 있을까요? (신박한... 또라이..) 3. 코드 # 입력 k, w, m =.. 2022. 9. 19.
[Greedy/그리디] 백준 16435 스네이크버드 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 2. 문제 풀이 스네이크버드의 길이와 과일들의 높이가 주어집니다. 스네이크버드가 과일을 1개 먹을 때마다 1씩 길이가 늘어나며, 자신의 길이보다 낮거나 같은 과일들은 먹을 수 있습니다. 스네이크버드가 최대로 자랄 수 있는 길이를 구해야 합니다. 2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 .. 2022. 9. 18.
[구현/수학] 백준 15474 鉛筆 (Pencils) - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 15474번: 鉛筆 (Pencils) JOI 君は10本の鉛筆を入手したい．セット X は3本で100円，セット Y は5本で180円である．この時，セット X を選んだ場合は，セットを4つ購入する必要があり400円必要である．セット Y を www.acmicpc.net 2. 문제 풀이 n개의 연필을 사야 합니다. X세트에는 a개를 b 값에 팔고, Y세트에는 c개를 d값에 팝니다. 어느 세트를 사는 게 유리한지 구하는 문제입니다. 각 세트를 구입했을 때, 들어가는 비용을 계산합니다. 3. 코드 # 입력 n, a, b, c, d = map(int, input().split()) # 계산 X = n//a if n % a != 0: X += 1 Y = n//c if n % c != .. 2022. 9. 17.
[구현/수학] 백준 18411 試験 (Exam) - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 18411번: 試験 (Exam) JOI 君は情報の試験を 3 回受けた．試験の点数はすべて 0 以上 100 以下の整数である． JOI 君の成績は 3 回の試験の点数のうち高い方から 2 つを足し合わせた合計によって決まる． 3 回 www.acmicpc.net 2. 문제 풀이 시험 점수 3개가 주어집니다. 제일 못 본 과목을 제외한, 점수의 합을 구합니다. 3. 코드 # 입력 a, b, c = map(int, input().split()) # 출력 print(sum((a, b, c)) - min(a, b, c)) 2022. 9. 16.

티스토리툴바