과제 제출마감 10분전

Array (배열) 같은 자료형에 대한 자료들을 메모리에 연속적으로 저장하기 위해 사용된다. 물리적 저장 순서와 논리적 저장 순서가 일치하는 특징이 있다. 선언되면 컴파일 타임에 할당할 사이즈를 미리 정해놓고 정적 메모리를 할당함 ➡ 크기가 미리 정해지며, 사이즈 변경이 힘듦 index를 통한 random access가 가능하다. (이는 배열의 원소들이 연속된 메모리 위치에 저장되기 때문임) 크기 : 자료형에 대한 메모리 할당 크기 * 배열 요소의 개수 삽입 : O(N) 삭제 : O(N) 탐색 : O(1) ▶ 삽입/삭제 시에는 해당 원소를 삭제한 뒤, 다른 원소들의 조정이 필요하기 때문에 worst case가 O(N)이 됨 배열을 사용하기 좋은 경우 데이터의 개수가 정해져 있다 데이터 탐색을 할 일이 많..

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

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

백준 문제를 풀다가 메모리 초과가 발생했다. 이 문제를 풀면서, string의 끝에서부터 연산을 하면서 구한 값들을 그 역순(다시 string의 원래 순서대로)으로 출력할 일이 있었는데, 이때 별도의 공간에 저장하지 않고 풀기 위해서 재귀함수를 이용했었다. 하지만 문제를 제출한 뒤, 메모리 초과가 발생했다. 왜일까 생각해 보니 위의 재귀함수에서 string input_string부분이 눈이 갔다. 재귀함수를 사용하면서 문자열 길이가 조금이라도 길어진다면 재귀함수의 매 호출마다 그 긴 문자열을 복사해서 사용했기 때문에 메모리가 초과된 것이다. 나는 그래도 재귀함수를 사용하는 방법으로 문제를 풀고 싶어서 string을 (포인터 같이?) 매번 복사하는 것이 아닌 참조 자체를 보낼 수는 없을까 찾아보았다. 검색..

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