위상정렬 - topological sort (비선형 자료구조의 선형화)
비교적 빠른 습득이 가능하고, 효용성도 좋은 알고리즘이라고 생각한다. 문제를 보면 위의 그림과 같이, A,B,C,D가 만드는 쌍(pair)에 대한 관계를 표현하고, 이를 통해 일종의 논리적 체인을 구성해야 하는 일이 있다. 그리고 아래와 같이, 그래프 상에서 DP를 해야하는 경우도 있다. 위의 그림을 조금 더 살펴보자. 위에서 처럼 A에 1을 놓고 전파를 시작한다. A에서 갈 수 있는 정점은 B와 C이므로 B와 C에 A로부터 받은 1을 합산해준다.(모든 정점의 초기값은 0이었다, A를 제외하고.) 위와 같이, E까지 전파하면, BFS를 돌렸을 때, 모든 정점에 대한 방문체크가 끝나고, 그림에서와 같은 값을 갖게 된다. 하지만 이는 올바르지 않다. 전파하는 와중에 값이 변경된 정점이 있기 때문이다. C의 ..
파이썬 자료구조 dict (dictionary)에 대해서
파이썬에는 dict( )라는 명령어가 있다. 맵 구조를 만들어준다. a=dict() a[3]=1 a[5]=3 a['abc']=5 위에서 [ ]안에 들어가는 것이 key이고 =뒤에 있는 것이 value이다. 이는 다른 언어의 해시테이블, 해시맵과 유사한 느낌으로 사용 가능하다. 필자는 이 맵 구조를 대단히 좋아하는데, 배열에서는 어떠한 값들을 선형구조로 기록할 때, 인덱스로 접근하지만, 맵은 인덱스를 임의의 값으로 바꿔놓을 수 있기때문이다. 물론 인덱스 값만 바뀌고 배열의 성질을 그대로 갖는 것은 아니지만, 편의성이 좋아서 자주 사용한다. a=[1,2,5,3]이라는 배열이 있다면, a[3]=3이고, a[2]=5다. 0~3이라는 인덱스를 통해 배열 안의 값에 접근할 수 있다. 그리고 이 인덱스는 항상 0부터..
