IT's me

BFS 알고리즘 보물섬 문제 (정올)

BFS는 항상 최단 경로만을 찾는다는 것을 명심하자.

목표지점까지 가는 루트가 많아도, 빙빙 둘러서

가는 경우가 없다. 왜냐하면 모든 루트가 큐에 저장되고

너비 우선탐색으로 진행되기 때문이다.

따라서 목표지점까지 중복된 곳을 방문하지 않으며,

목표지점까지 가는 길이 여러개인 경우

마지막에 비교를 통해 최저값을 찾아주기만 하면 된다.

BFS 보물섬 문제

01. 선언

02. 초기화 , 인큐, 디큐, 유효성 검사, 큐가 비었는지 검사

03. BFS 알고리즘 시작

04. 메인 함수

BFS 알고리즘은 DFS 알고리즘에 비해

이해하기도 쉬울 뿐더러 구현하기도 쉬운 것 같다.

어떠한 문제가 주어졌을 때 두 알고리즘 중에

어떤 것으로 풀어야 할 것인지 잘 캐치해야 할 것이다.

알고리즘의 기초가 되는 문자열 문제를 풀어보겠다.

백준 사이트에 있는 아스키 코드 , 알파벳 찾기, 문자열 반복이다.

01. 아스키코드

말할 것도 없는 문제

02. 알파벳 찾기

문자열을 찾아 체크하는 문제

문자열 체크라 해서 체크 변수를 생각없이

char로 줬는데 상당히 애를 먹었다.

출력하라는 대상의 자료형이 무엇인지 똑바로 보고

제대로 변수를 선언 하도록 하자!

03. 문자열 반복

도대체 뭐가 틀렸는지 알 수가 없다.

20 글자 넘지 마라해서 21 , 20 ,19로 다 체크해도 안되고

실행 시켜서 이것 저것 다 넣어봐도 잘 실행되는데..

기분 팍 상해서 오늘은 퇴근

알고리즘 기초가 되는 문자열

코딩 테스트 단골 메뉴이기 때문에

자주 풀어봐야겠다.

BFS 알고리즘 저글링 방사능 오염 문제 (정올)

BFS에서 좀 난해한 부분이라 하면

큐의 사이즈를 얼마로 해줄 것인가.

경우의 수를 다 따져서 큐의 사이즈를

정해줘야 하니 이것 또한 생각해봐야 할 문제.

그리고 이 문제를 풀면서 느낀점은

좌표에 대한 개념에 좀 더 익숙해져야 할 것 같은..

01. 저글링 구조체 선언

그리고 BFS 알고리즘을 위한 큐 관련 함수

02. 유효성 검사와 큐가 비었는지 검사

03. 큐를 하나씩 빼면서 탐색

또한 탐색해야할 부분에 대해서

큐에 차곡차곡 쌓아두자.

04. 메인 함수

BFS 알고리즘은 DFS 알고리즘에 비해

손이 많이 간다는 느낌이 든다.

하지만 뭔가 문제가 깔끔하기에 맘에 든다.

BFS 알고리즘 장기 문제 (정올)

첫 BFS문제이다. 확실히 DFS보다는 쉽게 느껴진다.

하지만 90점.. 그래도 첫 문제니 원리를 알았다는 거에

만족하며 이 문제는 여기서 마무리..

01. 구조체를 선언하고 초기화 한다.

또한 BFS 알고리즘은 큐가 핵심 원리이기 때문에

큐에 저장하는 함수 큐에서 빼내는 함수를 정의

02. 장기 말이 장기판 밖으로 나갔는지

혹은 지나왔던 곳을 또 밟았는지를 체크

03. BFS 알고리즘의 핵심 원리인 큐를 이용하여

노드를 큐에 넣고 빼고를 반복하며 답을 찾는다.

DFS를 할 때는 구정물에 발을 담그는 느낌이었는데

