https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 0. 알고리즘 분류 수학 1. 문제 2. 풀이 처음엔 문제를 이해하지 못했지만, 그냥 단순히 N!의 약수 중 10의 개수를 세는 문제이다. 10 = 2 * 5이고, 2는 모든 짝수에 들어있으므로 상대적으로 적은 5의 개수만 세면, 10의 개수를 알 수 있다. 여기서 주의해야할 점이, 25 = 5 * 5이므로 5가 2개이다. 필자도 처음에 이걸 모르고 단순히 n/5로만 계산했다.. 3. 코드 #include using namespace std; int main(void) { int n..
https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 0. 알고리즘 분류 자료구조, 스택 1. 문제 2. 풀이 이게 왜 스택 문제인지 몰랐다. 언뜻 봐서는 배열만 써서도 풀릴 것 같았다. 풀리긴 하지만 문제는 시간복잡도가 O(n^2)으로 시간초과된다. 때문에 스택을 써야한다. 하지만 내 머리로는 도대체 어떻게 스택을 쓰면 시간복잡도를 줄일 수 있는지 생각해내지 못했다.. 구글링의 힘으로 풀었다. 코드가 짧아서 놀랐고, 이게 왜 풀리는지 이해를 못해서 놀랐다. 이해..
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 0. 알고리즘 분류 수학, 문자열, 그리디 알고리즘, 파싱 1. 문제 2. 풀이 문제를 처음 읽고 이해를 못했다. 괄호를 쳐서 최솟값을 만들어라. 그럼 괄호를 숫자 사이에 치면, 곱셈으로 봐도 되는건가? "55-50+40"을 "5(5-50)+40"으로 봐야하는건가? 근데 그러면 예제로 준 값과 다른데. 조건이 제대로 명시되어있지 않아서 조금 헷갈렸다. 위와 같은 괄호를 쳐서 곱셈을 하는 것은..
어차피 통과못할게 뻔해서, 1문제만 풀자고 생각했다. 그런데 웬걸. a번조차도 못 푼 내가 머저리다... a번: 친구들 DFS로 시도했다. 어떻게 구현할지는 대충 그려졌다. 막상 짜는건 조금 헤멨지만 해결했다. segmentation fault가 뜬다. 내 코드에서 이게 뜰 이유는 vector 밖에 없는데... 대체 뭐가 문제인가.. 결국 코드만 쳐다보다 a번도 풀지못하고 끝났다.. 문제가 어려운건지.. 내가 실력이 모자란건지.. 어쨌거나 확실한건 공부를 더 해야한다는 거다. 내년엔 좀만 더 해보자.
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 0. 알고리즘 분류 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 1. 문제 2. 풀이 이 문제는 두 함수로 풀 수 있다. 그래프를 돌며 해당 좌표의 상하좌우 0의 갯수에 비례하여 값을 깍는 melting 함수와 bfs를 돌면서 빙산 덩어리의 갯수를 카운트하는 func 함수. 여기까지 생각하는 것은 쉽다. 이제부터는 본인의 구현 능력에 달렸다. 필자는 자잘한 실수가 많..
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 0. 알고리즘 분류 수학, 분할 정복을 이용한 거듭제곱 1. 문제 2. 풀이 간단한 문제라고 생각했지만, 머리가 굳어서그런지 꽤나 어려웠다. 오버플로우가 일어나지않게 c로 나누는 건 쉬웠지만, a를 b번 곱하는게 문제였다. 일반적인 곱셈으로 풀면 시간초과가 뜬다. 따라서 a의 거듭제곱을 다시 곱하는 방법으로 시간을 줄여줘야한다. answer = n^k == (n ^ k/2) * 2 == ... k가 짝수일때는 앞과 같이 처리하면 되지만, 1보다 큰 홀수일때는 다..
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 0. 알고리즘 분류 그래프 이론, 그래프 탐색, 너비 우선 탐색 1. 문제 2. 풀이 BFS 문제이지만, 여태까지 풀었던 기본적인 문제와는 조금 다르다. 불과 사람에게 각각 BFS를 취해주어야 한다. 어려운 점은 같은 스텝에서 같이 BFS를 돌려야한다는 점이다. 나는 문제를 복잡하게 생각하는 바람에 푸는데 12시간이나 걸렸다... 불이 붙는 좌표를 우선적으로 BFS를 돌린 후, 사람..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 0. 알고리즘 분류 그래피 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 1. 문제 2. 풀이 문제 자체는 일반 DFS/BFS 문제이다. 적록색약은 그냥 주어진 입력에서 G를 R로 바꿔주기만 하면 된다. 다만 시간 제한이 1초라서, 반복문을 사용하는데에 생각을 해봐야한다. inArea() 함수는 입력으로 들어온 좌표 x, y 가 배열의 범위에 들어있는지 체크하는 함수이다. bfs(..
남자는 등으로 말한다고 했던가. 날개처럼 펼쳐지는 V-테이퍼의 역삼각형 등은 남자가 보기에도 엄청나게 멋있다. 그럼 키우지 않을 수가 없지. 많은 헬서들이 가슴운동으로 시작하는 월요일 루틴. 나는 무조건 등이다. 펌핑되서 힘이 쫙 들어간 V-테이퍼의 등은 정말 간지난다. 아직 체지방이 많아서 자랑할만한 몸은 아니지만. 이제 11개월 정도 운동을 했으니, 2년차쯤 되면 어디가서 운동 좀 했냐는 소리 좀 듣겠지.
이 글은 "[개정판]파이썬과 케라스로 배우는 강화학습"(https://book.naver.com/bookdb/book_detail.nhn?bid=16315117)을 참고하여 정리/작성하였습니다. 강화학습이란, 순차적으로 행동을 계속 결정해야 하는 문제를 푸는 것. MDP(Markov Decision Process)는 이런 문제를 수학적으로 표현한다. MDP의 구성요소는 "상태(State)", "행동(Action)", "보상 함수(Reward Fuction)", "상태 변환 확률", "할인율"이다. 상태는 "에이전트 자신이 처한 상황에 대한 관찰"이라고 할 수 있다. 행동은 말 그대로 어떤 상태에서 에이전트가 취할 수 있는 요소이다. 상태를 바꾸고 어떤 보상을 받을지 확률적으로 선택할 수 있다. 보상함수는..
