IT's me

[자료구조] 연결 리스트의 이해(3)

더미 노드 기반의 연결 리스트에 대해 알아보자.

그 전 포스팅에서 보았듯이, 삽입, 삭제, 참조 시에

첫 노드와 그 이외의 노드의 처리과정이 차이가

나는 것을 볼 수 있었다. 모든 노드들을 일관되게

처리를 해주는 것이 좋은 코드라고 말했는데,

이는 더미 노드를 이용하면 쉽게 해결할 수 있다.

더미 노드란?

유요한 데이터를 저장하지 않는 노드이다.

즉, 헤드가 데이터를 가지지 않는 껍데기(?) 뿐인

노드를 물고있는 것이다. 아래 그림을 보자

기존의 연결 리스트

더미 노드 기반 연결 리스트

왜 이렇게까지 해야할까 의문이 들수도 있지만

연결 리스트의 구현이 더욱 복잡해 졌을 때, 코드의

일관성은 무시할 수 없기 때문이다. 때문에 현재

더미 노드 기반의 연결 리스트가 표준에 더욱 가깝다.

더미 노드를 통해 구현한 삽입, 삭제, 참조를 보도록 하자.

첫 노드를 할당했지만, 아무런 데이터를 물고 있지 않다.

데이터는 이 더미노드 뒤부터 추가되게 된다.

01. 삽입

더 이상 head를 다루지 않아도 된다.

head는 더미 노드이고 실제 데이터는 그 후로 저장되어 있기 때문

02. 참조

03. 삭제

기존의 연결 리스트와 다른 차이점이 보이지 않는다.

다만 처음에 head가 데이터를 저장하지 않는 노드를 물고 있다.

즉, 첫 노드는 아무런 데이터가 없다.

첫 노드를 제외한 모든 코드를 다루는 것이기 때문에

기존의 코드에서 첫 노드를 다루는 부분만 삭제해주면 된다.

DFS 알고리즘 백준의 미로 탐색 문제

백준 알고리즘 사이트의 미로 탐색 문제를 풀어보았다.

DFS 알고리즘, BFS 알고리즘 모두 가능 하지만

DFS 알고리즘을 이용하여 풀어 보았다.

결과는...

내가 생각하기에도 너무 쓸데없는 탐색이 많이 들어가있다.

한 지점에 들렀을 때 이 지점을 경유하면 최소값이

나올 수 없다는 것을 판단하는 부분을 넣어서 

아예 그 지점에 대한 DFS 알고리즘을 수행하지 않는

방법으로 가보는 것이 좋을 것 같다.

01. 초기화 , 체크 함수

02. DFS 알고리즘

03. 메인 함수

DFS 알고리즘은 항상 풀기는 쉬운데

시간 초과가 많이 뜨는 것 같다.

이 문제는 정답을 맞춘 후에

위의 포스팅과 비교하여 어떤 부분에서

시간초과가 났는지 분석해서 올리도록 하겠다.

BFS 알고리즘 백준의 토마토 문제

정말 오랜만에 BFS 알고리즘 문제를 풀어 보았다.

그저께 DFS 알고리즘 문제를 풀다가 2시간 멘붕이 와서

사실 자심감이 많이 떨어진 상태..

BFS, DFS만은 자신 있었는데.. 꾸준히 해야겠다는 생각이 든다.

이 문제도 40분 걸렸지만, 한 번에 성공했다는 것에 만족~

01. 구조체 , 큐, 박스 등등

02. 초기화

03. 체크 함수

04. 모두 익었니? 아니면 덜 익은게 있니?

05. BFS 알고리즘

06. 메인 함수

BFS 알고리즘을 이용하여 백준의 토마토 문제를 풀어보았다.

한동안 알고리즘에 손 떼고 있다가 풀어보니 낯설다..

무엇이든 꾸준함이 가장 중요한 것 같다.