목록전체 글 (291)

반갑습니다!

[백준] 2302 극장 좌석

2302번: 극장 좌석 boj.kr 풀이 VIP 회원들에 대해 생각하기 전에 일반 회원들을 먼저 생각해보자. 우선 1명의 회원이 좌석에 앉는 방법을 생각해보자. 1명의 회원이 앉을 수 있는 방법은 1가지인 것은 당연할 것이다. 이번엔 2명의 회원이다. 1, 2 / 2, 1 이렇게 총 2가지 방법으로 앉을 수 있다. 다음엔 3명의 회원인 경우이다. 1, 2, 3 / 1, 3, 2 / 2, 1, 3 총 3가지 방법이 나온다. 4명의 회원의 경우는 1, 2, 3, 4 / 1, 2, 4, 3 / 1, 3, 2, 4 / 2, 1, 3, 4 / 2, 1, 4, 3으로 총 5가지가 나온다. 4명의 회원인 경우를 조금 더 자세히 살펴보자. 1, 2, 3, 4 1, 2, 4, 3 1, 3, 2, 4 2, 1, 3, 4 ..
알고리즘 문제 풀이 2020. 10. 12. 14:59
[백준] 1976 여행 가자

1976번: 여행 가자 boj.kr 풀이 이 문제에서 동혁이의 여행 계획을 달성하기 위해서 최단 거리로 이동할 필요가 없다. E C B C D가 계획이라면 도시 사이에 다른 곳을 경유해도 된다는 의미이다. 따라서 이 문제는 결국 여행 계획을 세운 도시들이 같은 그래프에 속해있는지 파악해서 모두 같은 그래프에 속해있으면 YES, 다른 그래프에 속해있으면 NO를 출력하는 문제가 된다. 아래의 코드에서 같은 그래프에 속해있는지는 유니온 파인드를 사용해서 구분했다. 코드 C++ Python3
알고리즘 문제 풀이 2020. 10. 9. 15:23
[백준] 1005 ACM Craft

1005번: ACM Craft boj.kr 풀이 작업 문제와 거의 동일한 문제이다. 위상 정렬과 동적 계획법을 이용해 각 건물에서의 최대 건설 시간을 계속해서 갱신해주면 해결할 수 있다. 코드 C++
알고리즘 문제 풀이 2020. 10. 8. 17:39
[백준] 2056 작업

2056번: 작업 boj.kr 풀이 이 문제는 작업들 간의 선행 관계가 정해져 있기 때문에 위상 정렬로 해결해야 하는 문제이다. 그리고 동적 계획법으로 각 작업을 수행하기까지 걸리는 최대 시간을 계속해서 갱신해줘야한다. 코드 C++
알고리즘 문제 풀이 2020. 10. 8. 17:33
[백준] 1948 임계 도로

1948번: 임계경로 boj.kr 풀이 이 문제는 위상 정렬과 BFS를 사용해서 해결했다. 우선 위상 정렬을 사용하면 도착 도시까지 걸리는 최대 시간을 쉽게 구할 수 있다. 그리고 나면 관건은 1분도 쉬지 않고 달려야 하는 도로를 세는 것이다. 이는 위상 정렬을 했던 결과를 이용해서 구할 수 있다. 위상 정렬을 수행해서 각 도시까지 도착하는데 걸리는 최대 시간을 알아냈기 때문에 이번에는 도착지에서 출발지로 역행하면서 탐색해준다. 어떻게 도로의 개수를 찾을 수 있는지는 그림을 보면서 이해하자. 위의 그림처럼 1번 도시까지의 최대 시간이 7, 2번 도시까지의 최대 시간이 17이고 1번 도시와 2번 도시 사이의 도로를 건너는데는 10분이 걸린다고 가정하자. 그렇다면 2번 도시에서 1번 도시로 탐색을 할 때 2..
알고리즘 문제 풀이 2020. 10. 8. 17:09
이전 Prev 1 ··· 7 8 9 10 11 12 13 ··· 59 Next 다음