일시
22.07.02 19:00 ~ 22:00
목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.
사용 언어
C++
1번 문제
https://www.acmicpc.net/problem/1260
결과
dfs를 구현한 함수로 재귀적으로 구현하지 않고 스택을 사용하여 구현함.
bfs를 구현한 함수로 큐를 사용하여 구현하였다.
메인함수 코드로 데이터를 입력받고 순서가 뒤죽박죽일 수 있으니 정렬 후 dfs와 bfs를 사용해 결과 출력한다.
67번째 줄은 visited배열(방문 하였는지 확인용 배열)을 dfs에서 사용하고 초기화 해주는 코드다.
2번 문제
https://www.acmicpc.net/problem/1697
결과
이 문제도 bfs를 사용하여 쉽게 풀수 있는 문제이기에 bfs를 사용하였고 16줄은 도착 하였을 때 시간을 리턴하고 17-20, 21-24, 25-28은 각각 움직임이 x+1, x-1, 2*x로 움직였을 때의 경우를 나타낸것이다.
3번 문제
https://www.acmicpc.net/problem/2178
결과
가장짧은 길을 찾는 문제로 dfs나 bfs로 풀수있는 가장 유명한 예제이다.
이 문제는 dfs로 해결하였다.
4번 문제
https://www.acmicpc.net/problem/10844
결과
Dynamic Programming으로 푸는 문제로 마지막 자리수가 0이나 9를 제외하고는 자리수가 늘어날때마다 2개의 경우의 수가 생긴다.
이점을 유의하여 풀면 된다.
Vancouver