코테 (안함)43 [나만 볼 알고리즘] 최단 경로 문제 - 플로이드 워셜 최단 경로 문제 최단경로(Shortest Path)문제는 일상에서 매우 흔한 알고리즘 문제이다. 지도에서의 네비게이션 기능이나, 게임 상에서 유저의 길찾기 기능 등 다양한 분야에서 해당 문제를 마주칠 수 있다. 알고리즘 문제에서 최단 경로 문제는 주어진 그래프에서 특정 정점의 쌍에 대한 최단 경로를 구하는 것이 제일 흔한 형식이다. 최단 경로 문제와 관련된 알고리즘으로는 플로이드 알고리즘, 다익스트라 알고리즘, 벨만 알고리즘, A* 알고리즘 등이 있다. 플로이드 알고리즘 주어진 그래프에서 모든 정점의 쌍에 대한 최단 경로를 구해야 할 때 사용되는 알고리즘이 바로 플로이드(또는 Floyd-Warshall) 알고리즘이다. 모든 정점 간의 최단 경로를 한번에 구할 수 있다는 장점이 있다. 플로이드 알고리즘으로.. 2023. 7. 7. [나만 볼 알고리즘] 동적계획법 - LCS 예제 동적계획법? 반복 순회를 해야되는 문제를 해결하기 위해 우리는 재귀함수를 이용해 쉽게 접근 할 수 있다. 하지만 단순하고 무식한 브루트포스(완전탐색)의 방식은 지수적 시간복잡도를 갖는 경우가 흔히 있기에, 계산규모가 큰 문제에는 적합하지 않다. 재귀함수의 단점을 커버하고 강력한 해결능력을 보조하기 위해 선조개발자들은 동적계획법이라는 테크니션을 만들어내고 만다. 동적계획법은 재귀함수의 중복부분 문제를 해결하기 위해서 사용된다. 동적계획법을 공부할 때 꼭 한번씩은 접해본다는 LCS를 예시로 동적계획법을 경험해보기로 하자. LCS: Longest Common Subsequence - 최장공통부분서열 문제 Longest Common Substring이라고도 불리는데, 사실상 서열들의 공통된 부분 서열을 찾아내 .. 2023. 7. 5. 백준 골드티어 달성 별로 한게 없는거 같은데, 벌써 골드티어에 도달했다. 추천 문제 위주로 풀기만 했으며, 현재 그리디에 한해선 실버는 손 쉽게 풀고, 골드 문제는 대부분 스스로 풀 수 있는 수준이 되었다. 앞으로 dp 문제와 dfs / bfs 탐색 문제에도 심혈을 기울여야 할 것 같다. 문제를 많이 풀어보는 것 밖에 답이 없는 것 같다. 새로운 문제를 푸는 것 보단, 예전에 힘들게 풀었던 문제들을 쉽게 풀어 낼 수 있는지 복습을 많이 하려 노력하고 있다. 그리디 / dp / 탐색 각각 50문제 씩만 풀어도 골드1은 찍지 않을까 예상해본다.. 2022. 12. 9. 백준 11659 - 구간 합 구하기 4 import sys input = sys.stdin.readline n,m = map(int,input().split()) arr = list(map(int,input().split())) arr2 = [0]*n arr2[0] = arr[0] for _ in range(1,n): arr2[_] = arr[_]+arr2[_-1] for _ in range(m): i,j = map(int,input().split()) if i == 1: print(arr2[j-1]) else: print(arr2[j-1]-arr2[i-2]) # 간단한 누적합 문제 간단한 누적 합 문제이다. 2022. 12. 9. 2021 Dev-Matching: 웹 백엔드 개발자(상반기) - 행렬 테두리 회전하기 def solution(rows, columns, queries): graph = [[0]*columns for _ in range(rows)] cnt = 1 answer = [] for i in range(rows): for j in range(columns): graph[i][j] = cnt cnt +=1 for _ in queries: arr = [] prev_graph = [item[:] for item in graph] for i in range(_[0],_[2]+1): for j in range(_[1],_[3]+1): if j == _[1] and i != _[2]: graph[i-1][j-1] = prev_graph[i][j-1] continue if j == _[3] and i != _[.. 2022. 11. 26. 2021 Dev-Matching: 웹 백엔드 개발자(상반기) - 로또의 최고 순위와 최저 순위 def solution(lottos, win_nums): cnt = 0 answer = [0,0] zero = lottos.count(0) for i in lottos: if i in win_nums: cnt += 1 if cnt == 6: return [1,1] if cnt == 0 and zero == 0: return [6,6] if zero == 6: return [1,6] answer[0] = 6-cnt-zero+1 answer[1] = 6-cnt+1 return answer 2022. 11. 26. 이전 1 2 3 4 ··· 8 다음
