본문 바로가기

Python69

[Algorithm] 백준 1018 체스판 다시 칠하기 | 파이썬 ※ 1018 체스판 다시 칠하기https://www.acmicpc.net/problem/1018 문제 해결 TIP입력으로 주어진 맵(그래프)에서 8x8 크기로 자른 후, 가능한 두 가지 맵(그래프)과 비교하는 문제이다. 가능한 두 가지 그래프는 다음과 같다. 두 그래프와 동시에 비교해가며, 첫번째 그림과 다를 경우 count_1에 1씩 추가, 두번째 그림과 다를 경우 count_2에 1씩을 추가해준다. 이후 최값을 출력한다. 전체 코드N, M = map(int,input().split())graph = []answer = []for i in range(N): graph.append(list(map(str,input())))for i in range(N-7): for j in range(M-7).. 2024. 8. 2.
[Algorithm] 백준 7562 나이트의 이동 | 파이썬 BFS ※ 7562 나이트의 이동https://www.acmicpc.net/problem/7562 문제 해결 TIPbfs로 간단하게 풀 수 있다. 기존의 문제들은 상하좌우로 움직일 수 있지만 이 문제는 대각선으로 8방향 이동할 수 있다. 이에 맞춰서 dx, dy를 재설정해준다. 이후 최단거리 문제와 비슷하게 1씩 추가해가며 이동량을 그래프에 저장한다. 목표 좌표에 도달하면 이동량을 출력한다. 전체 코드from collections import dequen = int(input())for i in range(n): l = int(input()) graph = [[0]*l for _ in range(l)] i, j = map(int,input().split()) r, c = map(int,in.. 2024. 7. 22.
[Algorithm] 백준 1926 그림 | 파이썬 BFS ※ 1926 그림https://www.acmicpc.net/problem/1926 문제 해결 TIPbfs로 간단하게 풀 수 있다. 유기농 배추 문제와 비슷하다. 전체 코드from collections import dequegraph = []n, m = map(int,input().split())for i in range(n): graph.append(list(map(int,input().split())))#graph = [[1, 1, 0, 1, 1], [0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [1, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1]]dx = [-1,1,0,0]dy = [0,0,-1,1]def bfs(x,y): graph[x][.. 2024. 7. 16.
[Algorithm] 백준 1912 연속합 | 파이썬 (DP, Dynamic Programming) ※ 1912 연속합https://www.acmicpc.net/problem/1912 문제 해결 TIP현재값이 큰지, 이전 dp값과 현재값을 더한 값이 큰지 비교해야 한다. dp의 상태는 다음과 같이 변화한다. 최종 dp의 max값을 출력하면 된다.  전체 코드 n = int(input())number = list(map(int,input().split()))#number = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]dp = [-10000]*(n+1)dp[0] = number[0]for i in range(1,len(number)): dp[i] = max(dp[i-1]+number[i],number[i])print(max(dp)) 2024. 7. 10.
[Algorithm] 백준 18353, 이코테 병사 배치하기, 최장 증가 부분 수열 | 파이썬 (DP, Dynamic Programming) ※ 18353 병사 배치하기https://www.acmicpc.net/problem/18353 문제 해결 TIP최장 증가 부분 수열이란?예를 들어 다음 수열이 주어졌다고 하자.3 5 7 9 2 1 4 8위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.3 7 9 1 4 8 (5, 2 제거)7 9 1 8 (3, 5, 2, 4 제거)3 5 7 8 (9, 2, 1, 4 제거)1 4 8 (3, 5, 7, 9, 2 제거)위와 같이 일부, 혹은 전체가 오름차순인 수열을 '증가 부분 수열'이라고 한다. 그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다. 즉, 위의 수열의 집합에선 부분수열 3 5 7 8이 LIS이다. O(N^2) 알고리즘으로 구현할 수 있다. 새로운.. 2024. 7. 7.
[Algorithm] 프로그래머스 정수 삼각형 | 파이썬 (DP, Dynamic Programming) ※ 정수 삼각형https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 해결 TIP우선 예제 입력에 대해 30이 어떻게 나왔는지 파악해보자. 맨 위인 7에서 부터 밑으로 내려가며 합해준다. 두 번째 줄은 가운데가 없고 양끝만 존재하므로 10, 15가 된다. 세 번째 줄부터는 바로 위(두 번째 줄)에서 얻을 수 있는 숫자가 2가지(왼쪽 10, 오른쪽 15) 경우의 수인 가운데가 존재한다. 이때, 더 큰 숫자인 16으로 교체가 된다. 이를 반복하여 알 수.. 2024. 7. 6.
[Algorithm] 이코테 금광 | 파이썬 (DP, Dynamic Programming) [문제]n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.만약 다음과 같이 3 x 4 크기의 금광이 존재한다고 가정합시다.가장 왼쪽 위의 위치를 (1, 1), 가장 오른쪽 아래의 위치를 (n, m)이라고 할 때, 위 예시에서는 (2, 1) → (3, 2) → (3, 3) → (3, 4)의 위치로 이동하면 총 19만큼의 금을 .. 2024. 7. 6.
[Algorithm] 프로그래머스 멀리 뛰기 | 파이썬 (DP, Dynamic Programming) ※ 멀리 뛰기https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 해결 TIPn이 1일 때부터 생각해보자. dp[1] = 1, 2라면 1씩 2번, 2씩 1번 총 2이다. dp[3]은 (1,1,1),(2,1),(1,2) 3이다. dp[4] = 5, dp[5] = 8이므로 피보나치 수열이 떠오른다. 전체 코드def solution(n): if n == 1: return 1 else: dp = [0] * (n+1) .. 2024. 7. 5.
[Algorithm] 이코테 개미 전사 | 파이썬 (DP, Dynamic Programming) [문제]개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.{1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 .. 2024. 7. 3.

티스토리툴바