알고리즘72 [BOJ] 1351. 무한 수열 문제https://www.acmicpc.net/problem/1351이것도 처음에 뭔 말이지..? 싶었다현재 인덱스를 P와 Q로 나눈 것의 "내림값" 인덱스의 합A_0 = 1 주요 아이디어전형적인 DP 문제탑다운 방식으로 풀어보자! 코드 구현 (Python 3)더보기 from collections import defaultdict# 수열 n번째 반환def dp(n): # 저장되어 있는 값이면 if data[n] != 0: return data[n] data[n] = dp(n // p) + dp(n // q) return data[n]n, p, q = map(int, input().split())data = defaultdict(int)data[0] = 1 # 초기값 작.. 2024. 6. 25. [BOJ] 1541. 잃어버린 괄호 문제https://www.acmicpc.net/problem/1541괄호를 적절히 쳐서 주어진 식의 값을 최소로 만들기‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자55-50+40# 55-(50+40) = -35 주요 아이디어'-' 기준으로 식을 split하기'+' 연산자 처리 후 split된 단위로 '-' 처리ex. 70+20-30-40list[0] = 70+20 = 90list[1] = 30list[2] = 40answer = 90 - 30 - 40 = 20 코드 구현 (Python 3)더보기 op_str = input()num_list = op_str.split('-')for idx, num in enumerate(num_list): num_tota.. 2024. 6. 25. [BOJ] 7576. 토마토 문제https://www.acmicpc.net/problem/7576 M * N 칸으로 이뤄진 상자에 토마토가 존재정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸 토마토가 모두 익을 때까지의 최소 날짜를 출력 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력 토마토가 모두 익지는 못하는 상황이면 -1을 출력 6 4 # M*N0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 1 주요 아이디어전형적인 BFS 문제익은 토마토를 시작 좌표로 삼고 큐에 모조리 넣어놓자bfs를 진행하면서 box에다 며칠차에 해당 칸이 익는지를 적지bfs 밖의 반복문에서는 최소 일수를 구하고, 만약 최종적으로 안 익은 게 있을 경우 -1로 반환0일.. 2024. 6. 25. [BOJ] 16401. 과자 나눠주기 문제https://www.acmicpc.net/problem/16401M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다. 주요 아이디어과자 최대 길이를 이분탐색 target으로 두기target mid 값을 기준으로 나눠줄 수 있는 개수 구하기개수 모자랄 경우 최대 길이 줄이기개수 많을 경우 최대 길이 늘리기 코드 구현 (Python 3)더보기 """과자 최대 길이를 이분탐색 target으로 두기"""m, n = map(in.. 2024. 6. 25. [BOJ] 18870. 좌표 압축 문제https://www.acmicpc.net/problem/18870처음에는 문제가 잘 이해가 안갔다문제 예시를 보면 이해가 잘됨2 4 -10 4 -9# 출력 : 2 3 0 3 1좌표를 오름차순 정렬한 후 인덱스를 반환해주면 된다! 주요 아이디어위에서 했던 문제 설명 그대로좌표를 오름차순 정렬한 후 인덱스를 반환 코드 구현 (Python 3)더보기 import sysn = int(input())coor = list(map(int,sys.stdin.readline().strip().split()))sorted_coor = sorted(list(set(coor)))for c in coor: print(sorted_coor.index(c), end=' ') 시간 초과... 실패 원인list.ind.. 2024. 6. 25. [BOJ] 16954. 움직이는 미로 탈출 문제https://www.acmicpc.net/problem/16954시작 지점 -> 가장 왼쪽 아랫칸 | 목표 지점 -> 가장 오른쪽 윗칸캐릭터는 상하좌우 & 대각선 이동 가능 / 현재 위치 서있기벽이 움직여? - 1초마다 모든 벽이 아래 있는 행으로 한 칸씩 내려감 (가장 밑에서 사라짐)최종적으로 욱제 캐릭터가 목표 지점으로 이동할 수 있는지 없는지 여부 확인 주요 아이디어그래프 입력 받기while문 반복하면서 그래프 내의 벽 이동 (이동 함수 별도로 만들기)bfs 솔루션 실행하면서 목적지까지 도달 가능한지 확인하기캐릭터가 먼저 이동 -> 벽이 이동벽이 캐릭터와 닿으면 바로 0 반환최종적으로 도달 가능하면 1 반환하기 코드 구현 (Python 3)더보기 from collections import.. 2024. 6. 25. 이전 1 2 3 4 5 6 ··· 12 다음
