sm 기술 블로그

깊이 우선 탐색(DFS) -> 스택 사용 (재귀 이용 -> 재귀 자체가 스택임) 루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징 깊이 우선 탐색(DFS) 에 비해서 너비 우선 탐색(BFS)이 보다 좀 더 간단하다. 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 과정 결국 이동 순서는 0 -> 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 다음과 같다. 시간 복잡도 인접 리스트로 표현된 그래프: O(N+E) 인접 행렬로 표현된 그래프: O(N^2)

유클리드 호제법 두개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다. 작동 방식 78696과 19332의 최대공약수를 구한다고 해보자. 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 ＋ 72 108 ＝ 72×1 ＋ 36 72 ＝ 36×2 ＋ 0 나머지 정리를 통해 다음과 같이 표시할 수 있다. 나머지 정리란 A(원래 수) = B(나누는 수) * C(몫) + R (나머지) 로 다시 말해 78696 ＝ 19332×4 ＋ 1368 는 78696을 19332로 나누면 몫은 4이고 나머지는 1368이라는 이야기이다. 본론으로 돌..

좌표압축 만약 x축의 좌표가 [0 ,1 ,2 ,3 ,100 ,150]과 같이 주어졌을 때, 0~3은 각 1씩 차이라 크게 문제 되지 않지만 100과 150을 탐색하기 위해서는 100까지, 150까지 탐색해야하는 문제점이 있다. 다시말해 4~99, 101~149는 쓰지 않는데 탐색하고 있는 시간낭비를 하고 있는 것이다. 숫자의 갭차이가 크게 늘어난다면 시간낭비는 더욱 늘어날 것이다. 이때 사용하는것이 좌표 압축이다. 좌표압축 사용 0 ,1 ,2 ,3 ,100 ,150 을 0 ,1 ,2 ,3은 그대로 100을 4로 150을 5로 가정하고 비교한다면 매우 시간이 절약될 것이다. 그래서 0, 1, 2, 3, 100, 150 => 0, 1, 2, 3, 4, 5로 나타낼 수 있다. 구현 방법 먼저 값을 배열로 받고..

스택없는 계산기 먼저 설명에 앞서 모든 기능을 완벽하게 구현할 것은 아니다. 따라서 알고리즘을 보고 각자 기호에 맞게 집어 넣으면 될 것 이다. 스택 방법이 더 쉬우며 스택방법은 완벽히 구현이 완료 되었으므로 스택을 보고 싶다면 클릭 String s1 = (1+(10+5)* 4) 을 계산해 보자 1. 괄호 제거 먼저 괄호가 있는 부분을 찾아야 한다. 괄호에 다음과 같은 규칙을 생각해야한다. 앞에서 부터 ")"가 첫번째로 나온 부분이 제일 먼저 계산해야 하는 부분이다. 뒤에서 부터 "("가 첫번째로 나온 부분이 제일 먼저 계산해야 하는 부분이다. 먼저 공백이 있으면 안되니 공백을 제거해주자 s1 = s1.replace(" ", ""); 그 다음 먼저 계산해야하는 괄호를 찾아 s2에 저장하고, 그 부분에서 ..