백준 15686 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 전 나의 생각 이 문제를 처음 봤을 땐 BFS로 풀면 될 것이라고 생각했지만 생각을 정리하다 보니 결코 BFS로 풀면 안되는 문제였다. 만약 BFS로 진행하게 된다면 시간초과가 난다. 이유는 당연하게도 너무 많은 탐색을 진행하게 되기 때문이다. 또한 거리를 탐색할 수 있는 효율적인 계산식이 있는데 하나 씩 탐색하는 것은 굉장히 비효율 적이다. 그렇기 때문..
분류 전체보기
백준 18809https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두www.acmicpc.net 풀이 전 나의 생각 DFS와 BFS를 동시에 사용하여 풀 수있는 문제다. 초록색, 빨간색의 배양액을 뿌릴 수 있는 경우의 수를 모두 구해야 한다. 이는 DFS로 모든 경우의 수를 구하여 탐색이 가능하다. 이는 초록 배양액의 위치를 정한 후 빨간 배양액의 위치를 정하면 쉽게 구할 수 있다. 다음으로 배양액의 위치를 모두 정했으면 ..
백준 1941 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 전 나의 생각 우선 처음부터 BFS로 풀겠다고 접근하면 안된다. 왜냐하면 BFS는 자유로운 방향으로 'ㅜ' 나 'ㅏ' 의 방향처럼 퍼질 수는 있지만 역으로 다시 돌아와서 재탐색 하지 않는다. 그래서 모든 분기를 돌며 탐색을 진행하는 DFS와 같이 사용하면 쉽게 풀 수 있다. DFS는 학생들의 모든 조합을 찾기 위해 사용한다. 이유는 모든 조합을 구하면 모든 경우의 수를 구할 수 있..
백준 16987 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 전 나의 생각 백트래킹을 사용하여 풀 수 있는 문제지만 조건을 잘 걸어놔야만 정확한 결과를 얻을 수 있다. 우선 재귀함수가 어떤 방식으로 진행되야 할지 미리 파악해야 한다. 1. 계란의 내구도가 존재하여 다른 계란을 깰 수 있는 경우 2. 계란이 깨져서 더 이상 다른 계란을 깰 수 없는 경우 3. 계란의 내구도가 존재하지만 다른 계란이 다 깨져 있는 경우 이렇게..
백준 5427 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이 전 나의 생각 이 문제의 정답률이 굉장히 낮은 이유는 조건을 설정하는 과정에 있어서 정확한 판단을 할 수가 없기 때문이라고 생각한다. 우선 차근차근 문제를 알아보자. 문제의 요약은 사람이 불에 닿기 전에 탈출을 할 수 있냐 없냐다. 이를 판단하기 위해선 불과 사람이 동시에 움직이는 조건으로 진행해야 한다. 그러면 동시에 진행하는 것 처럼 코드를 제작하여 풀면 되는 것이다. 그 방법으로는 먼..
백준 7569 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 전 나의 생각 다른 토마토 문제는 2차원 BFS였는데 뭔가 똑같은 이름의 토마토 문제가 하나 더 있어서 클릭해 봤다. 비슷하긴 한데 축이 하나 더 늘었다. 여기서 굉장히 헷갈렸는데 보통 2차원 배열만 사용하지 3차원 까지는 거의 사용하지 않기 때문이다. 그래서 이 문제를 풀려면 우선 3차원 배열의 개념부터 잡고가야 한다. C++의 3차원 배열은 arr[z..
백준 1926https://www.acmicpc.net/problem/1926 1926번: 그림어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로www.acmicpc.net풀이 전 나의 생각 BFS를 사용할 수 있는지 없는지에 따라 성공, 실패가 나뉠정도로 BFS의 기초적인 내용을 묻는 문제다. 문제의 포인트는 그림이 있는 곳을 방문하여 그림의 개수와 그림의 최대 크기를 구하는 것이다. 1. 그림의 시작점을 방문 하기 위해 for문으로 탐색을 진행한다. 2. 시작점에 도착했다면 BFS를 진행하여 그림의 길이만큼 방문 표시를 해준다 3. 크기는 큐의 pop횟수, 개..
백준 1744 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 전 나의 생각 문제를 처음 봤을 때 그냥 최대값들만 곱해서 더하면 될 것이라고 생각했는데 자세히보니 아니다. 조건을 보면 -1000 ~ 1000의 크기를 가지는 수열이기 때문에 실버 문제보다는 조금 더 생각해야 할 필요가 있다. 음수, 0, 1, 양수 이 4가지를 가지고 조건을 만들어보면 1. 양수 * 양수 2. 음수 * 음수 3. 1이 나왔을 때 4. 0이 나왔을 때 이렇게..
