겜돌이의 개발일지

문제 백준 14226 이모티콘 C++ 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 방문 체크를 2차원 배열로 해주는 색다른 문제였습니다. 할 수 있는 행동은 3가지입니다. 1. 화면에 있는 이모티콘 개수만큼 클립보드에 저장하기 2. 클립보드에 있는 이모티콘 개수만큼 화면에 붙여 넣기 3. 화면에 있는 이모티콘 1개 삭제하기 bfs를 돌면서 이모티콘 개수가 일치하지 않을 때 다음 3개에 행동을 모두 queue에 push 해 줍니다. 방문 체크는 [화면 이모티콘 개수][클립보드 이모티콘 개수]로 해줍니다. ..

개요 함수 오버로딩(Function overlaoding) : C#, C++, 자바 등에서의 함수의 특징. 같은 함수 이름을 가지고 있으나 매개변수, 리턴타입 등의 특징은 다른 여러개의 서브프로그램 생성을 가능하게 한다. 조건 다음 중 하나를 만족해야 한다. 1. 매개변수의 자료형이 달라야 한다. 2. 매개변수의 개수가 달라야 한다. 주의점 1. 반환타입은 오버로딩에서 고려되지 않는다. 2. 모호한 함수가 있을 경우 컴파일 에러가 발생한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; void print(unsigned int value) { cout

문제 백준 2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 풀이 먼저 LIS (최장 증가 부분 수열)을 구합니다. LIS에 해당하지 않은 원소를 옮겨주면 되므로 n-LIS가 답이 됩니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include using namespace std; int dp[201]; int main() {..

문제 백준 2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 두 포인터를 사용합니다. 먼저 입력을 받아 오름차순으로 정렬합니다. 합이 0에 가까워져야 하므로, 합이 양수일 때는 right를 왼쪽으로 옮겨 합을 감소시키고 합이 음수일 때는 left를 오른쪽으로 이동시켜 합을 증가시킵니다. 합의 절댓값이 최솟값보다 작다면 갱신해주고 target에 저장합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..

문제 백준 15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 백트래킹을 통해 폐업하지 않을 치킨집을 선정합니다. M개만큼 선정했다면, 브루트 포스를 통해 최소 거리를 갱신해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57..

명백한 호출의 괄호 앞에 오는 식에는 함수 (포인터) 형식이 있어야 합니다 vector를 사용하다가 떴던 오류. 구글링 해보니 내장 함수의 이름과 변수의 이름이 똑같아서라는데... v라는 내장 함수가 있을 리는 없고 알고 보니 v[0].first자체가 변수기 때문에 괄호를 붙여주지 말고 사용해야 했다. 괄호를 제거해주면 잘 출력된다. 내장함수와 이름이 겹치는 변수를 사용할 때 뜨는 오류와 동일하다. 위의 경우에는 algorithm.h 안에 max라는 내장 함수가 있어 max라는 변수를 사용할 수 없다 int max를 _max 등으로 바꾸어주면 된다.

문제 백준 11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 nCr = n * (n -1) * (n-2) * ... * (n-r+1) / r! 이지만 n과 r이 커지면 오버플로우가 발생합니다. 따라서 파스칼의 법칙을 사용하여 dp로 해결합니다. 위 그림을 보면 nCr에서 r이 0이거나, n = r일 때는 1, 나머지 경우에는 nCr = n-1Cr-1 + n-1Cr 입니다. 1C0과 1C1의 초기값을 설정해주고 dp를 이용해 nCk을 구합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 백준 5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 현재 위치와 이동 횟수를 저장하는 queue를 선언합니다. 위로 올라갈 수 있을 때, 아래로 내려갈 수 있을 때 queue에 push 해주며 bfs를 실행합니다. 현재 위치가 G와 같다면 이동 횟수를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include..

문제 백준 11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 [i, j]에서 [i+1, j], [i][j+1], [i+1][j+1]로 이동할 수 있습니다. [i+1][j+1]은 어차피 [i+1, j], [i][j+1]를 거쳐 이동할 수 있으므로 고려하지 않아도 됩니다. (돌아서 갈 때 얻는 사탕이 무조건 크거나 같습니다.) 따라서 dp[i]j[j]에는 dp[i-1][j], dp[i][j-1] 중 더 큰 값에 map[i][j]를 더해준 값을 넣습니다. 소스 코드 1 2 3 4 5 6 ..

문제 백준 1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 해당 영역에서 가장 큰 길이를 계산해 담고 있는 dp 배열을 이용합니다. 먼저 0열과 0행에는 입력값과 똑같은 값을 넣어줍니다. 0열과 0행을 제외하고, 해당 칸의 입력이 0이라면, 어짜피 사각형의 길이는 0이 되므로 dp에 0을 넣어줍니다. 1이라면 왼쪽, 위쪽, 왼쪽 위 3가지 값을 탐색하면서 dp 값을 구합니다. dp값과 최대 길이 값을 비교하여 최댓값을 갱신합니다. 예제를 보겠습니다. square 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 dp 0 1 0 0 0 1 0 0 0 0 0행과..