컴공과고씨

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제를 보면 탐색 유형의 문제임을 알 수 있다. 보고 든 풀이 방법은 색칠 된 부분을 visit[][]에 방문 기록을 해 준 후 반복문을 통해 방문하지 않은 좌표를 bfs에 넣어준다. 그렇게 해서 bfs가 실행된 횟수가 나눠진 영역의 수이고 영역의 넓이는 bfs 함수를 구현 할 때 다음 좌표로 탐색할때 카운트를 해주고 bfs가 종료되었을 때 vector에 넣어 저장해주고 출력하..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음 보면 탐색 방법으로 풀어야겠다는 생각이 딱 든다. bfs를 이용해서 풀어보자! 일단 이 문제의 핵심은 벽을 1번 부술 수 있다. 그래서 나는 bool destory 변수를 두어 벽을 부수고 온 탐색인지 아닌지를 구분해 주었다. tuple을 사용하여 x좌표, y좌표, count, destory 이렇게 4개의 변수를 저장하여 큐에 넣어주는 식으로 구현하였다. 또 실수하지..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 일단 문제 제목에 나와있듯이 DFS 깊이 우선 탐색과 BFS 넓이 우선탐색을 구현 해주면 되는 문제이다. DFS의 쉽게 이해하자면 먼저 쭉쭉쭉 간다고 생각하면 편하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 무슨 말이냐면 위 표에서 1번에서 16번 가는 길을 찾으려고 할 때 DFS는 어떤식으로 탐색을 하냐면 일단 최대한 16까지 ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제를 처음 보고 위 보기에 있는 코드를 써서 카운트를 한다면 아마 시간초과가 날 것이다. 재귀 함수는 기본적으로 시간을 많이 쓰기 때문에... 그렇기에 다른 방법을 사용해야 하는데 나는 동적 계획법을 사용하여 풀었다. 동적 계획법은 이제 처음 연산은 기록해서 이미 했던 연산일 경우 연산을 하지않고 기록한 값을 가져오는 방식으로 위 문제를 재귀함수로 푸는 것 보다 훨씬 빠르다. 원리는 0 1 f(0) = 1번 0번 f(1) = 0번 1번 f(2) = f(0)의 0번 개수 + f(1)의 0번..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제를 보고 분할 정복을 사용해서 풀 수 있겠다는 생각이 들었다. 일단 분할 정복 같은 경우는 큰 문제를 작은 문제로 나눠서 푸는 방법이다. 지금 같은 경우 큰 정사각형에서 크기가 4인 정사각형까지 쪼개서 풀어주면 쉽다. 큰 정사각형은 4분할 해서 4개의 정사각형을 만들 수 있다. 그리고 조건문을 사용해서 4분면 중 위 순서대로 검사를 하여 구하고자하는 위치가 어디에 속해 있는지 확인해주..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net stack은 LIFO를 가지고 있기 때문에 이 규칙을 지켜서 문제 맞게 수행 해주면 된다. 내가 풀이 방법은 일단 스택이 있고 이 스택에는 미리 저장해놓은 원하는 수열 원소 크기와 비교해가면서 숫자를 순서대로 넣기 시작한다. 일단 원하는 원소 크기가 스택 top에 있는 숫자보다 크다면 원소 크기가 될때까지 숫자를 넣..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net queue를 이용하여서 풀 생각을 하였다. 해결 방식은 먼저 큐하나에는 우선 순위만 저장하고 다른 큐에는 pair를 이용하여 배열 번호와 우선 순위를 적어주었다. 그 다음 우선순위를 오름차순으로 sort를 한다. 그 후 정렬된 우선순위와 큐에 저장된 우선순위를 하나씩 비교하면서 정렬된 우선순위 보다 낮다면 뒤로 보내준다. 올바른 우선순위가 나오면 그 배열 번호를 결과 큐에 넣어준다. 결과 큐에 넣어주..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제를 읽었을 때 사용해야할 알고리즘이 떠오른것은 그래프 탐색이였다. 그 중 나는 넓이 우선 탐색 bfs를 선택해서 풀었다. 전체적인 풀이 방법은 배추가 있는 한 곳에 지렁이를 풀어준다. 그리고 그 지렁이가 인접해 있는 배추를 탐색하기 시작 한다. 이때 지렁이가 지나간 곳은 bool visit로 해서 방문했다는 표시를 해준다. 그리고 bfs가 끝나고 다른 배추 위치를 bfs에 넣어 지렁이를 다시 푸는데 이때 ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 일단 이 문제의 경우 이분 탐색을 사용하였다. 절단기를 높게 설정하면 잘리는 나무는 적어진다. 절단기를 낮게 설정하면 잘리는 나무는 커진다. 절단기 설정 높이를 이분탐색을 사용하여 구하면 된다. low는 0, high는 나무 길이의 최대값인 1,000,000으로 설정하고 이분탐색을 시작한다. 절단기의 설정 높이가 모든 나무길이보다 크게되면 의미가 없기 때문...

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제를 보면 카드가 FIFO 처음 들어간것이 먼저 나오는 구조를 가지고 있기 때문에 큐를 사용했다. 처음에는 POP을 사용하고 그 후 그 다음 숫자를 뒤로 넣어주는 구조로 구현 했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include using namespace std; int main(){ int n;..