1. 문제 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 2. 풀이 백준 골드 5의 브루트포스, 백 트래킹 문제이다. 생각보다 골드 문제라기보단 실버 2 ~ 1의 문제인 것 같고, 오히려 직전에 푼 마인크래프트가 더 어렵다고 느껴졌다... 이 문제를 풀 때 잡았던 핵심은 백 트래킹으로 빈 공간에 장애물을 설치한 후 선생님의 위치에서 상하좌우로 배열의 끝까지를 탐색하고 학생을 만나는지를 판단하는 것이다. 우선 주어진 입력을 변수와 배열..
1. 문제 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 2. 풀이 백준 실버 1에 해당하는 브루트포스 & 백트래킹 문제다. 알고리즘 스터디에서 발표할 때 이 문제를 들고 갔고 최적화 부분(재귀를 기존보다 덜 돌 수 있는 부분)에서 깨달음을 얻었다. 우리 스터디원들은 진짜 천재다...(나만 말하는 감자.....) 우선 이 문제의 해결 포인트로 생각한 건 백트래킹이었다. 팀원 수가 주어질 때 스타트팀..
1. 문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 2. 풀이 백준 실버 1에 해당하는 브루트포스, 백트래킹에 대한 문제이다. 브루트포스를 연습하려고 손을 댄 문제였지만, 백트래킹에서 한참을 고생하고 다시 개념부터 돌아가게 된 문제였다. 푸는 방법은 여러가지가 있겠지만, 필자는 여기서 다음과 같은 방법을 사용하였다. 우선 입력을 보면 부등호의 개수와 각 부등호가 주어진다. 이때 이 부등호와 숫자가 들어갈 수 있는 공간을 생각해보자. 부등호가 2개라면..
1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 풀이 백준 실버 1에 해당하는 문제이다. BFS를 너무 오랜만에 풀어서 그런지 쉬운 문제인데도 감을 잡는데 오래 걸렸다..(복습의 중요성..) 입력으로 주어지는 값을 저장한 후 BFS 함수를 실행한다. BFS 함수에서는 먼저 큐를 선언하고 현재 위치를 저장한다. (37줄) 그 후 큐가 비어있을 때까지 while 반복문을 돌면서 현재 큐의 사이즈만큼 for 반복문을 돈다. for 반복문 안에서는..
1. 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 풀이 백 트래킹 및 탐색을 이용하여 푸는 문제이다. 백 트래킹에 대한 내용이 기억이 나지 않아서 잘 정리된 블로그 포스팅을 참고하였고 다른분의 풀이를 참고하였다. https://iseunghan.tistory.com/241 알고리즘 - 백트래킹(Back-Tracking) 백트래킹 이란? 백트래킹은 모든 조합의 수를 살펴보지만, 조건이 만족할 때만 살펴보기 때문..
