생각하는 아져씨

4485번: 녹색 옷 입은 애가 젤다지?https://www.acmicpc.net/problem/4485문제 정의주인공 링크는 현재 도둑루피가 가득한 N*N 크기의 동굴안에 젤 안쪽에 있다. ([0][0]에 위치)동굴의 반대편으로 가야하는데, 도둑루피를 지나면 도둑루피의 크기만큼 소지금을 잃게된다.한번에 상하좌우 1칸씩 이동할 수 있다.이 때 잃는 금액을 최소로 하여 동굴을 이동하려고 한다. 링크가 잃을 수 밖에 없는 최소 금액을 구하면 된다. 접근 방법‘잃을 수 밖에 없는 최소 금액’ = 동굴의 마지막 [N-1][N-1] 로 가는데 드는 비용을 최소화하는 경로로 가야한다.따라서 최단경로, 다익스트라로 풀 수 있다.다익스트라는 노드와 간선의 정보가 있어야 하는데, 이 문제에서는 다음과 같다.노드: 도둑루..

다익스트라(Dijkstra)다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 특정한 하나의 정점 → 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선은 포함할 수 없다. (현실세계에 사용하기 매우 적합한 알고리즘 중 하나이다.) 👉 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는?최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. 작은 문제가 큰 문제의 부분집합에 속해있다. 👉 그리디 알고리즘의 일종인 이유는?매번 ‘가장 비용이 적은 노드’를 선택하기 때문이다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 다음의 그래프에서 노드 1에서 2,3,4 ..

개요누적합누적합 예제 문제 살펴보기2차원 배열에서 누적합구현간단한 구현 예제구현 시 고려해야 할 메모리 제약 사항 (Python)채점 환경 (Python)문제를 푸는 방법참조 개요오늘은 알고리즘의 가장 첫번째인 누적합과 구현에 대해서 공부한다. 이 글은 세상을 널리 이롭게 하는 돌, 큰 돌 님의 강의를 기반으로 정리하고 개인적으로 공부한 것을 덧붙여 정리하였음을 먼저 밝힌다. 공부를 할 때 마다 새로운 지식을 계속해서 정리할 예정이다.누적합누적합이란 요소들의 누적한 합을 의미한다.어떤 배열을 기반으로 앞에서 부터 요소들의 누적한 합을 저장해서 새로운 배열을 만들고 이를 활용하는 방식이다. 누적합의 종류에는prefix sum: 앞에서부터 더하는 것 → 코딩테스트에 나오는 것suffix sum: 뒤에서부터 ..

개요시간복잡도시간 복잡도란?빅오표기법(Big-O notation) 빅오표기법빅오 표기법 복잡도 비교상수시간 시간복잡도는 O(1)문제로 연습하는 시간복잡도시간복잡도의 존재 이유는 효율적인 코드의 척도!자료구조의 시간복잡도공간복잡도공간복잡도공간복잡도 계산공간복잡도를 참고한 문제 풀이 방법참조 개요알고리즘을 해결할 때는 복잡도가 굉장히 중요하다. 복잡도는 시간복잡도와 공간복잡도로 나뉘어지는데 하나씩 공부해보도록 하자. 이 글은 세상을 널리 이롭게 하는 돌, 큰 돌 님의 강의를 기반으로 정리하고 개인적으로 공부한 것을 덧붙여 정리하였음을 먼저 밝힌다.시간복잡도시간 복잡도란?입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요 로직의 반복횟수를 중점으로 측정된다. 👉 시간복잡도는 시간을 재야할까?아..