자료구조 고득점을 위한 계산 실수 줄이는 법 대표적인 실수 문제들

소개글

자료구조 오답노트 : 대표적으로 실수할 법한 문제들을 엄선 실수를 줄이자
난해한 문제도 엄선

목차

없음

본문내용

*항상 답을 고를 때는 다른 답들도 유심히 봐야한다 그래야 함정을 찾을 수 있다
*또한 답을 비교 할때 선택한 답에 다른 답이 두가지가 나오면 의심해봐야 한다
즉 내가 선택한 답이 ABDC, 였고 다른 답이 ABCD, ADBC 이며 의심
1. 순환함수 호출개수

2. 순환함수 연산
if xxx(int n){
if(n==0)
return 4;
return 1 + xxx(n-1);]

<중 략>


16. 후위순회 전위순회 중위순회
* 후위순회와 전위순회
post G D E B H F C A
pre A B D G E C F H
단말노드는 ? 중위순회하면 ?
-후위와 전위이고 HF, FH 다르므로 둘중에 하나만 단말 노드 전위 기준이므로 H, GD와 DG가 다르므로 전위기준으로 G가 단말노드 E도 단말노드가 된다
-중위순회 GDBEACFH (전위를 기준으로 문제를 풀어라) 어려움
*후위순회로 중위순회 순서
후위순회 ABCDEFG 에서 CBEGADF가 나올수 있는가 ? x
스택이 top이외에도 bottom이란 포인터를 사용해야 되는 경우는 여러 개의 스택을 하나의 연속된 기억공간에 나타날 때 o
17. A/B**C+D*E-A*C 전위표기 형태에서 후위 표기 형태로 바꾼것은 ?
- 제곱을 유의하라 = ABC*/DE*+AC*-

18. 최단 경로 문제 포인트
- 한 정점에서 최단 경로를 찾는 것은 O(n의2승)
- 모든 정정을 최단 경로를 찾을 때 수행 시간은 O(n의3승)
- Dijkstra알고리즘을 인접행렬로 표현 시 시간복잡도는 O(n의2승)
- Bellman과 Ford 알고리즘을 인접행렬로 표현 시 시간복잡도는 O(n의2승)

19. 인접 다중 리스트는 그래프 표현은
- 노드를 보면서 간선이 있는지 보아라

참고 자료

없음