D cron

문제 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 왜 틀렸을까? 이 문제에 어떻게 DP를 적용할지 생각이 나지 않았다. 그리고 다른사람의 풀이도 보고 설명도 많이 들었지만 과정이 명확하게 이해가 되지 않았다. 나처럼 동전이 도저히 이해가 되지 않았던 사람을 위해 최대한 친절하게 풀어서 설명해보려고 한다. 문제 풀이 방식 많은 분들이 1차원 dp를 사용해서 풀었는데, 나는 1차원 dp table를 사용하는 방식으로는 이해가 잘..

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 왜 틀렸을까? 이 문제를 풀기 전에는 이차원 배열에서 0과 1을 통해 board[1][3] 이면 1에서 3을 갈 수 있다는 식으로 연결 상태를 나타냈었는데, 이 문제는 노드의 개수가 최대 100,000개 이므로 이차원 배열에서 연결상태를 표시하게 되면 10만*10만 = 100억개의 칸을 사용하기 때문에 메모리 초과가 날 수 밖에 없다. # 원래 알던 이차원배열에 모두 저장하는 방식 board = [[0]*(n+1) for i in range(n+1)] f..

📷 회고 이번 주차 역시 알고리즘 주였고 키워드는 그래프, BFS. DFS, 위상정렬이었다. 모르는 개념들은 나동빈 형님의 강의를 듣고 정리하고, 문제를 풀어보는 식으로 진행했고 1시간정도 고민하다가 모르겠으면 답을 보고 이해하고, 다시 한번 풀어보는 식으로 진행했다. 3주차에 조원중에 한명은 알고리즘을 푸는걸 좋아하는 형이었다...! 알고리즘 문제를 풀기도 잘 풀고, 답을 보고 이해하고 그걸 흡수하는 속도도 엄청 빨라서 내가 일주일동안 걸려서 겨우 다 푼 문제들을 3일만에 다 풀어버리고 다른 사람들을 많이 도와줬다. 도움을 줄 때도 내가 어떤 부분에서 지금 모르고 있고 어떤걸 생각해야 할지 힌트도 적절하게 줘서 모든 과제를 끝내는데 도움을 많이 받았다. 3주차가 되니까 3기 동기(거의 운명공동체)들과도..

문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 왜 틀렸을까? 시간초과로 엄청 고생했던 문제였다. 시간초과를 줄여보기 위해서 바이러스가 우리가 구하고자 하는 좌표칸 안에 증식되게 되면 변하지 않는 점을 이용해서 우리가 구하고자 하는 위치에 바이러스가 증식되는 순간 종료시키는 코드를 추가했다. 처음 짰던 코드에서는 바이러스의 종류별로(1~K 까지) 모두 확인하면서 코드를 짰었는데, 그 시간을 줄이기 위해서 전체..

📷 회고 2주차에는 조원 형의 추천으로 문제들의 속도, 메모리, 코드길이를 적어서 google sheet에 올렸다. 이 방법을 사용하니까 더 속도를 높이려면 어떻게 해야하는지 상대방의 코드를 참고할 수 있어서 좋았다. 각자의 코드는 github repository를 각자 파서 올리고 그 주소를 공유해주는 식으로 볼 수 있게 했다. 추이를 살펴보니 같은 문제에서 속도와 메모리는 반비례관계가 있는 듯 했다. 속도를 빠르게 하기 위해 여러 작업들을 추가할수록 메모리 사용이 늘어나는 것 같다. 각자 풀다가 이렇게 가다가는 다 못풀 것 같아서 회의를 통해 진도를 맞추고 1시간 고민, 못풀면 1시간 답보고 이해, 그래도 이해못하면 1시간동안 서로 알려주는 식으로 진행했다.(1-1-1) 1주차와 비슷하게 혼자 힘으로..

왜 틀렸는지 메모리초과의 늪에서 한참동안 빠져있던 문제였다. 찾는 N의 범위가 1~10억 이기 때문에 배열에 Moo 수열을 만들어서 넣으면 메모리 초과가 뜬다. 그래서 m의 위치만 배열에 집어넣어도 마찬가지로 메모리 초과가 난다. 큰 수를 배열에 넣는 순간 메모리를 많이 잡아먹는 것을 처음부터 생각해서 배열에 넣는 방식말고 다른 방식을 사용했어야 했는데 그러지 못했다. 접근방법 배열에 수열, m의 위치를 넣지 못한다면 n이 Moo수열의 몇 번째 원소인지 어떻게 찾아낼 것인가? 길이를 사용하면 된다 !.! 문제에서 주어진 점화식은 S(K) = S(K-1) + (3+K) + S(K-1) 이고 이는 S(K) = 2*S(K-1) + K + 3으로 쓸 수 있다. 그런데 여기서 S 수열을 S 수열의 길이로만 바꿔주..

점근 표기법(Asymptotic Notation) 점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 우리는 이를 알고리즘의 복잡도를 단순화할때 쓴다. 어떻게? 가장 큰 영향을 주는 항만 계산하는 방식으로 단순화 시킨다. 점근적 표기법에는 대표적으로 3가지가 있다. 최상의 시나리오를 기준으로 하는 표기법: 오메가 표기법 평균적인 시나리오를 기준으로 하는 표기법: 세타 표기법 최악의 시나리오를 기준으로 하는 표기법: 빅오 표기법(Big-O Notaion) 우리가 주로 사용할 빅오 표기법은 실행 시간의 상한을 나타내며, 다른말로 하면 최악을 생각하는 경우이다. 컴퓨터공학자들은 일반적으로 최악을 상황을 고려하고 프로그래밍을 짜기 때문에 Big-O 표기법을 많이 쓴다..