Doby's Lab

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 노트에 구현을 해보았다. 시작 수가 0이면 안 되기 때문에 1 ~ 9까지 수들을 각 수로부터 파생될 수 있는 수들을 트리 형식으로 그려볼 수 있었다. 다음과 같은 특징을 지니고 있었다. 시작 수는 0이 될 수 없다. 1 ~ 8까지는 두 가지의 수가 파생될 수 있다. 0과 9는 각각 1, 8 밖에 파생시키지 못한다. 이러한 관계식을 어떻게 나타낼 수 있을까 한참을 고민하다가 2차원 배열을 떠올렸다. cache[i번째 자리][숫자 j] = 숫자 j가 나온 횟수; 다음 계단식의 특징을 가지고서 점화식을 나타내면 //..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 여전히 DP 문제는 접근하기 어렵다. 문제를 풀 때마다 '이렇게 생각해보자'라는 지난 DP 문제로부터 나름대로 얻은 팁을 적용해봐도 어렵다. 이제까지 접근했던 방식들을 떠올려보면 직접 TC를 가지고서 output을 노트에 도출하며 관계성과 점화식을 세웠었다. [input] 6 6 10 13 9 8 1 [answer] 33 맨 처음에는 조금 멍청하게 접근을 했는데 n번째 포도주를 선택한다고 했을 때,..

현재 값을 중심으로 생각 (점화식 세울 때 까다로워짐) 일부분을 캐치하는 능력 (연속 3번은 안 된다 했을 때, '0번, 1번, 2번 연속을 알아봐야겠다'라고 생각이 드는 능력) 점진적으로 문제를 해결할 수 있다는 걸 항상 암시하기 어떠한 조건들을 따져야 할지 캐치하는 능력 DP를 훌륭하게 푸는 법 (https://debuglog.tistory.com/80)

https://www.acmicpc.net/problem/23628 23628번: 악마의 연차 계산기 360일 일하면, 휴가를 받아야 함이 마땅하다. 그에 따라, 우리 회사도 연차와 월차를 주고자 한다. 연차와 월차는 사용하면 하루 쉴 수 있는 것이다. 그런데, 인력이 너무 부족한 탓에 그만…. 지 www.acmicpc.net 처음엔 많은 조건 분기로 풀었으나 이는 너무 복잡한 코드였다. #include using namespace std; int main() { int y, m, d; int dy, dm, dd; cin >> y >> m >> d; cin >> dy >> dm >> dd; int year = 0; int month = 0; int days = 0; if (dy == y) { if (dm..

https://www.acmicpc.net/problem/1990 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 솔루션 1) 에라토스테네스의 체를 통해 입력받은 b보다 작거나 같은 소수들을 구한다. 2) a와 b 사이의 범위를 만족시키기 위해 이분 탐색을 통해 시작과 끝 범위를 찾는다. 3) bool 타입의 팰린드롬 판별 함수를 통해 소수 중에 팰린드롬을 찾는다. 4) -1 출력, 종료 >> 다음 솔루션은 메모리 초과 발생 >> 게시판 질문 글에서 10,000,000을 넘어가는 팰린드롬인 소수는..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 이번 문제는 학교에서 자료구조 과제로 나왔던 키워드이지만 그 당시에 안 했어서 이번 기회에 구현을 해보려 했다. 솔루션 [1] 식을 문자열로 받아서 피연산자인지 연산자인지 구분을 한다. [2] 연산자나 괄호를 스택에 우선순위로 처리해야 하는 *, / 의 조건과 +, -의 조건, (, ) 두 괄호의 조건을 따로따로 처리를 해줘야 한다. A+B*C 다음 경우를 예로 들어보자. 답으로는 ABC+*가..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음엔 BFS를 돌려서 큐에다가 현재의 위치와 벽을 부술 수 있는지에 대한 힘의 여부를 담았다. 그리고, 한번 방문했다면 방문할 수 없게끔 했다. (무한 루프 방지) [처음 코드] #include #include #include #include using namespace std; int n, m; int map[1001][1001] = { 0, }; int temp[10..

https://draw-code-boy.tistory.com/101 [알고리즘] 백준 2407번: 조합 (C++), Combination, Permutation https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 이번 문제는 (https://jaimemin.tistory.com/682)을 참고한다. 개념 학생.. draw-code-boy.tistory.com 이 문제를 풀면서 솔루션을 참고하다가 공부하게 된 내용이다. 우선 &를 쓴다는 점에서 포인터라고 생각했지만 전혀 다른 개념을 사용된다. 변수의 의미는 '메모리 공간에 이름을 붙인 것'이다. 참조자는 똑같은 메..