과제 제출마감 10분전

코테 전에 보고 갈것들 1. 자주 사용하는 STL의 함수들 기억 string ▪ 문자열 일부분 잘라내기 - substr s.substr(index, 개수) ▪ 문자열에서 특정 문자 찾기 - find s.find("찾으려는 문자열") -> 찾으려는 문자열이 등장하는 첫 번째 인덱스를 리턴해줌 vector vector 2. 형변환 방법 기억 형변환 가끔씩 까먹을 때 있음 string ↔ int string result = to_string(int); int result = stoi(string); (#include 필요) string ↔ char (잘안나오는듯) string result = ""; result.push_back(char); char result = int ↔ char int result = ..

백준 문제 풀이 [백준] 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