본문 바로가기

Algorithm

 (22)
[이코테] 그리디 - 곱하기 혹은 더하기 python 난이도 ●○○ | 풀이 시간 : 30분 | 시간 제한 : 1초 | 메모리 제한 : 128MB | 기출 : Facebook 인터뷰 문제 각 자리가 숫자(0~9)로만 이루어진 문자열 S가 주어진다. 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 만들 수 있는 가장 큰 수를 구하여라. 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다. 입력조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어진다.(1
[이코테] 그리디 - 모험가 길드 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 특징 그리디 알고리즘에 포함됨 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택하기 때문임 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음 한 단계당 하나의 ..
[다이나믹 프로그래밍] 피보나치 수열, 개미 전사, 1로 만들기, 효율적인 화폐 구성, 금광, 병사 배치하기 python 다이나믹 프로그래밍(Dynamic Programming, 동적 계획법) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 계산한 결과를 메모리에 저장해(Memoization) 다시 계산하는 일이 없게 함 구현 방식은 일반적으로 탑다운방식과 보텀업방식이 있음 탑다운방식-큰 문제를 잘게 쪼개어 푸는 것 보텀업방식-작은 문제들을 해결해 큰 문제를 해결하는 것 다이나믹 프로그래밍의 조건 주어진 문제가 다음의 조건들을 만족할 때 다이나믹 프로그래밍을 사용할 수 있음 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나누고 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복..
[구현] 상하좌우, 시각, 왕실의 나이트, 문자열 재정렬 python 상하좌우 n = int(input()) x,y = 1,1 dx = [-1,1,0,0] dy = [0,0,-1,1] move_types = ['U','D','L','R'] plans = input().split() for plan in plans: for i in range(len(move_types)): if plan == move_types[i]: nx = x+dx[i] ny = y+dy[i] if nxn or nyn: continue x,y = nx,ny print(x,y) 시각 문제 설명을 듣고 직접 짠 코드 n = int(input()) cnt=0 for h in range(n+1): for m in range(60): for s in range(60): if(h%10==3)or(m%10==3 o..
[그리디 알고리즘] 1이 될 때까지 python k로 나눌 수 있는 만큼 나누고 나머지는 -1을 반복해서 수행하는 방식으로 해결하면 된다. n,k = map(int,input().split()) result = 0 while True: # n보다 작거나 같은 수 중 k로 나누어떨어지는 가장 큰 수 target = (n//k)*k # -1을 수행해야 하는 횟수를 계산한 것 result += (n-target) n = target # n이 k로 나눠떨어지지 않는다면 # -1을 수행해야 하니 반복문 탈출 if n

티스토리툴바