https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net kmp 알고리즘에 관한 문제이다. kmp 알고리즘이란, 문자열 패턴 매칭을 O(nm)이 아닌, O(n+m)에 해결할 수 있도록 해주는 문제이다. 이 알고리즘을 이해하기 위해서는, 접두사 접미사의 개념과 pi라고 칭한 이동경로 테이블을 왜 만드는지에 대한 이해가 필요하다. 이동경로 table은, 패턴의 부분 문자열(길이 1~원래 길이까지)마다 접두,접미사가 최대로 겹치는 길이를 저장해둔 tab..
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 알고리즘 수업에 나온 내용이 백준 문제에 있길래 풀어보았다. 우선 행과 열 값들을 저장해준다. 그런 다음 삼중 for문(O(n^3)) 을 이용해 값을 구해준다. 행렬곱셈의 순서는 다른 dp 문제들과 동일하다. 바텀 업으로 시작하여 값을 계산하고, 계산된 값을 저장한다. 그리고 그 계산된 값을 이용하여 답을 구하는 것이다. 행렬 곱셈순서를 구하기 위해서는 몇개를 곱할 것인지, 시작점은 ..
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 이 문제.. 분명 맞게 푼 것 같은데 자꾸 시간초과가 나시는 분들이 있을 것이다. 아래 코드를 보자 if (nx = n || ny = m) continue; // 이미 방문한 경우 if (visited[nx][ny][wall]) continue; if (board[nx][ny] == 0) { q.push({nx,ny,ans..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 구현 + bfs 문제라서 조금 까다로웠다. 보통 구현, 시뮬레이션 이쪽 문제들은 꼼꼼히 읽고 자잘하게 챙겨줘야하는 것들이 많으니 유의하시길 바란다! 우선, 원소 하나하나에 대해 bfs를 해준다. bfs에 들어가기 전에 연합 정보를 저장할 벡터를 이용해 벡터에 탐색을 '시작하는' 곳의 좌표를 넣어주고, 연합의 인구 수를 계산할 변수인 sum에 현재 나라의 인구 수를 저장해준다. bfs..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 이 문제는 bfs에 구현을 섞은 문제이다. 총 3가지의 주요 로직으로 이루어져 있다. 1. 가장자리 입력부터 차근차근히 보자면, 입력을 받을 때 0행, 마지막 행, 첫 열, 마지막 열은 가장자리로써 상근이가 자유로이 접근할 수 있기 때문에 모두 큐에 넣어주자. 그러나! 가장자리에는 벽이 올 수도 있고, 문 또는 키, 그리고 빈칸 모두가 올 수 있다. 그러므로 입력을 받을 때 이들을 걸러주자. case1...
https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 이 문제는 bfs 기본코드에서 약간의 응용이 필요하다. 우선 갈 수 있는 방향이 1.상 2.하 3.좌 4.우 5.좌상 6.우상 7.좌하 8.우하 9.제자리 로 총 9가지다. 그리고 벽이 1초에 한 줄씩 내려온다고 하였으므로, 1초마다 벽의 위치를 움직여줘야한다. 0,0에서 부터 for문을 시작하면 벽을 내리고, 내린 벽과 기존 벽을 구분하기 어려우므로 밑에서부터 for문을 시작하여 ..
