9월 11일 토요일 14:00 ~ 19:00, 7문항, 5시간. 1번 문항은, 19년도 출제된 오픈 채팅방 문제랑 거의 유사했다. (https://programmers.co.kr/learn/courses/30/lessons/42888) 배열, 해시 테이블 등을 이용한 문자열 처리 문제. (구현 문제라 보면 된다.) 2번 문항은, 10진수 -> N 진수 변환 후 문제에서 주어진 조건에 맞게 소수를 찾는 문제였다. 즉, 10진수 -> N진수 변환 + 소수 판별 + 기초 구현(주어진 조건을 처리) + 탐색 의 끔찍한 혼종 문제가 나와버렸다. 3번 문항은, 주차장에서 차가 들어온 시간에 따라 요금을 계산하는 문제였다. 역시 구현 문제. 18년도 셔틀 버스 문제랑 비슷한 느낌.(https://programmers..

스도쿠 (골 4) : https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠는 내가 정말 좋아했던 게임이다. 에버랜드 알바하던 시절에 쉬는 시간 틈만 나면 폰으로 스도쿠 했을 만큼 좋아했다. 스도쿠를 하면서 가장 힘들었던 유형은, 노가다로 숫자를 하나씩 집어 넣어 중복되는게 없는지 일일이 다 확인해야 하는 경우가 많은 문제였다. 이 문제는 그 노가다 과정을, 고스란히 코드로 옮기는 문제이다. 접근 방법은 다음과 같다. 1. 빈 칸에 숫자 1을 ..

Two Dots (골 4) : https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net DFS 를 이용, 주어진 좌표가 사이클을 이루는지 확인하면 된다. visited 배열/해쉬 테이블/set을 이용하여 이미 한번 왔다간 좌표를 재방문할 시 true, 아니면 false를 반환하면 된다. C++은 visited로 set을 사용, 자바는 일반 벡터를 사용하였다. HastSet을 사용하여 했으나, HashSet 클래스의 Contains 메서드는 값을..

드래곤커브 (골4, 구현/시뮬레이션) : https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 구현 문제 중 특히 시뮬레이션 문제는 프라모델 조립하듯이 단계별로 나눠 풀면 된다. 큰 하나의 기능을 작은 세부적인 기능들로 나눈 다음, 조립해서 끼워 맞추듯 하나하나 구현한다음 합치면 된다. #include #include #include #include using namespace std; int N, map[101][101]..

RGB 거리 (실 1) : https://www.acmicpc.net/problem/1149 N개의 집이 주어지고 각 집을 세 가지 색깔로 칠할 시, (단, 색깔은 이전 집을 칠한 색깔과 동일하면 안된다) 모든 집을 칠하는 비용의 최솟값을 구하는 문제. 1. 문제 분석 모든 집을 칠하는 최솟값을 구하는 문제이니, 최적화 문제. 1. 그리디한 접근이 가능한가? 각 선택에 대하여 최솟값만을 선택한다고 했을 시, 정답이 된다는 보장이 없다. 반례도 충분하다. 따라서, 칠하는 경우의 수와 최솟값를 하나하나 계산해봐야 한다. 2. 최적 부분 구조인가? yes. 이전 선택에 관계없이, 각 부분 문제를 최적으로 풀었을 시 전체의 해답이 나옴. DP 식을 도출해보면 알 수 있음. 집 칠하는 비용의 최솟값을 리턴하는 함..

1, 2, 3 더하기 3 (실 2) : https://www.acmicpc.net/problem/15988 재귀문제인 1, 2, 3 더하기 문제(https://sanghoonly.tistory.com/21)를, DP를 활용하여 메모이제이션을 적용한 문제 및 코드이다. 이전 문제는 n의 범위가 작아서 단순 재귀 호출로 충분히 풀 수 있었지만, 이 문제의 경우는 n이 1000000이하로 급격하게 커지니 메모이제이션은 필수이다. 또한 n이 커짐에 따라 정답도 급격하게 증가하니, 정수 범위에 조심할 것!! #include #include #include using namespace std; long long cache[1000001]; long long recur(long long n) { long long &..

가장 긴 증가하는 부분 수열 (실 2) : https://www.acmicpc.net/problem/11053 가장 긴 증가하는 부분 수열 4 (골 4) :https://www.acmicpc.net/problem/14002 DP에 관하여 워낙 유명한 문제. 여기서는 LIS를 실제로 출력하는 코드를 위주로 살펴본다. 1. (일반적인) 최대 증가 부분 수열의 길이 반환 #include #include #include using namespace std; int N, A[1001], cache[1001]; int lis(int start) { int &ret = cache[start + 1]; if (ret != -1) return ret; ret = 1; for (int i = start + 1; N > i..

1. 재귀 호출의 각 단계에서 최적해를 만들었던 선택을, 별도의 배열에다 저장. 2. 별도의 재귀 함수를 구현해 이 선택을 따라가며 각 선택지를 저장하거나 출력. 예) LIS에서 LIS 복원하기 : https://sanghoonly.tistory.com/45 -> 1. 최적 선택을 기록하는 choices 배열 생성 후, 2. reconstruct 함수로 choices함수의 값을 이용해 lis 복원.