problem solving/ps 팁5 [ps 팁] 재귀는 마치 누군가가 종이에 숫자를 쓰고, 그 종이를 다음 사람에게 넘겨주는 방식과 같다 아래의 코드를 보면 DFS여서 매번 재귀할 때마다 함수 첫 번째 줄부터 다시 시작하는데저렇게 int cnt = 1;해 버리면 카운트를 하다가도 계속 1로 초기화되는 거 아닌가..? 처음엔 그렇게 보일 수도 있지만, 재귀 함수에서는 각 함수 호출마다 자신만의 지역변수 스코프(scope)를 가지기 때문에int cnt = 1;이거는 그 호출된 함수 하나에만 국한되는 초기화다private static int dfs(int V) { visited[V] = true; int cnt = 1; // 자기 자신 포함 for (int next : graph[V]) { if (!visited[next]) { cnt += dfs(next); // 재귀 호출 결과 누적 .. 2025. 3. 25. [ps 팁] 그래프 순회는 무조건 인접 리스트로 구현하는 게 유리할까? 결론부터 먼저 말하면..간선 리스트: MST 크루스칼 알고리즘인접 행렬: 최단 거리 플로이드-와샬 알고리즘인접 리스트: 그 외의 모든 것들!! 그냥 모든 ps 문제들은 인접 리스트로 구현하는 게 맞을까?틀리다! 각각의 구현 방식들에는 장단점들이 분명해, 올바르게 선택해야 좋은 효율을 낼 수 있다.https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep5-1-%EA%B7%B8%EB%9E%98%ED%94%84graph [알고리즘] ep5-1) 그래프(graph)ㅁ그래프(graph) ADT: (vertex, edge)의 쌍v: 정점 노드들의 집합e: 간선 노드들의 집합 정점: 공항을 표현하며 공항도시 이름을 저장간선: 두 공항 .. 2025. 3. 24. [ps 팁] 이진 탐색 트리(BST) 순회에 관한 놀라운 사실 이진 탐색 트리(BST)에서 중위 순회를 하면 오름차순으로 정렬된 결과를 얻을 수 있다.....ㅎㅎ 2024. 10. 27. [ps 팁] 문제의 입력 제한값으로 알고리즘 유추하기 https://claremont.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-ep1-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B8%B0%EB%B3%B8-%EC%A7%80%EC%8B%9D%EB%93%A4 [자료구조] ep1) 자료구조 기본 지식들ㅇ다차원 배열- 3차원 배열 - 4차원 배열 ㅇ빅오(Big O) 표기법: 연산의 횟수를 대략적(점근적)으로 표기"최악의 case 실행시간을 고려한다" [예시](1) 7n-2: O(n)(2) 3n^3 + 20n^2 + 5: O(n^3)(3) 3log(n) + logclaremont.tistory.com 일반적으로 연산을 1억(10^8) 번 하면 1초다📌 어떻게 나온 계산인가.. 2024. 10. 23. 코딩테스트 빈출 유형 정리 [코딩테스트 주요 알고리즘]- 구현 및 시뮬레이션 - 문자열 처리(해시테이블 or 스택)- 완전 탐색(브루트 포스)- 이진 탐색(매개변수 탐색)- 그래프 탐색(DFS, BFS)- 백트래킹- DP- 그리디- 투포인터 [가끔 나오는 알고리즘]- 정렬- MST(크루스칼)- 최단경로(다익스트라, 벨만-포드, 플로이드-와샬)- 위상정렬- 모든 쌍 최단경로 문제- 분리집합- 트리의 지름 구하기- 트라이 2024. 8. 4. 이전 1 다음
