코알못의 코잘알 되기 프로젝트

[문제]

https://www.acmicpc.net/problem/1931

[문제 풀이]

- 공책에 도식화

끝을 정렬하면 될 듯?  끝 값과 다른 회의에 첫 값 비교 후 첫 값이 더 크면 그걸 다시 끝 값으로 삼기

- 회의 시간 pair 사용

두 변수가 하나의 변수 처럼 사용될 때 (대신 두 값 따로 사용할 수 있는 무언가여야함) 검색하다가 pair 발견

Pair 클래스는 사용자가 지정한 2개의 타입의 데이터를 저장하는데 사용합니다.

첫번째 인자 p.first로 꺼낼 수 있기도 하고 해서 좋을 듯 

- sort를 해야하는데 pair라 어떻게 sort되는지 궁금해 출력해봄

원리 파악 완료 v.first 요소들만 sort - 끝 값 비교할거라 이대로 sort하면 안될 듯 싶어 push 할 때 first에 끝 값 넣음

해결!

[문제]

https://www.acmicpc.net/problem/19942

[푼 방식]

재료라는 변수를 담을 곳을 고민하다 구조체를 만들기로 결정함 이 구조체는 단,지,탄,비,재료가격 변수가 포함되어있음

- vector을 가지고 있는 int 자료 vector  키를 가지고 있는 map을 사용함 키에 중복된 값도 들어가지 않는 점도 이용  자동으로 오름차순으로 정렬도 됨 cost 합 vector int가 여러개를 뭐가 담을 수 있나 여러개 써보다가 얼마전에 배운 map쓰니까 된다.

마지막 결과만 남았는데 에러가 뜬다..;; 제일 cost적게 나오는거 출력하면 되는거 아닌가?

바보였다... 여기서 이미 최저를 걸러주고 있으니 ret만 출력하면 된다

ret 초기값 설정안해줘서 오류난것도 해결했다...!

해결..!...

이었으면 좋겠지만 runtime 오류남.. 처음보는 오류였다,,

머리 싸매다가 초기값 막 설정하고 생각나서 다들 987654321로 설정해주길래 그렇게 했더니 해결됨...

진짜 해결

DFS는 그래프를 탐색할 때 쓰는 알고리즘이며 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘입니다.

수도코드

DFS의 수도코드는 다음과 같습니다. 

수도코드(pseudocode)? 는 프로그램의 로직을 표현하기 위해 쓰이는 코드입니다. 주로 어떤 알고리즘이 어떠한 로직을 갖고 있는 지 나타내기 위해 쓴다. 

<설명>

어떠한 정점 u의 visited를 참으로 바꾸고 u로 부터 연결되어있는 v지점을 탐새합니다.

이 때 방문되어있지 않은 노드에 대해 재귀적으로 DFS를 호출합니다. 

재귀적으로 1,2,4번까지 방문한다. 또한, 4번에서 다시 2번으로 가려고 했지만 이미 방문한 노드이기 때문에 다시 방문하지 못하고 5번으로 간다. 

1 - 2 - 4 -5 - 3

DFS 구현방법

1. 돌다리 두드려보기

visited 되어있는지 확인

2. 일단 GO

일단 방문되어있던 안되어있던 무조건 dfs를 호출하고 해당 함수에서 만약에 방문되어있다면 return 해 함수를 종료시키는 방법입니다.