알고리즘 썸네일형 리스트형 [DFS & DP] BJ_1937, 욕심쟁이 판다 [문제의 접근] 500 X 500의 배열이 주어지고, 동서남북으로 이동이 가능하다. 당신이 제일 먼저 생각하게 되는 풀이법은? 바로 BFS일 것이다. 그런데 이 문제는 잘 읽어보게 되면, 시작하는 위치와 더불어 방문의 순서가 매우 중요하다는 것을 깨달을 수 있다. 간단한 예시로 아래의 배열을 보자. 가장 작은 대나무의 위치인 5에서 시작한다고 가정했을 때 DFS로 탐색하는 경우는 한번에 한 위치만 방문하기 때문에 위와 같이 최대거리 4를 찾아낼 수 있지만, BFS로 탐색할 경우 최대 거리를 3밖에 찾을 수 없다. 거리 4를 도출하기 위해서는 한번 방문한 위치를 다시 방문해야 하고, 이는 가장 기본적인 BFS탐색 원리를 위배하는 일이다. 즉, 이문제는 DFS로 풀어야 하는 문제다. 보통 DFS로 풀기 위한.. 더보기 Next Permutation Permutation(순열)은 프로그래밍에서 흔하게 사용되는 개념이다. 나무 위키에는 다음과 같이 정의되어 있다. 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다. 위의 순열의 개념에서 "순서에 상관있게"를 "순서에 상관없게"로 바꾼 개념이 바로 조합(Combination)이다. n과 r이 일정한 수로 주어졌을 때, 어느쪽이 경우의 수가 더 많이 도출될까? 당연하게도, 순열이 그 경우의 수가 훨씬 많다. $_nP_r = n \times(n-1) \times (n-2) \times ... (n-r+1) =$ $n!\over(n-r)!$ $_nC_r = $ $_nP_r\over r! $ = $1\over r!$ $n!\over(n.. 더보기 [DP] BJ_2775, 부녀회장이 될테야 [문제의 접근] 이 문제에서의 핵심은 바로 다음 글귀이다. "a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다." 이 것을 읽고 어떤 생각을 해야할까? 특이한 조건이네 이렇게? 특이한 조건인건 맞다. ㅎㅎ. 많은 알고리즘 문제에서는 스토리를 만들어내기 위해 사실 별로 필요없는 문구들도 많이 넣기는 하는데, 위의 문구를 보면 아래와 같은 수식을 떠올려야 한다. 우리는 알고리즘 문제를 풀고 있고 알고리즘은 수식으로 이루어지니 말이다. arr[a][b] = arr[a-1][1] + arr[a-1][2] + ... arr[a-1][b] 그럼 이 문제를 위의 수식 그대로 풀어내면 될까? test case의 T의 숫자가 주어지지 않아서 명확하진 않지만.. 더보기 [Two-Pointer] BJ_2230, 수 고르기 [문제의 접근] 두 수를 선택하고, 두수의 차이가 M이상이면서 가장 작은 차이를 구해야 한다. 어떻게 접근해야 할까? Bruteforce로 접근하면 가장 쉽게 접근법을 생각할 수 있다. 즉 모든 경우의 수를 비교해 보는 것이다. N개의 수 중에서 2개의 수를 임의로 선택해야 하기 때문에, $O(N^2)$ 시간 복잡도가 나온다. For 문을 계층적으로 2번 돌린다고 생각하면 쉽다. 첫번째 수를 정하고 N-1개 비교, 2번째 수를 정하고 N-2개 비교,.... 현재 N이 1,000이하라면 충분하겠지만, 주어진 값은 N이 100,000 으로 주어져 있다. 연산량은 $10^{10}$으로 대략적인 1초의 연산량 $10^8$을 초과하므로 시간초과다. 그럼 어떻게? $O(n\log_{2}{n})$의 접근이나, $O(.. 더보기 [DFS] BJ_13023, ABCDE [문제의 접근] 어떻게 이 문제에 접근할 수 있을까? 일단, 친구 관계로 주어지는 입력이 graph로 표시될 수 있다는 것을 알아야 한다. 또한 graph의 깊이가 4단계 까지만 진행할 수 있다면 문제의 답으로 도출할 수 있는 것으로 보아 그렇게 깊게 탐색할 필요가 없다는 사실도 알 수 있다. 모든 경우를 다 탐색해 봐야 하는 문제일까? 아니다. 5명이 친구가 되는 케이스가 하나만 있다면 탐색을 종료하고 답을 도출하면 된다. 그렇다면 어떤 알고리즘을 사용해야 할까? 바로 DFS이다. [DFS의 특징] 탐색 가능한 경로의 모든 방향의 Graph를 탐색하여 답을 도출하는 BFS와는 다르게 DFS는 모든 경로를 체크하는 대신 한 경로 우선하여 마지막 깊이까지 진행하여 조건을 만족할 수 있다면 다른 경로를 탐색.. 더보기 [BruteForce] BJ_1018 체스판 다시 칠하기 알고리즘의 존재 이유이자 최종 목적은 제한시간 안에 얼마나 효율적으로 문제를 계산해 낼 수 있으냐이다. 따라서, 모든 알고리즘 문제에서 수의 입력 범위를 확인하는 것은 중요한 일이다. 입력 범위가 충분히 작다면 굳이 어려운 방법으로 문제를 풀 필요가 없다는 뜻이된다. 컴퓨터는 1초에 1억번 정도의 연산을 해낼 정도로 계산에 최적화된 기계이다. 그렇다면 이 문제에서는 얼마만큼의 연산량이 필요할까? 문제를 읽어보면 확인할 수 있겠지만, 입력으로 주어지는 전체 판의 크기는 50 x 50이다. 여기에서 기준이 되는 매트릭스 좌측 상단의 색깔이 'W', 'B' 두가지 케이스에, 검사해야 하는 maxtrix의 크기인 8x8이다. 총 계산량은 ? 아무리 크게 잡아도 32만을 넘기 어렵다. 그렇다면 우리가 이 문제를 .. 더보기 BJ_6987 월드컵 문제 문제를 처음 접할 경우, 너무 쉬운게 아닐까라고 생각해 볼 수 있는 문제지만, 나름의 복잡함을 확인할 수 있는데, 일단 입력 부분이다. 나라마다 승/무/패의 결과가 일렬로 나열되어 주어지기 때문에 나라별로 정리할 필요가 있다. 리스트 슬라이싱 등 여러가지 방법이 있을 수 있지만, 아래와 같이 map iterator를 이용해서 정리하면 비교적 깔끔하게 정리가 가능하다. n을 map 객체로 선언한 후, next(n)의 경우는 iterator에서 하나씩 item을 꺼내주는 함수이므로 이를 이용해서 승/무/패 3개씩 6개의 독립 리스트로 분리할 수 있다. n = map(int, readl().split()) result = [[next(n) for w in range(3)] for t in range(6)] 그.. 더보기 이전 1 2 3 다음
