본문 바로가기

알고리즘34

[백준] 1629 곱셈 by C++ https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 재귀를 제대로 이해하고, 수에 관한 통찰력도 요구하는 문제다. 핵심함수 Recur : A, B, C를 입력 받고 A ^ B % C (나머지)의 값을 반환 알고리즘 방식 방식이라기보다는 2가지만 명확히 이해하면 어렵지 않게 풀 수 있다. 재귀 A^B % C = [A^(B / 2) % C] * [A^(B / 2) % C] * [A^(B % 2) % C] % C 2번 방식만 설명하면 될 것 같은데, A^B % C는 X * C + Y (X = 몫, Y = 나머지)로 나.. 2022. 11. 4.
[백준]1018번 체스판 다시 칠하기 by C++ https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 브루트 포스를 사용하는 문제였다. 브루트 포스 알고리즘은 어렵지 않아서 이 것을 이용해야 하는 것을 알면 쉬운데, 그게 아닐 경우 높은 확률로 시간 초과에 걸리기 때문에 항상 BFS, DFS인지를 고민하는데 시간을 많이 쓰게 된다. 전형적인 문제의 형식이 있는 것 같다고도 느껴져서 한 번 몰아서 풀어보면 좋을 것 같다. 핵심 변수 char expectedColor : 시작점의 값('B' o.. 2022. 10. 31.
[백준] 2146번 다리 만들기 by C++ https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 어렵지 않게 풀 수 있을 줄 알았는데, 생각보다 시간이 너무 걸렸다. 핵심 변수 qBuf - 1번째 BFS의 queue q - 2번째 BFS의 queue qSize - 2번째 BFS에서 각 시행 횟수 answer - 대륙간의 최단 거리 알고리즘 방식 전체적으로 2번의 BFS알고리즘을 사용하는데, 1번째 BFS 대륙에 번호를 매기고, pair vis 배열에 {1, 대륙 번호}를 입력하며, 각 좌표와 대륙.. 2022. 9. 13.
[백준] 11729번 하노이 탑 www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 재귀 문제중에 제일 많이 풀어본 문제가 아마 이 문제일 것 같다. 개인적으로 재귀라는 알고리즘 방식이 항상 관념적으로는 이해가 되는데 직관적으로 이해하기 어려운 느낌이 있다. 그렇다보니 알고리즘을 생각하는 과정에서 다른 방식보다 디버깅도 많이하게되고 결과를 보고 코드를 맞춰가는(?) 식으로 문제를 풀게 되는데 좋은 방향은 아닌 것 같아서 이 문제를 깊이있게 이해해보기로 했다. (이쪽 분야에 있으신 .. 2021. 3. 18.
[백준] 2573번 빙산 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS기반으로 알고리즘을 구성했다. 코드 완성해놓고 47번째줄에 board[cur.first][cur.second]를 board[i][j]라 써놓고 계속 디버깅하고있었다;; 처음 코드를 작성할 때 신경을 많이 써서 작성해야겠다. 변수 board - 빙산의 높이가 저장되는 배열 vis - 매년 빙산이 영향 받았는지 여부를 0, 1로 표현 q - 빙산의 좌표를 입력 (x, y) year - 매 시행이 몇 년째.. 2021. 3. 17.
[백준] 2493번 탑 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 이제는 방식을 외우긴 했는데 코드짜면서 깊게 생각하다보니 또 헷갈려서 포스팅한다. 언제쯤 익숙하게 외우려나... 휴... stack을 써야하는 이유 모든 탑에 대해서 높이를 입력받은 i번째의 탑을 기준으로 앞쪽으로 이동하며 더 높은 탑을 찾아도 되지만, O(N^2)의 시간복잡도를 가지게 된다. 하지만 이를 stack을 통해 구현할 경우, 탐색의 경우의 수를 비약적으로 줄여 시간에서 큰 이득을 볼 수 있다. 변.. 2021. 3. 17.

티스토리툴바