BFS 알고리즘은 그보단 훨씬 깔끔한 느낌이다.

DFS 알고리즘 적록 색약 (백준)

런타임 에러..

예제는 정답이고 내가 임의로

입력해봐도 맞는 값이 나오는데

런타임 에러가 뜬다. 다른 사람들의

답을 참고해봐도 비슷한거같은데..

새벽이라 고칠 의욕도 안나고..

01. 초기화

02. 답 찾기

이번 DFS 알고리즘은 답을 찾는 데 꽤 오래 걸렸다.

단지 번호 붙이기와 상당히 유사한 문제였지만

두 가지의 답을 찾아야 했기 때문에 한번의 호출로

답을 찾아야 할지, 아니면 나누어서 찾아야 할지

고민을 많이 했던 것 같다.

아무튼 BFS 알고리즘은 많이 풀어보는게 답인거 같다.

DFS 알고리즘 단지 번호 붙이기 (백준)

DFS 문제이다. 재귀를 사용해서 풀었다.

원래는 메인에서 재귀함수를 한번 호출하고

재귀 함수 내에서 모든 작업을 다 하는 방식으로

진행하려 했지만, 메인에서 반복문으로 재귀를 불러주니

문제가 상당히 쉬워졌다.. 그래도 여전히 25분

01. 초기화

02. 재귀 함수 호출 및 답 출력

DFS 알고리즘을 풀면서 비용적인 측면까지도

생각해볼 때 인 것 같다. 위의 문제는 메인에서

하나하나 호출을 하는게 상당히 비효율적으로 보인다.

하지만 테스트는 푸는 시간 또한 중요하기에

이러한 방법으로 계속 푸는 연습을 해야겠다.

DFS 알고리즘 경로찾기 (백준)

DFS 문제이다.

재귀를 사용해 풀었지만 시간초과..

때문에 답이 맞는지도 모르겠다.

적어도 예제는 다 맞았으니 올려본다.

다음엔 스택을 이용해 풀어보겠다.

예전 같은 경우 재귀를 이용해 DFS를 풀 때

재귀 함수 내에서 모든 것을 끝내려 했다.

사실 그게 큰 부담이 되었는데, 메인 함수에서

재귀를 여러번 불러주는 식으로 진행을 하니 한결 수월했다.

비용적인 측면에 대해서도 고민해볼 시기인 것 같다.

열공합시다!

백트래킹 알고리즘 알파벳 문제 (백준)

난이도가 어려운 편은 아니었지만

아직 재귀에 대해 익숙하지 않은 듯 하다.

좀 더 연습해서 이러한 문제는 10분 대에

해결할 수 있도록 해야겠다.

말이 지나온 알파벳을 저장해두고

중복된다면 다시 돌아가는 것이 포인트

이번 주 까지는 백트래킹과 기초적인 문제를

많이 풀어보고 다음 주 부터 BFS를 들어가도록 하겠다.

백트래킹 알고리즘 부분집합의 합 (백준)

처음부터 답을 참고하고 들어가니 쉽게 풀린듯 하다.

이제는 어떠한 문제가 백트래킹 문제라는 것을

빨리 캐치하는 연습이 필요한 것 같다.

지금까지 풀어봤던 백트래킹 문제치고는

난이도가 상당히 낮은 편이었다.

그래도 백트래킹의 대표적인 문제라고하니

좀 더 들여다 볼 필요가 있는 것 같다.

쉬운 문제인데도 30분이 걸렸다.

좀 더 분발하자.

알고리즘 기초 수열 (정올)

오름차순으로 한번 내림차순으로 한번

따로따로 함수를 만들어 값을 카운트하고

마지막에 비교해서 큰 값을 출력

01. 오름차순 카운트 , 내림차순 카운트

02. 초기화 한 후, 함수를 호출해서 값을 얻어냄

알고리즘 기초, 이러한 기초적인 문제를

많이 풀어봐야 할 듯하다.