[Python/파이썬] 백준 16928 - 뱀과 사다리 게임

문제 설명 입출력 예제 풀이 코드 10 x 10 크기의 보드판에서 진행되는 게임이라고 했지만 상하좌우로 움직이는게 아닌, 한 방향으로만 움직일 수 있다. 그렇기 대문에 2차원 배열이 아닌 1차원 배열로 나열해 풀 수 있다. 그리고 주어진 사다리, 뱀의 위치를 dict(딕셔너리) 타입으로 받아 주사위를 던져 도착한곳이 사다리, 뱀 위치(key)면 value로 이동시킨다. 정답 코드 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) # 사다리 수, 뱀 수 board = [0] * 101 visited = [False] * 101 ladder = dict() for _ in ran..

• format_list_bulleted DFS,BFS
• · 2023. 6. 26.
• textsms

[Python/파이썬] 백준 1436 - 영화감독 숌

문제 설명 입출력 예제 풀이 코드 이 문제는 완전탐색 탐색 문제로 완전 탐색 답게 무식하게 숫자를 하나씩 더해가면서 해당 숫자가 몇번째 종말의 수인지 찾아야 한다. 그래도 반복문을 덜 타게 규칙이 있지 않을까?했지만 그런 규칙을 찾긴 힘들었다 다만 반복문을 덜타도록 탐색하는 수 num을 1부터가 아닌 종말의 수인 "666"부터 시작하도록 하였다. 정답 코드 import sys input = sys.stdin.readline n = int(input()) cnt = 0 # 몇 번째 종말의 수인지 카운팅 num = 666 while True: if "666" in str(num): # 666이 num에 포함되어 있다면 cnt = cnt + 1 if cnt == n: # 구하자고 하는 n번째 종말의 수와 같다..

• format_list_bulleted 완전탐색 (Bruteforce)
• · 2023. 6. 23.
• textsms

[Python/파이썬] 백준 11659 - 구간 합 구하기 4

문제 설명 입출력 예제 풀이 코드 이 문제는 현대오토에버 코딩문제에 나온 문제라고 한다. 사실상 실버난이도인 만큼 접근만 한다면 쉽게 풀 수 있는 문제다. 제한 사항을 보면 N, M 입력값의 제한 범위가 100,000이다. 이중 반복문으로 풀면 쉽게 풀수는 있겠지만 2중 반복문은 O(n^2) 시간 복잡도를 갖기 때문에 시간초과가 발생한다. 따라서 O(N)이나 O(logN)의 시간 복잡도로 풀어야 하는데 문제에서도 이미 정답을 말해줬다."구간합" 문제를 푸는 방법은 다음과 같다. 주어진 값들의 누적합을 갖는 리스트를 만든다. PrefixSum 여기서 PrefixSum에 0을 넣어 놓은 이유는 주어지는 구간 i가 1부터 시작하기 때문에 인덱싱에러를 방지하기 위해서이다. 각 수들의 합을 갖는 변수 total을..

• format_list_bulleted 구간합 (Prefix)
• · 2023. 6. 22.
• textsms

[Python/파이썬] 백준 1065 - 한수

문제 설명 입출력 예제 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 코드 처음에는 문제 설명을 이해하는게 어려울 것이다. (문제 설명이 좀 많이 아쉽;) 왜 110을 입력했을 때 결과가 99가 나오는지 이해할 수가 없었다. 하지만 왜 그러한 결과가 나오는지 이해만 한다면 문제는 실버난이도 답게 쉽게 풀 수 있을 것이다. 일단 "한수"라는 것은 각 자리수의 차이가 일정한 수이다. 111 이라는 수가 주어진다면 이 수는 각 자리수 차이가 0이므로 ㅠ이다. 그렇다면 5는 어떨까? 자리수를 비교할 대상이 없지만..

• format_list_bulleted 완전탐색 (Bruteforce)
• · 2023. 6. 17.
• textsms

[Python/파이썬] 백준 9205 - 맥주 마시면서 걸어가기

문제 설명 입출력 예제 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 코드 이 문제의 핵심 내용만 정리하면 다음과 같다. 현재 20병의 맥주를 가지고 있다. 50미터에 한 번씩 맥주 한 병을 마신다. (즉, 한번에 1000m를 갈 수 있다.) 편의점에 갈 때마다 새로운 맥주를 20병 얻을 수 있고 나선 직후 50미터에 한 번씩 맥주 한 병을 마신다. (즉, 편의점 위치 부터 페스티벌 까지 이동을 시작한다.) 시작위치에서 페스티벌까지 (1000m = 맥주 20개 * 50m) 갈수 있다면 "happy..

• format_list_bulleted DFS,BFS
• · 2023. 6. 16.
• textsms

[Python/파이썬] 백준 1325 - 효율적인 해킹

문제 설명 풀이 코드 가장 핵심은 "A가 B를 신뢰한다."는 즉, "B는 A의 부모 노드"이라는 점이다. 아래 그림은 위의 "예제 입력 1"에 해당하는 값대로 노드를 표현한 그림이다. 만약 1번 노드에서 시작한다면 3, 4, 5 총 3개의 노드를 탐색하는 것이고 3번 노드에서 시작한다면 4, 5를 탐색하는 것이 된다. 탐색 노드 1번 2번 3번 4번 5번 탐색 수 3 3 2 0 0 먼저 입력값을 받아, 노드 연관관계 리스트를 만든다. 각 노드마다 bfs 탐색을 시작해 해당 노드에서 시작하여 총 몇개의 노드를 탐색하는지 카운팅하여 리스트에 저장한다. 가장 많은 노드를 탐색한 노드를 출력한다. 정답 코드 from collections import deque import sys input = sys.stdin..

• format_list_bulleted DFS,BFS
• · 2023. 6. 14.
• textsms