728x90 알고리즘/개념4 [알고리즘개념]구간합 11659. 구간 합 구하기 4 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWr.. 2023. 6. 15. [알고리즘개념]힙 뉴진스의 히트곡 제목에도 들어갈 정도로 최근 트렌드로 급부상하고 있는 힙(Heap)은 자료구조의 일종으로 완전 이진 트리를 통해 우선순위 큐를 구현한다. 먼저 큐(Queue)는 자료가 들어온(push) 순서대로 나가는(pop) 자료구조이다. 이를 코드를 통해 보면 다음과 같다. queue = [] for i in range(5): queue.append(i) print(queue) # [0, 1, 2, 3, 4] for i in range(5): print(queue.pop(0)) ''' 0 1 2 3 4 ''' 0부터 4까지 순서대로 입력되고 0부터 4까지 순서대로 나가는 선입선출(FIFO;First-in First-out) 구조이다. 우선순위 큐(Priority Queue)는 큐와 비슷하지만, 들어온.. 2023. 2. 8. [알고리즘개념]DFS/BFS와 인접행렬/인접리스트 graph는 정점(vertex)과 간선(edge)으로 이루어진 하나의 자료구조이다. 이 그래프를 탐색할 때는 해당 정점에 연결된 정점을 우선적으로 차수를 늘려가며 탐색하는 깊이 우선 탐색(DFS; Depth Firsh Search)과 해당 차수에 있는 모든 정점을 탐색하고 다음 차수로 넘어가는 너비 우선 탐색(BFS; Breadth First Search)을 사용할 수 있다. 위의 그림에서 DFS는 0에서 이어진 1로, 1에서 이어진 3으로 이동했다가 더이상 이어진 정점이 없으므로 상위 차수로 이동해 1에서 이어진 또다른 정점인 4로 이동한다. BFS는 반대로 0에서 이어진 1로 이동했다가 같은 차수의 또다른 정점인 2로 이동한 후 다음 차수의 첫번째 정점인 3으로 넘어간다. 일반적으로 DFS는 LIFO.. 2023. 1. 19. [알고리즘개념]Big O 알고리즘 문제를 풀 때 제한시간, 제한용량이 있기 때문에 이 범위 내에서 문제를 해결하기 위해서는 내가 짜는 코드의 시간복잡도(소모하는 시간)나 공간복잡도(소모하는 용량)가 기준을 충족하는지 파악해야 할 필요가 있다. 이를 나타내는 방식으로 Big O 표기법을 주로 사용한다. 알고리즘 문제는 주로 데이터를 탐색해서 정답을 찾아내는데, 이 탐색하는 과정은 데이터의 수가 많아질 수록 길어지고 데이터 탐색 방식이 어떤것인지에 따라 효율이 달라진다. for문을 통해 리스트를 탐색할 때 리스트의 첫 항부터 마지막 항까지 전부 탐색하는 것과 반씩 쪼개어 가며 이분탐색하는 것은 리스트의 길어질 수록 그 연산에 걸리는 시간 차이가 명확히 드러난다. 가령 길이가 N인 리스트를 M번 반복해서 탐색해야 한다면 일반적으로는 .. 2023. 1. 14. 이전 1 다음 728x90
