부캠 2차 문제

[익명(118.91)]

1번 수열 연속: 구현

2번 원형 집: 그리디

3번 하우징 접근 비용: 구현

4번 아르바이트: 정렬 후 완탐(그리디도 가능할 듯?)

5번 풍선 터트리기: 자료구조(map 등)

6번 지뢰찾기: bfs 구현

7번 개구리: dp + bfs

8번 항공 연료통: MST

3문제(1, 2, 7)는 1차랑 중복이구만

컷은 5솔 정도?

[익명(114.203)]

dp할게 있나?

[익명(118.91)]

memorization은 해야되니까?

[익명(114.203)]

할게뭐있지 visited체크?

[익명(118.91)]

지역 최솟값을 알아야하잖아

[익명(114.203)]

bfs는 최소 보장이잖아.

[익명(114.203)]

source가 일정하고

[익명(118.91)]

대신 그러면 큐에 들어가는 메모리가 많아짐. a에서 c 가는 거랑 b에서 c 가는 거랑 두 경우 모두 똑같은 횟수면 2개가 들어가버리잖어

[익명(114.203)]

큐에는 visited 안된것만 들어갈 수 있으니까 공간복잡도는 무조건 O(N) 아니냐? visited했는지 여부 체크하는거 말하는거 아니냐?

[익명(118.91)]

아 ㅇㅋ 무슨말인지 이해했음. 그러면 맞지. 나는 visited 대신에 걍 dp를 visited처럼 썼음. 그래도 됨 ㅇㅇ

[익명(114.203)]

서로 dp에 대한 정의를 다르게 이해한듯 ㅋㅋ;

[익명(121.167)]

6문제에 8번 정확도만 맞았는데 제발...

[익명(118.91)]

그 정도면 붙을듯

[익명(121.167)]

고마워 제발 그러길

[익명(203.226)]

망함

[익명(114.203)]

5번 map넣기전에 어떤처리해야되냐? 최소공배수로 나눠줘야하나

[익명(118.91)]

걍 map 2개써서 y >=0일때랑 y < 0로 나누면 됨

[익명(118.91)]

아 나는 기울기로 처리는 했음

[익명(114.203)]

아 시발 ㅋㅋㅋ 기울기를 왜 생각안했지;

[익명(114.203)]

쓸데없이 어렵게생각했네

[익명(114.203)]

8번빼곤 아는거라 다 풀만했는데 시발 쓸데없는 문제에 시간 많이버렷다..

[익명(222.107)]

ㅋㅋ 2시간 넘 짧어

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(118.91)]

ㅇㅇ

[익명(220.78)]

8번이 MST였음?

[익명(220.78)]

이분탐색으로 했는데 mst랑은 달랐던거 같은데

[익명(118.91)]

ㅇㅇ. MST 쓰고 하나씩 빼면서 1번 정점과 n번 정점이 같은 component에 속하게 될 때 끝내면 됨.

[익명(118.91)]

이분탐색으로 bfs 한 번씩 돌아도 되긴 할 텐데, 문제 제한이 기억 안나는데 엄청 크면 MST가 나을 듯

[익명(220.78)]

아 그렇게 해도 되네 ㅋㅋ