2023/07/29 20:00 ~ 23:00
Meeting Summary
사전에 선별한 프로그래머스 Lv.1 ~ Lv.2 문제들 총 5문제를 선별하고 미리 풀어왔다.
#1. https://school.programmers.co.kr/learn/courses/30/lessons/17687
#2. https://school.programmers.co.kr/learn/courses/30/lessons/12973
#3. https://school.programmers.co.kr/learn/courses/30/lessons/42888
#4. https://school.programmers.co.kr/learn/courses/30/lessons/17684
#5. https://school.programmers.co.kr/learn/courses/30/lessons/92342
특히 애먹은 문제들은 #4, #5로 모두 카카오 기출문제였다.
#4는 구현하는 과정에 비해 입출력 흐름을 파악하고 이해하는 데 오래 걸렸고,
#5는 문제를 이해하는 것은 다소 쉬웠으나, 예외 사항이나 조건이 붙은 것 때문에 구현하는 과정에 더 많은 시간을 할애하였다.
#3까지는 무난하게 풀이해왔고 서로의 풀이 방법 공유와 접근 방법의 차이에 대해서 비교해보았다.
이때 #2. 문제에서 동엽이는 특이 case를 우선적으로 처리한 이후에 일반적인 case를 처리하였는데, 종혁이는 예외처리를 굳이 해야 하는 경우가 아니면 하지 않는다고 했다. 그래서 예외처리를 제외하고 보니 둘 모두 구현한 코드는 같아서, 서로의 runtime이 유의미한 차이를 갖는지 궁금하여 비교하였으나 (일부 특이 케이스를 제외하고) 거의 유사한 실행 시간이 나왔다. 아마 for문이 하나만 있고 연산 횟수가 동일해서 그런 것으로 생각된다.
동엽이의 코드 경우 테스트 6번에서 실행시간이 높아진 것을 볼 수 있었는데 해당 테스트가 어떤 입력인지 알 수 없어서 더 자세한 분석은 불가했다.
What we learned today
"탐색"을 요하는 문제들에 대해서 사용할 수 있는 DFS와 BFS의 구현에 대해서 정리해보았다.
DFS와 BFS를 구현할 때에, DFS는 스택이나 재귀함수를 사용하고, BFS는 큐를 사용한다.
- DFS의 stack 구현 과정
- 1) 탐색 시작 노드를 stack에 삽입하고 visited로 처리
stack의 top에서,
- 2-1) not_visited인 인접 노드가 있는 경우 stack에 삽입하고 방문 처리, 없는 경우 최단 노드를 pop한다.
- 3) 2)가 불가능할 때까지 반복한다.
- BFS의 queue 구현 과정
- 1) 탐색 시작 노드를 queue에 삽입하고 visited로 처리
- 2) queue에서 노드를 pop한 후, 인접 노드 중 not_visited인 노드를 모두 집어넣고 visited로 변경한다.
- 3) 2)가 불가능할 때까지 반복한다.
보통 기본적인 자료구조로는 위와 같이 표현을 하지만,
구현이나 확장성(입출력 처리 등)을 고려해서 DFS를 재귀함수로 구현하는 경우가 많다.
재귀함수는 사용할 때 종료 조건을 명시해줘야 무한 루프에 빠지지 않고 사용 가능하다.
(스택과 재귀함수 모두 LIFO(Last-In-First-Out)이므로 구조적으로 동일하다)
