본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 4949번 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 22/08/28 마찬가지로 클래스 2++ 문제 중 안 푼 문제가 있길래 풀어본 문제이다. 전형적인 스택을 사용한 응용문제이며, 괄호 문자열에 대한 개념을 알고 있었으면 더 쉽게 푸는 문제이다. 접근 방법: 문제에서 주어진 대로 접근했다. 이제 괄호 스택을 하나 만드는데, '(' 나 '['가 나올 때마다 괄호 스택에 차곡차곡 그 괄호들을 넣어준다. 마찬가지로, ')' 나 ']'..
[Python] 2805번 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 22/08/28 보자마자 날먹 문제라고 생각했다. 이 문제는 그제 풀었던 1654번 랜선 자르기 문제와 거의 동일한 문제였기 때문이다. 단지 약간의 조건만 달랐다. 문제 접근 방법: 랜선 자르기 문제와 동일한데, 나무를 일정 간격으로 계속 자르는 게 아니라, 일정 높이를 두고 일정 높이 이상인 나무만 한 번 자른다는 점만 다르다. 다시 말해, 나누기를 하는게..
[Python] 1874번 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 22/08/28 마찬가지로 클래스 2++에 해당하는 문제 중 풀지 않은 문제가 있어서 풀은 문제이다. 문제 풀이 자체는 그렇게 마구 어렵다거나 그러지는 않는데 문제 해석이 조금 난감했던 문제이다.(내 국어 능력이 부족한 탓 일 수도 있다.) 하지만, 여러 번 틀렸다거나 그러지는 않았고 한 번에 맞았다. 지금 되돌아 ..
[Python] 3533번 Explicit Formula https://www.acmicpc.net/problem/3533 3533번: Explicit Formula Consider 10 Boolean variables x1, x2, x3, x4, x5, x6, x7, x8, x9, and x10. Consider all pairs and triplets of distinct variables among these ten. (There are 45 pairs and 120 triplets.) Count the number of pairs and triplets that contain at least one variab www.acmicpc.net 22/08/27 오늘은 좀 바빠서 브론즈 한 문제만 풀고 넘기려고 했다. 근데 왠걸, 브론즈 3 문제 치고는 비주얼..
[Python] 1654번 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 22/08/26 클래스 2 문제 중 안 푼 문제가 있길래 푼 문제이다. 전형적인 이분탐색 문제이고, 이분탐색 문제 특성상 범위나 종료 조건을 잘못 설정하면 맞왜틀을 하기 쉽기 때문에 나도 맞왜틀을 여러 번 했다. 당연히 이분탐색이 무엇인지 알고 있다는 전제 하에서 글이 쓰여있으므로, 풀이를 참고할 생각이 있다면 이분 탐색기법을 알아야 할 것이다. 문제 접근 방법: 기존..
[Python] 1699번 제곱수의 합 / 17626번 Four Squares https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 22/08/..
[Python] 2013번 선그리기 https://www.acmicpc.net/problem/2013 2013번: 선그리기 첫째 줄에 선분의 개수 N(1 p2[0]: return p1 elif p1[0] = p2[1]: return p1 else: return p2 def point_swap(p1, p2): if point_compare(p1, p2) == p1: return p2, p1 else: return p1, p2 def line_swap(p1, p2, p3, p4): if point_compare(p1, p3) == p1: return p3, p4, p1, p2 else: return p1, p2, p3, p4 def can_draw_once(line1, line2)..
[Python] 21650번 Чемпионат по стрельбе https://www.acmicpc.net/problem/21650 21650번: Чемпионат по стрельбе Победитель школьного этапа олимпиады по информатике нашел дома в старых бумагах результаты чемпионата страны по стрельбе из лука, в которо www.acmicpc.net 22/08/24 이 문제 또한 실버 랜덤 디펜스를 하다가 만나게 된 문제이다. 어떻게 보면 언어의 장벽이 제일 크게 느껴졌던 문제였다. 잘못 해석하고, 실수해서 9번이나 틀렸습니다! 를 받았으니깐 말이다. 이 문제를 통해 얻은 점은 러시아어 문제를 풀 때는 영어로 한번 중역을 해야 자연스럽게 번역이 된다는 사실이..

티스토리툴바