판교의 메타몽

링크 : www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 그다지 어렵지 않지만, 좌표를 받는 부분에서 반복적으로 실수를 냈다. #include #include #include using namespace std; int m = 0, n = 0, k = 0, my = 0, mx = 0 ,width = 0; bool ch[102][102] = { false, }; int yy[4] = { 0,1,0,-1 }; int xx[4] = { 1,0,..

링크 : www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net #include using namespace std; int max(int a, int b) { return a > b ? a : b; } int arr[100001]; int sum[100001]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int n = 0, maxi = 0; cin >> n; for (int i = 0; i < n; ..

링크 : www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 영문명 'Longest Increaseing Subsequence (LIS)'로 잘 알려진 문제이다. #include #include #define MAX 1001 using namespace std; int arr[MAX], sum[MAX], n = 0, ans = 1; int main() { ios_base::..

링크 : www.acmicpc.net/problem/21562156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net이 문제는 크게 2가지의 조건을 고려하여 최대값을 구해야한다. 1. i번째 음료를 마시는 경우 (1) i번째 음료 / i-3번째까지의 음료 중 큰 합산 값 / i-1번째 음료 (2) i번째 음료 / i-2번째까지의 음료중 큰 합산 값 2. i번째 음료를 마시지 않은 경우 (1) 1번에서 최대값과 i번째 직전의 음료와 값을 비교한다. 위의 그림이 이해가 되지 않는다면, 아래 테스트 케이스가 통과되는지 확인해보자...

링크 : www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 매우 어려운 논리를 요구하는 DP문제는 아니였다. 하지만 Over flow를 방지하기 위해 계산마다 1,000,000,000을 나눠주는 점을 놓쳐서 오답이 나와버렸다. #include #include #include using namespace std; long long int arr[101][11]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); long long int ans = 0; int n = 0; cin >> n; for (int i ..

링크 : programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 분류 : 해시 해시의 개념을 모르고 있었기에, 최대한 아는 개념을 동원해 vector로 문제를 풀려했다. 채점 후 몇몇 테스트 케이스에서 실패가 나고 코드가 점점 길어지자 다른 문제 해결 방법이 필요하다는 것을 깨달았다. map이라는 개념을 파악한 뒤, 해당 개념을 통해 문제를 접근했다. #include #include #include #include using namespace std; int solution(vector clothes) { int answer = 1; map map1; for (int i = 0; i < clothes.size(); ..

map Key와 Value를 쌍으로 자료를 보관하는 컨테이너. map은 자료를 저장할 때 내부에서 자동 정렬을 하고, hash_map은 정렬하지 않는다. 레드 블랙 트리 자료구조를 사용하며, 작은 값은 왼쪽 서브트리, 큰 값은 오른쪽 서브트리에 저장한다. (오름차순) 따라서 정렬이 필요하지 않은 곳에서 hash_map을 사용하는 것은 메모리 낭비이다. STL로 map과 iterator를 추가해야 한다. map 변수명 (ex : map map1 ) 맵 생성 변수명.size() (ex : map1.size() ) 맵의 사이즈 반환 변수명.empty() (ex : map1.empty() ) 맵이 비어있으면 1(true), 아니면 0(false)를 출력 insert 방법 1 : 변수명[key] = value (..

링크 : programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 �� programmers.co.kr 분류 : 완전탐색 혹시 이 문제를 풀었는데 테스트케이스 4번, 6번, 7번을 틀린 사람은 아래의 예시를 테스트 케이스로 추가해보자. 입력값 : Brown 50, Yellow 20 출력값 : [24, 3] #include #include using namespace std; vector solution(int brown, int yellow) { vector ..

링크 : programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 분류 : 깊이/너비 우선 탐색 (DFS/BFS) 이 문제는 제한사항들 중에서 서로 충돌하는 포인트가 있다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return합니다. 주어진 항공권은 모두 사용해야 합니다. 이 두 조건을 동시에 고려하지 않고 문제를 풀면 아래와 같은 예시에서 충돌이 발생한다. 입력값 : [["ICN", "AAA"], ["AAA", "CCC"], [..

#include #include #include using namespace std; string solution(string s) { string answer = "", temp = ""; int mini = INT_MAX, maxi = INT_MIN, temp2 = 0; bool ch = false; for(int i=0; itemp2) mini = temp2; if(maxi