본문 바로가기

알고리즘

 (364)
[Python] 32653번 흑백 요리사 https://www.acmicpc.net/problem/32653 24/11/20  간단한 정수론 문제다. 문제 접근 방식:  하나의 고기 앞/뒷면을 모두 익히기 위해서는 최소 $2x_i$만큼의 시간이 필요하다. 모든 고기를 동시에 다 익혀야 하므로, $2x_i$들의 최소 공배수만큼 익히는 것이 최소 시간이 된다.아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.더보기# 32653번 흑백 요리사# 정수론import sysinput = sys.stdin.readlinefrom math import lcmN = int(input())A = list(map(lambda x: 2*int(x), input().split()))print(lcm(*A))
[Python] 29154번 작곡가 A의 시창 평가 https://www.acmicpc.net/problem/29154 24/05/16  이전에 해결했었던 스그 문제인데, 꾸역꾸역 kmp랑 엮어서 만들었다는 느낌을 너무 강하게 받은 문제이다. 문제 접근 방식:  일단 선/후공 승패 여부 판단하고, 색칠된 부분이 여러 개의 모습으로 분리되며, 색칠된 부분을 그냥 님게임으로 간주할 수 있다는 사실은 스프라그 그런디 정리를 많이 풀어본 사람이라면 쉽게 파악할 수 있을 것이다. 문제는 그러면 색칠된 부분을 어떻게 빠르게 구할건데?가 핵심이 된다. 보면 멜로디 $L$과 멜로디 $L$의 접미사들을 "모두" 기존 문자열 $S$에서 찾아야 한다.(빠르게) 그러면 당연히 생각나는건? kmp다. kmp의 동작 원리를 생각하면 접두사와 접미사가 일치하는 부분을 통해 "당겨옴..
[Python] 2733번 Brainf*ck https://www.acmicpc.net/problem/2733 24/11/18  입력 커맨드를 제외한 brainfuck 인터프리터를 구현하는 문제이다. 문제의 핵심 부분은 괄호 쌍을 찾아서 넘어가는 부분이다. 문제 접근 방식:  구현의 용이성을 위해, 먼저 파싱부분과 인터프리터 부분을 나눴다.  기본적으로 파싱부분은 하나의 테스트 케이스를 입력받아서 프로그램에 해당하는 하나의 문자열을 내뱉는 함수로 구현했다. 하나의 테스트 케이스는 'end'만 적혀 있는 문자열로 구분된다. 따라서 'end'라는 문자열이 입력되기 전 까지 계속해서 입력을 받는다. 파이썬은 줄바꿈을 기준으로 문자열을 입력받기 때문에, while True를 사용하여 'end'를 입력 받을 때까지 계속 입력받도록 했다. 이후, 주석의 처리..
[Python] 32390번 과녁 맞히기 https://www.acmicpc.net/problem/32390 24/11/17  이전에 KCPC때 검수 못했던 문제 중 하나인데, 이제서야 풀어본다. 사실 그때 한 30분 정도 생각해보다가 답이 안나와서 그냥 GG치고 다른 문제를 봤다. 이제서야 붙잡은 이유는 큰 이유는 없고, 그냥 좀 붙잡으면 풀릴 것 같아서 붙잡았다. 이 문제를 풀기 위해선, 모듈로 곱셈 역원에 대한 지식이 필요하다. 문제 접근 방식:  문제가 뭔가 수능에서 나올법 한 경우의 수 문제랑 비스무리 하다. $M$개의 줄이 있고, 각 줄에는 과녁이 $A_i$개 만큼 달려있다. 나는 과녁을 쏠 때, 각 줄에서 위 또는 아래만 쏠 수 있다.이 문제에서 구하고자 하는 것은 과녁을 쏘는 전체 경우의 수이다.  일단 각 줄 별로 생각을 하면,..
[Python] 32612번 Expected Eyes https://www.acmicpc.net/problem/32612 24/11/15  두 가지 방법으로 풀 수 있다. 둘다 소개해보려고 한다. 문제 접근 방식:  1. 파이썬의 itertools모듈의 product함수를 이용한다. 직접 모든 가능한 경우의 수를 조사하면서 기댓값을 구한다. 이 접근방식의 시복도는 최대 $\mathcal{O}(8^8)$이다. 따라서 파이썬3로는 통과하기 힘들고 파이파이로 하면 통과된다. 2. 기댓값의 선형성 이용 전체 기댓값은 선형성에 의해 각 주사위의 기댓값의 합과 같다. 이를 이용하면 한줄로 코딩할 수 있다.아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.더보기# 32612번 Expected Eyes# 1. 나이브한 반복 풀이..
[Python] 1178번 간선 추가 https://www.acmicpc.net/problem/1178 24/09/02  몇 번 잘못된 접근을 한 문제였기 때문에 어떻게 잘못된 접근을 했는지를 중심으로 적어보겠다. 문제 접근 방식:  먼저 한붓그리기라는 점에서 오일러 경로 문제임을 파악했다. 오일러 경로가 존재하려면 그래프 정점의 차수를 모두 센 다음에, 차수가 홀수인 정점이 0개 혹은 2개 있어야 한다.이러한 사실을 기반으로, 처음에는 다음과 같은 접근 방식을 세웠다. 먼저, 한붓그리기를 하려면 모든 정점이 서로 이어져 있어야 한다. 따라서, 정점의 차수가 0이라면 그 누구와도 이어져 있지 않으므로, 이것을 고려해주었다. 그리고 오일러 경로가 존재하려면 차수가 홀수인 정점이 0개 혹은 2개 있어야 한다는 사실에 기반하여, 정점의 차수가 홀..
[Python] 2418번 단어 격자 https://www.acmicpc.net/problem/2418 24/11/14  예전에 북마크 해뒀다가 지금 해결한 문제다. 해결 방식은 어제 해결했던 내리막길 문제와 유사하다. 문제 접근 방식:  탑다운 DP로 접근했다. DP상태는 다음과 같이 정의했다. DP[i][j][k] = 지금까지 단어에서 k번째 글자까지 읽었고, (i, j)에 위치한 글자가 단어에서 k번째 글자일 때, 단어를 읽을 수 있는 방법의 수 이후, 모든 격자 칸을 조사하며, 이 격자 칸에 적힌 글자가 단어의 첫 글자와 일치한다면, 즉, (i, j)에 위치한 글자가 단어의 0번째 글자라면 DP[i][j][0] = 1로 초기화 해주었다. 이후 dfs를 통해 주변 8방향을 조사하며 구현했다. 우리가 원하는 값은 단어의 마지막 글자와 (..
[Python] 1520번 내리막 길 https://www.acmicpc.net/problem/1520 24/11/13  무난한 DP이다. 처음에는 바텀업으로 생각했으나, 잘 생각나지 않아서 탑다운으로 짰다. 문제 접근 방식:  DP식을 다음과 같이 정의하자. DP[i][j] = $(i, j)$번째 칸에 왔을 때 항상 내리막 길로만 오는 경우의 수. 우리의 목적은 $DP[N-1][M-1]$의 값을 구하는 것이다. 또한, $DP[0][0] = 1$임을 알고 있다. 내리막 길로 간다는 것은 현재 칸보다 이전의 칸에 쓰여있는 숫자가 더 크다는 뜻이다. 따라서, 기본적으로 현재 칸을 둘러싸고 있는 4개의 주변 칸, 즉, 이전의 칸에 쓰여있는 숫자가 더 크다면, 그 칸을 통해 현재 칸으로 올 수 있다. 따라서, 4개의 주변 칸에 대해서 DP값을 찾아..

티스토리툴바