과제 제출마감 10분전

백준 문제 풀이 [백준] 9205. 맥주 마시면서 걸어가기 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제 해석 & 접근 방법 출발지에서 50m씩 움직일 때마다 맥주 한 병이 필요하다. 맥주는 총 20개를 들고 있을 수 있고, 편의점에 도착할 경우에는 맥주가 20개로 리필된다. 출발지, 편의점들, 도착지의 좌표가 주어질 때 맥주가 다 떨어지지 않고 도착할 수 있는지 여부를 구하는 문제이다. 처음에는 BFS로 풀려고 접근했지만 플로이드 워셜 알고리즘을 이용하면 문제가 간단해질 것 같아 해당 알고리즘을..

플로이드 워셜 (Floyd Warshall) 알고리즘 두 점의 최단 거리를 구하기 위한 알고리즘 특히, 모든 정점 사이의 최단 거리를 구할 필요가 있을 때 사용하는 알고리즘이다. 그 이유는 알고리즘 수행 시 모든 정점 사이 최단 거리를 계산하며 사이에 있는 정점을 통해 최단 거리를 개선해 나가기 때문! 시간 복잡도 O(N^3) 과정 다음 그래프가 주어졌을 때, 플로이드 워셜 알고리즘을 수행하는 과정은 다음과 같다. 1. 먼저 모든 정점에서 다른 정점으로 (다른 점을 거치치 않고!) 바로 갈 수 있는 거리를 구한다. 1 2 3 4 5 1 0 ∞ 1 ∞ 5 2 3 0 9 2 ∞ 3 4 4 0 ∞ ∞ 4 ∞ 8 6 0 ∞ 5 ∞ ∞ ∞ 2 0 2. 그 후, 모든 정점에 대해 순회하며 해당 정점을 거쳤을 때의 ..

백준 문제 풀이 [백준] 16918. 봄버맨 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 문제 해석 및 접근 방법 처음 폭탄을 설치하고, 2초에 빈 칸들에 새롭게 폭탄을 설치한다. 그 후 3초째에는 처음 설치한 폭탄이 폭발하고 4초째에 폭발한 자리가 비었으므로 다시 새로운 폭탄을 설치한다. 다음과 같은 패턴이 반복됨을 알 수 있다 폭탄은 3초 뒤에 폭발하고, 폭발 시에는 연쇄 반응 없이 상하좌우 4개를 같이 폭발시킨다. 따라서 처음 상태가 주어졌을 때, N초가 지난 후의 격자판 상태를 구하려 하는 문제이다. 처음 폭탄이 주어..

백준 문제 풀이 [백준] 7569. 토마토 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 해석 7576. 토마토 문제에서 z축이 추가된 문제이다. BFS를 사용해서 풀 수 있다. 토마토가 보관된 상자의 x y z 크기가 주어지고, 입력으로 토마토의 정보가 주어진다. 1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 없는 칸이다. 또한 토마토가 무조건 하나 이상 있는 경우만 입력으로 주어진다고 했다. 이 때 토마토가 모두 익는 데 며칠이 걸리는지를 답으로 출력하면 ..

백준 문제 풀이 [백준] 1759. 암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 해석 입력으로 L,C가 주어지고, C개의 문자들이 주어진다. 이 중 L개를 골라서 최소 한 개의 모음과 두 개의 자음으로 이루어진 암호를 모두 출력하는 문제이다. 풀이 이 문제는 순열을 이용해서 모든 경우를 다 구하면서 조건에 맞는 것만 출력해 주는 식으로 풀었다. // 1. 입력받는 부분 int input_l, input_c;// 3> input_c; for (int i = 0; i < input_c; i++) ..

백준 문제 풀이 [백준] 15663. N과 M(9) 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 15654. N과 M(5) 문제와 비슷한 문제이다. 역시 브루트 포스를 통해 해결했다. 다른 점은 예제의 입력을 보면 15654번 문제와 다르게 주어진 자연수가 중복된 숫자가 올 수 있다는 것. 즉 1824 이런 숫자만 주어지는 것이 아닌 1118 이렇게 1이 여러 번 있는 자연수의 입력도 주어질 수 있다는 것이다. 출력의 조건을 보면 중복되는 수열을 여러 번 출력하면 안 된다. 그러므로 N과 M(5..

s.at(i) → s[i] s.at(i)는 범위 체크가 있으나 s[i]는 없음 s.push_back('a') → s += "a"; 여러 글자 추가할 때에는 s+="qwer"로 추가하는 것이 좋음 s1 == s2 → s1.compare(s2) == 0 s1과 s2를 비교할 때, compare를 사용하는 것이 더 빠름 compare함수는 s1과 s2을 비교하면서 s1이 더 길이가 짧거나, s2과 처음으로 다른 글자가 더 작은 글자(a

알고리즘 문제를 C++로 풀면서 Visual Studio를 사용했는데, 한 프로젝트에 여러개의 cpp파일을 생성해서 문제를 풀곤 함. 이러다 보면 소스 파일이 엄청나게 많아지고, 실행해볼 때 다른 것까지 같이 실행되면서 main함수를 빼거나 함수 이름을 바꾸어서 원하는 파일 빼고는 실행되지 않게 하곤 했음 근데 그것보다 간단하게 쓰는 방법이 있어서 적어둠!! 1. 다 푼 문제와 같이 실행을 원하지 않는 cpp파일을 오른쪽 우클릭 -> 속성 2. 속성에서 일반 -> 빌드에서 제외 "예" 3. 실행 및 디버깅 시 그 파일은 제외됨 이 방법을 통해 더 편하게 원하는 파일을 실행할 수 있음!! 간단하고 나중에 해제할때도 뭘 고칠 필요가 없어서 좋은 것 같음ㅎㅎ