https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 기본적인 bfs문제에 약간의 테크닉을 요구하는 문제이다. 우선 C가 두개 주어지므로 그냥 먼저 나오는 C를 시작점이라고 치고, 늦게 나오는 C를 도착점이라 친다. 그리고 시작점을 큐에 넣고 bfs를 시작하는데, 큐의 맨 앞에 것을 가져와서 4가지 방향을 탐색하는 건 기존 bfs와 동일하다. 그러나 여기서 레이저의 특징을 이용해야한다! 레이저는 한 방향으로만 직진하므로, while문을 통해..
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 매번 입력마다 정렬해서 가운데 값을 출력하면 시간초과가 난다ㅜㅜ 0.1초안에 해결해야하는데, 최대 입력이 100,000이므로 O(N^2)으로는 해결할 수 없다는 뜻이다. 이 문제는 2개의 우선순위 큐를 활용하면 되는데, 활용조건은 다음과 같다. 1. 최소 힙의 값들은 모두 최대 힙보다 커야한다. 2. 최대 힙의 크기가 최소 힙의 크기보다 1보다 크거나 같도록 유지한다. 3. 최..
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 얼핏보면 그냥 행렬 곱을 반복해주면 되는거 아닌가? 싶을 수도 있다. 하지만! 최대 천억제곱까지 주어지므로 O(N)에는 해결할 수 없다! 때문에 빠른 거듭제곱 알고리즘을 사용해야한다. 즉, N이 홀수일 땐 밑을 하나 꺼내서 N을 짝수로 만든다. N이 짝수일 땐 밑을 제곱하고 N을 2로 나눈다. 그럼 어떻게 이 문제를 풀어야할까? 우선 행렬곱을 해주는 함수를 하나 만든다. 배열을 파라미터로 넘길 땐 주소가 넘..
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/19948 19948번: 음유시인 영재 감수성이 뛰어난 음유시인 영재는 일상생활 중에 번뜩 시상이 떠오르곤 한다. 하지만 기억력이 좋지 못한 영재는 시상이 떠오르면 그 순간 컴퓨터로 기록해야만 안 까먹는다! 시는 대문자, 소 www.acmicpc.net 이 문제.. 약 10번의 시도 끝에 겨우 풀었다. C++를 이용한 답안 코드가 없길래 혹시 누군가 필요할까 싶어 글을 적게 되었다. 우선 문제를 꼼꼼히 읽자..! 자신과 똑같은 것이 다음에 오면 2번이 아니라 1번으로 친다는 것을 읽지못하고 좀 오래 헤매었다. 그리고, 주어진 키보드로 제목까지 입력할 수 있어야한다. 문제 풀이 우선 입력들을 다 받자 제목이 되는 문자들을 다 저장한다. 원하..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제분석 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력..
