본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 21317번 징검다리 건너기 https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 22/10/03 개인적으로 굉장히 난이도에 비해 굉장히 어렵게 느껴졌던 문제로, 다른 방법으로 풀었다면 조금 쉽게 해결하지 않았을까 하는 아쉬움이 남는 문제이기도 하다. 문제 접근 방식: 백트래킹으로도 접근할 수 있는 문제이긴 하지만, 나의 경우는 DP로 이 문제를 접근했었다. 굉장히 많이 틀렸기 때문에 틀린 과정을 상세하게 설명하고자 한다. 맨 처음 풀이는 그냥 단순하게 DP[N] = N번째까지 도착했을 때, 산삼을 얻기 위해 필요한 영재의 에너지 최솟값이라고 정의를 했었다. 그리고 가장 큰 점프는 한 번만 할 수 있으므..
[Python] 11057번 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 22/10/03 전형적인 DP문제로, 나는 이차원 배열을 사용하여 문제를 해결하였다. 문제 접근 방식: 나는 DP[i][j]의 정의를 다음과 같이 정의했다. DP[i][j] = i자리 숫자일 때, j로 끝나는 오르막 수의 개수 이와 같이 정의를 하면, j가 0일 때, 1일 때, ..., 9일 때 모두 비슷한 점화식을 가진다. 오르막 수의 정의 상 이전 숫자보다 ..
[Python] 10994번 별 찍기 - 19 https://www.acmicpc.net/problem/10994 10994번: 별 찍기 - 19 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 22/10/02 흔하디 흔한 별 찍기 문제로, 재귀로도 구현할 수 있지만 그냥 규칙을 찾아서 이중 for문으로 구현하였다. 문제 접근 방식: 먼저, 나는 위와 아래의 모습이 가운데 선을 기준으로 대칭을 이루고 있다는 사실을 발견했다. 때문에 위의 절반까지만 출력하고, 아래 절반은 위의 절반의 코드를 그대로 인덱스만 거꾸로 한 채 출력하면 될 것이라고 생각했다. 칸 수를 보면, 1을 입력받을 때 위의 절반의 칸 수가 1, 2를 입력받을 때는 3, 3을 입력받을 때는 5이므로, 가로를 출력하는 i가 2*n - 1이 된다는 것을 알..
[Python] 20040번 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 22/10/01 사이클을 만들 수 있는지의 여부와, 만들 수 있다면 처음 사이클이 만들어졌을 때의 차례를 출력하는 문제로, 유니온-파인드 알고리즘을 활용하여 쉽게 풀 수 있는 문제이다. 만약 유니온-파인드 함수나 분리집합 자료 구조에 관해서 잘 모르는 상황이라면 공부를 먼저 하고 이 글을 보면 도움이 될 것이다. 문제 접근 방식: 이 문제에서 사이클이 만들어 진다는 뜻은, 이미 같은 선분으로..
[Python] 7569번 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 22/09/30 이 문제는 7576번 토마토와 거의 유사한 문제로, 이 문제에서 3차원으로 바꾸기만 하면 되는 문제이다. https://lighter.tistory.com/34 [Python] 7576번 토마토 7576번: 토마토 (acmicpc.net) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자..
[Python] 4821번 페이지 세기 https://www.acmicpc.net/problem/4821 4821번: 페이지 세기 워드, 한글, 메모장과 같은 워드 프로세서에서 인쇄를 할 때, 페이지 범위를 직접 입력하여 지정할 수 있다. 예를 들면, 다음과 같이 입력할 수 있다. 10-15,25-28,8-4,13-20,9,8-8 사용자는 위처럼 인쇄 www.acmicpc.net 22/09/29 문자열 파싱 문제로, 난이도에 비해서 의외로 실수할 만한 부분이 곳곳에 분포해있었다. 문제 접근 방식: 이 문제를 2번 틀렸었는데, 문제에서 주어진 "만약, low > high인 경우에는 이 범위는 인쇄하지 않는다."라는 조건을 잘못 해석하여 이 범위를 영구적으로, 혹은 일시적으로 빼도록 구현을 해서 틀렸었다. 알고 보니, 그냥 저 경우일 때는 무시를..
[Python] 25640번 MBTI https://www.acmicpc.net/problem/25640 25640번: MBTI 진호는 요즘 유행하는 심리 검사인 MBTI에 관심이 많다. MBTI는 아래와 같이 네 가지 척도로 사람들의 성격을 구분해서, 총 $16$가지의 유형중에서 자신의 유형을 찾을 수 있는 심리 검사이다. 내향( www.acmicpc.net 22/09/29 단순 문자열 비교 문제이다. 문제 접근 방식: 먼저 진호의 MBTI를 입력받고, for문을 사용하여 진호의 MBTI랑 다른 사람의 MBTI와 같은지 비교한다. 같으면 total변수를 +1 시켜준다. 이후 total변수를 출력하였다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다. 더보기 # 25640번 MBTI # 구현 j..
[Python] 11277번 2-SAT - 1 / 11278번 2-SAT - 2 https://www.acmicpc.net/problem/11277 11277번: 2-SAT - 1 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 20)과 절의 개수 M (1 ≤ M ≤ 100)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 양수인 www.acmicpc.net https://www.acmicpc.net/problem/11278 11278번: 2-SAT - 2 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 20)과 절의 개수 M (1 ≤ M ≤ 100)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 양수인 ..

티스토리툴바