본문 바로가기

글

 (385)
[Python] 9024번 두 수의 합 https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 24/02/12 이전에 실패 했던 문제를 다시 풀어보았다. 전형적인 투 포인터 문제이지만, 포인터를 움직이는 방향에 유의해서 문제를 해결해야만 했었다. 문제 접근 방식: 특정한 값이 주어져 있고, 그 값에 가장 가까운 두 수의 합을 만들 수 있는 모든 조합을 찾는 것이 문제의 목표이다. 투 포인터 문제임을 보자마자 파악했지만, 포인터를 움직이는 방향에 유의해야만 했다. 나는 두 가지 경우로 분리해서..
[Python] 23325번 마법천자문 https://www.acmicpc.net/problem/23325 23325번: 마법천자문 최근最近 만화漫畫 마법천자문魔法千字文을 감명感銘 깊게 읽은 연두然斗는, 모든 수數를 한자漢字로 적기 시작始作했다. 그런데 수업授業을 들으면서 필기筆記 해놓은 내용內容을 복습復習 www.acmicpc.net 24/02/08 업 다운 랜디를 하다 만난 문제로, 처음에 어떤 알고리즘을 적용해야 할 지 몰라 많이 헤맸던 문제다. 문제 접근 방식: 처음에 접근했던 방식은 무지성 dfs였다. 열심히 짰지만 당연히 시간초과가 났다. 태그를 까고 곧바로 어떻게 풀지 알아버렸는데, 태그는 DP였다. 상태 식은 다음과 같이 정의된다. $$DP[i] = i\textrm{번째 문자까지 보았을 때 해석할 수 있는 가장 큰 계산 결과}$..
[Python] 25512번 트리를 간단하게 색칠하는 최소 비용 https://www.acmicpc.net/problem/25512 25512번: 트리를 간단하게 색칠하는 최소 비용 0번 정점을 black, 1번 정점을 white, 2번 정점을 white, 3번 정점을 black, 4번 정점을 black, 5번 정점을 black, 6번 정점을 black, 7번 정점을 white로 색칠하는 비용 310이 정답이다. www.acmicpc.net 24/02/08 간단한 그래프 탐색 문제로, 트리의 성질을 이용한 교육적인 좋은 문제다. 문제 접근 방식: 트리를 색칠할 수 있는 최소 비용을 문제에서는 요구하고 있고, 인접한 노드마다 항상 다른 색깔로 칠해야 한다는 제약 조건이 걸려있다. 요지는, 트리는 이분 그래프라는 점이다. 트리는 이분 그래프이기 때문에, 루트를 중심으로 ..
[Python] 2290번 LCD Test https://www.acmicpc.net/problem/2290 2290번: LCD Test 첫째 줄에 두 개의 정수 s와 n이 들어온다. (1 ≤ s ≤ 10, 0 ≤ n ≤ 9,999,999,999)이다. n은 LCD 모니터에 나타내야 할 수 이며, s는 크기이다. www.acmicpc.net 24/02/04 좀 귀찮은 구현 문제로, 침착하게 구현하면 맞을 수 있는 문제이다. 문제 접근 방식: 문제의 요구 사항은 꽤나 명확한 편이다. 숫자의 크기가 주어지고, 이 크기를 가지는 숫자를 그대로 출력하면 된다. 나는 숫자 하나와 그 크기를 입력 받아 그 크기를 가지는 숫자를 리스트로 반환하는 함수를 구현했다. 아래 코드를 보면 알 수 있듯, $8$의 경우는 모든 세그먼트가 다 켜진다고 간주할 수 있기 때..
[Python] 2676번 라스칼 삼각형 https://www.acmicpc.net/problem/2676 2676번: 라스칼 삼각형 첫째 줄에 테스트 케이스의 개수 T(1
[Python] 1364번 울타리 치기 https://www.acmicpc.net/problem/1364 1364번: 울타리 치기 육각형 블록들로 이루어진 RPG 세계가 있다. 그 세계에 나라를 세우려고 하는 군주 캐릭터 송유진은 일반 블록을 울타리 블록으로 바꿀 수 있는 아이템을 N개 가지고 있다. 유진이가 이 N개의 아 www.acmicpc.net 24/01/16 백준 그룹 연습 문제로 나왔던 문제 중 하나다. 수열의 규칙을 찾아서 이를 코드로 구현하면 된다. 문제 접근 방식: 수열의 규칙은 다음과 같이 찾았다. 먼저, $1$부터 $5$까지는 $1$부터 $5$그대로 나옴을 쉽게 확인할 수 있다. $6$부터는 조금 다르게 나오는데, 그 이유는 육각형 울타리가 둘러싸는 면적이 생기기 때문이다. $7$의 경우는 다음과 같이 나온다. $8$의 경..
[Python] 2084번 차수열 https://www.acmicpc.net/problem/2084 2084번: 차수열 첫째 줄부터 N개의 줄에 걸쳐 그래프의 인접 행렬을 출력한다. 인접 행렬은 0 또는 1로 이루어지며, 답이 여러 개인 경우는 그 중에 하나만 출력하면 된다. 그래프가 존재하지 않는 경우에는 첫째 www.acmicpc.net 24/01/19 이전에 차수열이 주어졌을 때 트리를 만드는 문제를 풀었었는데, 그 문제와 접근 방식이 동일하여 빠르게 아이디어를 떠올릴 수 있었던 문제였다. 다만, 이 문제는 우선순위 큐를 사용하여 구현하지 않고, 그때그때 마다 정렬하여 문제를 해결하여도 쉽게 풀리는 문제이기 때문에 그 문제보다 약간 낮은 난이도를 받은 것 같다. 나름 유명한 문제로, 그래프 이론을 조금 배웠다면 해결할 사람들은 쉽게..
[Python] 1038번 감소하는 수 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 24/01/16 백트래킹 혹은 브루트 포스로 구현할 수 있는 유명한 문제이다. 비트마스킹을 이용해 구현하는 색다른 방법을 발견하여 적어보고자 한다. 기존 문제 접근 방식: 처음 문제를 접근했을 때에는 문제의 조건을 만족하는 함수 bruteforce를 작성했었다. 이 함수는 재귀적으로 호출을 하는 함수로, 호출을 받을 때마다 인자로 받은 현재 숫자를 리스트에 추가하고, 조건을 만족하도..

티스토리툴바