본문 바로가기

전체 글

 (263)
[이코테] 그리디 - 모험가 길드 python 난이도 : ●○○ | 풀이 시간 : 30분 | 시간 제한 : 1초 | 메모리 제한 : 128MB | 기출 : 핵심 유형 문제 한 마을에 모험가가 N명 있다. 모험가 길드에서는 모험가 N명의 공포도를 측정했는데, 공포도가 X인 모험가는 반드시 X명 이상으로 구성된 그룹에 참여해야 여행을 떠날 수 있다. 최대 몇 개의 모험가 그룹을 만들 수 있는지 구하라. 입력 조건 첫째 줄에 모험가의 수 N이 주어진다.(1
[최단 경로 알고리즘] Dijkstra, Floyd-Warshall algorithm 1. Dikstra algorithm 특정한 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 계산함 음의 간선이 없을 때 정상적으로 동작함 매 상황에서 가장 비용이 적은 노드를 선택하므로 그리디 알고리즘으로 분류됨 1.1 Dijkstra algorithm 동작 과정 출발 노드를 설정함 최단 거리 테이블을 초기화함 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택함 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신함 위 과정에서 3번과 4번을 반복함 1.2 Dijkstra algorithm 특징 그리디 알고리즘에 포함됨 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택하기 때문임 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음 한 단계당 하나의 ..
[백준] 1912 : 연속합 python https://data-marketing-bk.tistory.com/52 백준 - 1912번 - 연속합[파이썬] 1. 문제 출처 백준 - 1912번: 연속합 문제로 이동하기 우선 링크로 가서 문제를 보도록 하자. 2. 문제 설명 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 data-marketing-bk.tistory.com 위 포스트를 참고했는데 이전까지의 합이 그냥 i번째 숫자보다 작은 경우 이전의 기록들은 무의미하다는 문장이 큰 도움이 됐다. 현재값보다 연속된 수들의 누적합이 더 크다면 그 값을 쓰고, 현재값이 더 크다면 이전 값은 의미가 없으니 현재값으로 갱신을 한다. 현재값과 그 이전값들의 합을 비교하는 것이니 메모리를 추가로 사용할 필요도 없다. n..
[백준] 2156 : 포도주 시식 python 세 잔을 연속해서 마실 수 없기 때문에 (마시는 걸 O, 마시지 않는 걸 X라고 했을 때) OXO : dp[i-3]+dp[i-2]+arr[i] XOO : arr[i-1]+arr[i] 이 두 가지 경우를 생각했는데 마지막잔을 마시지 않아도 된다는 점을 간과해서 문제가 풀리지 않았다. OOX : dp[i-1] 인 경우도 구해서 세 가지 경우 중 최댓값인 걸 dp[i]에 저장하도록 해서 해결했다. import sys input = sys.stdin.readline n=int(input()) arr = [int(input()) for _ in range(n)] dp = [0]*n dp[0] = arr[0] if n>1: dp[1] = arr[0]+arr[1] if n>2: dp[2] = max(dp[1], ar..
[SWEA] 1206 : [S/W 문제해결 기본] 1일차 - View python https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com n을 입력받고 집의 높이들을 arr라는 리스트에 저장한다. arr[0], arr[1], arr[n-2], arr[n-1]은 0이기 때문에 arr[2]부..
[백준] 14002 : 가장 긴 증가하는 부분 수열 4 python n = int(input()) A = list(map(int,input().split())) # A에 저장된 각 값들까지의 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열 # A에 저장된 0번째 수까지의 가장 긴 증가부분수열의 길이는 1이므로 # 1로 초기화함 dp=[1]*n # A에 저장된 1번째값부터 자신의 앞에 있는 수들과 비교를 함 for i in range(1,n): for j in range(i): # 자신이 더 크다면 기존의 증가부분수열의 길이와 # 부분수열에 자기자신을 추가했을 때의 길이 중 더 긴 것으로 업데이트함 if A[i]>A[j]: dp[i] = max(dp[j]+1, dp[i]) # 가장 긴 증가부분수열의 길이를 저장함 order = max(dp) # 증가부분수열의 실제 값을..
[백준] 1932 : 정수 삼각형 python 첫번째행부터 자신의 위에서 나올 수 있는 최대값에 자신을 더하는 방식으로 문제를 풀어나갔다. 0번째열이라면 dp[i-1][j]+자기자신이 답이니 바로 저장하고 열값이 0보다 크다면 dp[i-1][j-1]과 dp[i-1][j]중 더 큰 값에 자기자신을 더한 걸 dp테이블에 저장하도록 했다. n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] dp = [[0]*n for _ in range(n)] dp[0][0] = arr[0][0] # 1부터 n-1행까지 for i in range(1,n): # 0 부터 i까지 for j in range(i+1): # 0번째 열이면 if j ==0: dp[i][j]=dp[i-1][j]+arr[..
[백준] 12865 : 평범한 배낭 python [물건의 개수]x[가방에 넣을 수 있는 최대 무게] 크기의 dp행렬을 생성하고 0으로 초기화한다. 물건을 하나씩 보면서, 현재 물건을 넣을 수 없다면 기존의 가치값을 그대로 가져오고 넣을 수 있다면 기존의 가치와 현재 물건을 넣을 수 있는 시점에서의 가치 + 현재 물건의 가치 중 큰 값을 저장한다. n,k = map(int,input().split()) item = [[0]*2 for _ in range(n+1)] for i in range(1,n+1): item[i] = list(map(int,input().split())) dp = [[0]*(k+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,k+1): weight = item[i][..

티스토리툴바