토피넛라떼조아

오늘은 구간합을 구할 때 효율적인 세그먼트 트리에 대해 알아보겠다. 1차원 배열로 표현이 가능해서 생각보다 간단하게 구현할 수 있고, 단계별로 이해하면 크게 어렵지 않게 이해할 수 있다. 모든 알고리즘이나 자료구조는 코드를 암기하는 것 보다 구조와 동작을 이해하는 것이 더 중요하다. 세그먼트 트리를 한 단계씩 파헤쳐보자. 세그먼트 트리 (Segment Tree)? 일단 세그먼트 트리를 먼저 알아보자.세그먼트 트리는 특정 구간의 합, 곱과 같은 연산을 포함하여 최댓값, 최솟값을 구하는 용도로 사용하는 자료구조이다. 비슷한 자료구조로 구간 합과 비슷하지만 시간복잡도도 우수하고 업데이트에도 용이하다. 세그먼트 트리를 이해하기 쉽게 몇 가지 특징을 먼저 알아보자. 그 다음 세그먼트 트리로 구간합을 구해보자.특징..

지난 포스팅을 통해 DFS를 알아보았으니 형제 탐색법인 BFS를 알아보겠다.BFS 또한 DFS처럼 트리나 그래프를 순회하는 기본 방법 중 하나이다. BFS (Breadth First Search)? BFS는 너비 우선 탐색이다. 시작 노드부터 가까운 노드들을 모두 살펴본 뒤 그 다음 노드들을 탐색한다. 단순하게 생각해서 파원에서 파장이 퍼져나가는 모양을 생각하면 얼추 비슷하다. 특징과 장단점- 연결된 모든 노드를 탐색할 수 있다.- 방문 노드를 기억하고 재방문하지 않는다.- DFS가 스택을 활용하는 것과 다르게 보통 큐를 활용한다.- 최단경로 탐색에 적절하다. 해를 찾고나면 다음 해는 찾을 필요가 없기 때문이다.- 논리 구조가 간단하다.- 해가 깊은 곳에 있으면 탐색에 오랜 시간이 걸릴 수 있다.  BF..

알고리즘 풀이를 놓은 지 시간이 좀 흐르니까 자신만만하던 문제들도 쉽게 풀지 못하는 지경에 이르렀다. 아무래도 정리를 하면서 이해를 하는 시간을 한 번 더 가져야 할 것 같아서 문제 풀이에 기본이 되는 알고리즘들을 다시 코드를 작성하면서 복기해보려고 한다.  자 가장 쉬운 그래프 탐색법인 DFS부터 알아보자수많은 트리, 그래프를 순회하는 방법 중 기본이 되는 알고리즘이다. DFS (Depth First Search)? 이름부터 깊이를 우선하여 서치한다는 의미를 담고 있다. 시작부터 끝까지 '깊이'를 우선하여 탐색한다. 처음에는 깊이를 우선한다는 게 이해가 잘 되지 않을 수 있다. 쉽게 이해하기 위해 미로를 탐험한다고 가정해보자. 무수히 많은 갈림길이 존재할 것이다. 이런 미로를 모두 정복하기 위해 한 방..

에라토스테네스의 체 수학에서 소수를 찾는 방법론 중 하나입니다. 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 자기 자신을 제외한 2의 배수를 모두 지운다. 제외되지 않은 3은 소수이다. 자기 자신을 제외한 3의 배수를 모두 지운다. 제외되지 않은 5는 소수이다. 자기 자신을 제외한 5의 배수를 모두 지운다. 제외되지 않은 7은 소수이다. 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 만약 120까지 수 중에서 소수를 구하고 싶다면, 11^2 > 120 이므로 11보다 작은 수들의 배수들만 지워도 소수를 구할 수 있습니다. Python 코드 소수 리스트 구하기 에라토스테네스의 체를 이용하여 120이하의 소수 리스트를 구해보겠습니..

유클리드 호제법 (Euclidean algorithm) 은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나입니다. 최대공약수 (Greatest Common Divisor) : 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값을 의미합니다. 공식 만약 i > j 일 경우, i % j == 0이면 i와 j의 최대공약수는 j이다. 그렇지 않다면, i와 j의 최대 공약수는 j와 i % j의 최대공약수와 같다. (i % j != 0) 예를 들어, 10과 5의 최대공약수: 10%5 = 0 이므로 5가 최대공약수입니다. 10과 8의 최대공약수: 10%8 = 2 이며, 8 % 2 = 0 이므로 2가 최대공약수 입니다. 더 큰 수인 832와 1088의 경우에도 - 1088 % 832 = 256 - 89..

Spanning Tree 스패닝 트리란 그래프 내 모든 정점을 포함하는 트리입니다. 또한, 사이클을 포함하면 안된다는 특징이 있습니다. MST(Minimum Spanning Tree) 최소 스패닝 트리(최소 신장 트리)는 스패닝 트리 중 사용된 간선의 가중치가 최소인 트리를 뜻합니다. MST 특징 N개의 정점에 대해 N-1개의 간선이 존재합니다. 스패닝 트리이므로 사이클을 포함해서는 안됩니다. 간선 가중치의 합이 최소여야합니다. MST 구현 방법 1. Kruskal 알고리즘 Greedy method를 활용하여 구현합니다. 간선을 가중치 기준으로 오름차순 정렬합니다. 사이클을 포함하지 않는 경우 MST 구성 간선으로 포함시킵니다. N개의 정점에 대해 N-1개의 간선을 포함시킬 때까지 반복합니다. 💻 Kru..

문제 출처 : https://www.acmicpc.net/problem/1325

문제 출처 : https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 🔥 작성 코드 def sol(rsi, rsj, bsi, bsj, cnt): global result # 최소값이 아니라면 종료 if result 10: return # 4방향으로 기울이기 for d in range(4): flag = 0 rni = rsi + di[d] rnj = rsj + dj[d] bni = bsi + di[d] ..

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWMeRLz6kC0DFAXd&categoryId=AWMeRLz6kC0DFAXd&categoryType=CODE&problemTitle=%EC%A0%95%EC%8B%9D%EC%9D%B4&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🔥 작성코드 # 한 자리를 바꾼 2진수와 3진수 값 x, y def check(x, y)..

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=%ED%99%88+%EB%B0%A9%EB%B2%94&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🔥 작성코드 # bfs def sol(si, sj, k): global result q..