본문 바로가기

알고리즘

 (368)
[Python] 1325번 효율적인 해킹 https://www.acmicpc.net/problem/1325 max_hacked: ans = [] ans.append(start) max_hacked = hacked elif hacked == max_hacked: ans.append(start) print(*ans) main()
[Python] 26260번 이가 빠진 이진 트리 https://www.acmicpc.net/problem/26260 26260번: 이가 빠진 이진 트리 김소마는 최근에 포화 이진 트리에 대해 배웠다. 포화 이진 트리란, 이진 트리에서 리프 노드를 제외한 모든 노드가 두 자식 노드를 가지며, 모든 리프 노드가 채워진 것을 말한다. 아래의 그림 www.acmicpc.net 24/02/16 업다운 랜디를 하다가 만난 문제로, 처음 보고 뇌 정지가 와서 잘 해결하지 못했던 문제다. 이후 다시 풀게 되었고, 생각보다 간단한 해결 방법이 있어 글을 쓴다. 문제 접근 방식: 문제의 요구 조건은, 포화 이진 트리이면서 이진 검색 트리인 트리가 주어졌을 때, 특정 부분을 제거하고 다시 새롭게 썼을 때 바뀌는 트리의 후위 순회 결과를 출력하는 것이다. 처음에 보고 정석..
[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$의 경..

티스토리툴바