목록자료구조 (2)
Seung's Learning Record
≣ 목차 알고리즘 시간 복잡도 알고리즘을 풀때는 제한 시간내에 코드가 실행 완료되는것이 중요하다. 이를 위해 우리는 알고리즘의 시간복잡도와 공간 복잡도가 어떠한가를 미리 파악한 후 이에 맞는 문제 풀이 방법을 생각해내야 한다.이러한 복잡도를 표현하는 방법 중 가장 흔히 사용되는 방법은 빅오 표기법(big-O notation)이다. 이에 관한 설명은 아래 링크에 자세히 작성되어 있다. https://seung2344.tistory.com/22 리스트 파이썬에는 다른 언어들에서 다뤄지는 배열과 유사한 성질의 리스트(list)라는 자료구조가 존재한다. 동일한 자료형만 가질 수 있는 배열과는 달리, 리스트는 다양한 자료형을 하나의 리스트 안에 담을 수 있다. 선언 방법 a = [1,2,'a','b',"xyz"]..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/k5GpZ/btsz1e47zlT/CncmzCDi4KvSKBdk5qYNIk/img.png)
BFS(Breadth First Search) BFS란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 시작 정점을 방문한 후, 인접한 정점들을 우선 방문하는 방법이다. 해당 그래프의 방문 순서가 저럴 경우, 큐에 값이 들어가고 나가는 순서는 다음과 같다. push(0) -> pop(0) -> push(1), push(2) -> pop(1) -> push(3) -> pop(2) -> push(4) -> pop(3) -> pop(4) BFS구현 이론 BFS 구현을 위해서는 큐를 사용해야 한다. 쉬운 이해를 위해 빨간색,파란색이 섞여있는 2차원 배열에서 파란색 칸만을 탐색하는 알고리즘을 작성하는 과정을 예로 들어 구현 플로우를 대강 정리해보자. 시작 좌표(0,0)를 방문 표시 후,..