본문 바로가기

파이썬

 (320)
[Python] 16456번 하와와 대학생쨩 하와이로 가는 거시와요~ (추후 보강 예정) 16456번: 하와와 대학생쨩 하와이로 가는 거시와요~ (acmicpc.net) 16456번: 하와와 대학생쨩 하와이로 가는 거시와요~ 첫째 줄에 하와이 열도의 섬의 개수 n(1 ≤ n ≤ 50,000)이 주어지는 거시와요 하와와. 하와와! 답이 커질 수 있으니 1,000,000,009로 나눈 나머지를 출력해 주시는 거시와요! www.acmicpc.net 22/09/03 그룹 연습에서 푼 문제로, DP문제여서 몇 개 나열해보다가 신뢰의 제출을 해서 맞았다. 문제 접근 방식: 먼저 숫자를 몇 개 구해봤다. 그래서 점화식을 dp[i] = (dp[i-1] + dp[i-3]) 과 같이 유추를 했는데, 그에 대한 정당성을 세워야만 했다. 근데 아직까지 정당성을 세우지는 못했다. 이후 정당성을 세운다면, 보충해서 ..
[Python] 16956번 늑대와 양 16956번: 늑대와 양 (acmicpc.net) 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net 22/09/03 그룹 연습 중 풀었던 문제이다. 그래프 문제임에도 불구하고, 재치 있는 아이디어로 쉽게 풀 수 있는 문제여서 즐겁게 풀었었다. 문제 접근 방식: 먼저 가능한 경우와 불가능한 경우를 따지는 것이 우선이라고 생각하였다. 가능한 경우라면, 울타리를 칠 때, 빈 들판에다 모두 울타리를 쳐버리면 양도 늑대도 모두 못 움직이니깐 늑대가 양을 잡아먹지 못하도록 만들 수 있을 것이라고 생각했다. 어차피 이 문..
[Python] 1551번 수열의 변화 1551번: 수열의 변화 (acmicpc.net) 1551번: 수열의 변화 첫째 줄에 수열의 크기 N과 K가 주어진다. N은 20보다 작거나 같은 자연수이고, K는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다. 둘째 줄에는 수열이 ‘,’로 구분되어 주어진다. 수열을 이루 www.acmicpc.net 22/09/03 마찬가지로 그룹 연습에서 풀었던 문제이다. 문제 자체는 매우 쉬운 편으로, 문제에서 주어진 상황을 반복문으로 그대로 구현하면 된다. 문제 접근 방식: 그대로 구현했다. 개인적으로 글을 쓸 필요도 없을 정도로, 딱히 작성할 내용이 없다. 왜 브론즈 1인지 이해가 되지 않는다. 아래는 내가 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다. 더보기 # 1551번 수열의 변화 N, ..
[Python] 21313번 문어 21313번: 문어 (acmicpc.net) 21313번: 문어 문어에게 여덟개의 팔이 있다는 사실은 잘 알려져 있다. 하지만 문어들이 자신의 팔들을 1번, 2번, 3번, ..., 8번이라고 부른다는 말은 오늘 처음 들었을 것이다! 단, 시계방향으로 오름차순이라던 www.acmicpc.net 22/09/03 그룹에서 연습문제로 같이 풀었던 문제 중 하나이다. 간단한 그리디 문제로 쉽게 풀 수 있었다. 문제 접근 방식: 예제 입력을 보고 짝수일 때의 경우를 쉽게 유추할 수 있었다. 붙어있는 배열의 두 원소가 서로 다르고, 그 배열들 중에서 제일 사전 순으로 앞서는 것을 출력하면 되므로, 그리디적인 방법으로 보았을 때, 1과 2가 반복되는 문자열을 출력만 하면 된다. 홀수일 때의 경우는 짝수일 때의 경우에서..
[Python] 2022번 사다리 2022번: 사다리 (acmicpc.net) 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net 22/09/02 은근히 어려웠던 문제이다. 요즘 태그를 보지 않고 문제를 푸는데, 이분 탐색을 활용하는 문제가 아니라 온전히 답안이 나오는 문제인 줄 알고 식 정리에만 시간을 온전히 쏟았다. 알고 보니 명확한 식으로 나오지 않는 문제임을 알고서 이분 탐색을 활용하여 문제를 풀었다. 식 정리가 제일 어려운 문제이다. 문제 접근 방식: 그냥 식 정리를 한 뒤에 이분 탐색으로 문제를 풀면 된다. 이 식 정리가 좀 어렵긴 하지만, 사진으로 나와있으니 참고하..
[Python] 9663번 N-Queen (추후 보강 예정) 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 22/09/01 클래스 3 문제 중에서 안 풀었던 문제가 있기에 풀어보았다. 백트래킹 문제 중에서 가장 유명하고 잘 알려진 문제인 N-Queen 문제이기에, 나는 당연히 이 문제를 솔루션을 보지 않고는 풀기 힘들 것이라고 생각되어서 이 문제를 유튜브 강의를 참고하여 해결하였다. 참고한 유튜브 강의는 아래 링크에 있다. 유튜브 강의에서 설명을 굉장히 잘 해놓았기 때문에 보고 글을 읽으면 더욱 이해가 잘 될 것이다. 파이썬으로 배..
[Python] 1069번 집으로 1069번: 집으로 (acmicpc.net) 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 22/09/01 이 문제는 참 창의적인 문제이다. 문제 풀면서 참 감탄한 문제이다. 발상이 굉장히 독특하긴 한데, 수많은 예제들을 보고 이를 쉽게 유추해낼 수 있어서 참 다행이었다. 만약 이 문제가 이렇게까지 예제 입력이 많이 주어지지 않았더라면 지금보다 난이도가 더 높게 매겨지지 않았을까 싶다. 문제 접근 방식: 처음에 살짝 그리디적인 방법으로 접근했다. 이후 이 방법을 뼈대로 하여 고쳐가며 문제를 해결..
[Python] 1270번 전쟁 - 땅따먹기 1270번: 전쟁 - 땅따먹기 (acmicpc.net) 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n

티스토리툴바