https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 알고리즘 수업에 나온 내용이 백준 문제에 있길래 풀어보았다. 우선 행과 열 값들을 저장해준다. 그런 다음 삼중 for문(O(n^3)) 을 이용해 값을 구해준다. 행렬곱셈의 순서는 다른 dp 문제들과 동일하다. 바텀 업으로 시작하여 값을 계산하고, 계산된 값을 저장한다. 그리고 그 계산된 값을 이용하여 답을 구하는 것이다. 행렬 곱셈순서를 구하기 위해서는 몇개를 곱할 것인지, 시작점은 ..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net bfs문제다. 근데 주의할 점은 물 -> 고슴도치 -> 물 -> 고슴도치 순으로 bfs를 진행해줘야 한다는 것! 먼저 물을 담고 있는 큐의 사이즈만큼 탐색을 진행한다. 그리고 고슴도치 위치를 담고 있는 큐의 사이즈만큼 탐색을 진행해주면 된다. 생각보다 간단한데, 이런 유형의 문제를 처음 푸는 분들은 조금 당황할 수도 있다. 왜냐?? 바로 큐의 사이즈만큼 탐색을 하기 때문이다. bfs문제에서 큐의 사이즈만큼..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 이 문제는 bfs에 구현을 섞은 문제이다. 총 3가지의 주요 로직으로 이루어져 있다. 1. 가장자리 입력부터 차근차근히 보자면, 입력을 받을 때 0행, 마지막 행, 첫 열, 마지막 열은 가장자리로써 상근이가 자유로이 접근할 수 있기 때문에 모두 큐에 넣어주자. 그러나! 가장자리에는 벽이 올 수도 있고, 문 또는 키, 그리고 빈칸 모두가 올 수 있다. 그러므로 입력을 받을 때 이들을 걸러주자. case1...
https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만-포드 알고리즘을 사용하는 문제이다. 그래프에서 음의 가중치가 등장한다면, 다익스트라로 해결할 수 없으므로 벨만-포드 알고리즘을 적용하자. 벨만 포드 알고리즘이란? 그래프의 최소비용을 구하는 알고리즘 중 하나로, "모든 경우의 수를 전부 탐색하여 최소비용을 찾는다." 자세히 말하자면, N개의 정점이 존재할 때 N-1번 탐색해야한..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 맨날 다익스트라나 bfs만 연습하다가 오랜만에 풀어본 dfs문제이다. dfs를 익히기에 아주 좋은 문제라고 생각되어 포스팅해본다! 크게 어렵지도 않아서 dfs에 능숙하지 않은 나같은 사람도 잘(?) 풀 수 있으리라 생각한다. 풀이 1. 우선, R x C 모양의 보드를 입력받아준다. 2. 그리고 0,0 위치(=시작 위치)도 말이 갈 수 있는 칸 중 하나로 친다고 하였으므로 해당 위치의 알파벳..
https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net 문제분석 누구나 쉽게 알 수 있는 오목게임이다. 구사과와 큐브러버는 10x10크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는데, 바둑판의 상태가 입력으로 주어지고 구사과가 턴을 한 번 더 가졌을 때, 즉, 한 수를 두었을 때 이길 수 있는지 구하는 프로그램을 작성해아한다. 오목의 승리 룰은 가로,세로 대각선 방향 중 하나에서 자신의 돌이 5개 이상 연속하는 것이다...
