devlog

출처 : https://www.acmicpc.net/problem/19237 풀이 방법호흡이 긴 문제 이므로 구현해야 할 것을 정리하자  턴마다 수행해야 할 것상어 이동방향 정하기겹치면 강한 상어 살아남기냄새 시간 제거시간 0이면 냄새 제거냄새 생성위와 같이 순서를 정할 수 있다. 이제 구현할 때 사용할 자료구조를 선택하자일단 저장해야 할 자료 : 상어의 위치, 냄새 (시간, 위치, 누구의 냄새인지)를 저장해야 한다.이를 위해 상어의 위치는 pair의 벡터로 저장했다. 또한 냄새도 매 턴이 지날 때마다, 시간을 1씩 감소해야 하므로 2차원 배열을 사용하기보단, vector, int>를 활용하여 저장했다.냄새를 따로 저장했고, 상어의 이동을 위해 해당 상어의 상하좌우에 어떤 상어의 냄새가 있는지 빠르게 판..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 방법처음에는 완전 탐색을 이용해서 풀이했지만, 시간 초과가 발생했다.문제를 살펴보면, 특정 상황이 반복되는 것을 확인할 수 있다.하지만 다른 문제와 다르게 2가지의 상황이 반복되므로, DP를 두 개를 사용해야 했다.또한 DP의 기준점을 정하는 것도 중요하다.기준점으로 top으로 설정했다. (n개 이기도하고, 가장 명확한 기준점이 될 거 같아서)또한 케이스를 나누어야 한다.  n = 2일 때, dp[1]을 구하려면 두 가지 경우로..

출처 : https://swexpertacademy.com/main/solvingProblem/solvingProblem.do SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com풀이 방법Cell 구조체를 정의하고 operator Cell의 구조체는 y, x, time, life를 저장하는데 time은 활성화한 후 1시간 후인 즉 번식하는 시간으로 설정했다. 그리고 K시간 후 남아 있는 줄기 세포를 계산하기 위해 time -1 -life  또한 줄기세포가 좌표 범위를 넘어가 번식을 못하는 경우가 없으므로 줄기세포를 저장하는 lab의 범위설정도 중요했다. 다른 사람의 풀이를 보니 351로 설정해도 통과가 가능하다고 한다...

출처 : https://www.acmicpc.net/problem/16235 풀이 방법처음에는 현재 나무를 모두 vector에 저장해서 매번 여름마다 정렬을 했다. 처음 생각엔 정렬 시간 복잡도는 nlogn이라 생각했기 때문에 시간적 여유가 있을 것이라 생각하고 제출했더니 시간초과가 발생했다.다른 분들의 풀이를 보니 deque를 사용해서 정렬을 하지 않는 것이 시간이 덜 드는 것을 알 수 있었다. deque방법을 봤을 땐, for i = 0 ~ n, for j = 0 ~ n 즉 n^2의 시간 복잡도가 걸린다 생각해서 정렬을 하는 것이 시간이 덜 든다고 생각했지만, n의 최댓값은 11이고 정렬을 하게 된다면 나무의 개수가 121개만 넘어가더라도 deque를 활용하는 것이 더 효율적이라는 것을 알 수 있었다..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/258707?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법제일 처음에는 완전 탐색을 이용해가 위해 dfs를 활용해서, 모두 선택하는 경우, 하나만 선택하는 경우, 둘 다 선택하는 경우를 백트레킹을 활용해서 풀이하였다.하지만 시간 초과가 발생했다. 이에 그리디를 활용해서 풀이할 수 있음을 알게 되었다. 문제의 핵심은 코인을 사용해 짝을 맞출 수 있는 카드를 별도로 저장해 두는 것이다. 이를 통해, 기존에 가진 카드만으로는 짝을 맞추지 못할 경우 코인을 사용해 얻..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법각 모든 경우의 수의 조합을 다 구하면 된다.그러기 위해 dfs를 활용하여 백트레킹을 이용해 구현했다.만약 선택한 수가 cnt라면 가능한 승리 횟수를 구했는데여기서 visited 배열은 A가 선택한 주사위이다. A의 주사위만 선택하고 B의 주사위는 visited의 인덱스가 0인 것만 추가해 줬다.주사위를 다 선택하면 A와 B가 만들 수 있는 수를 구해야 한다. 이를 위해 또 dfs를 활용했다. 모든 가능한 수를 구해 벡터에 저..

출처 : https://www.acmicpc.net/problem/15684 풀이 방법최대 설치 사다리가 3개이므로 완전 탐색 + 구현으로 풀이했다.설치된 사다리를 어떤 자료구조로 저장할지도 중요하다.ladder[y][x] 배열에 설치 유무를 저장했다.  의미는 y번째 가로줄에 x번째 세로줄에서 x+1번째 세로줄로 연결된 위치이다.  작성해야 하는 함수1. i번째 세로줄이 i번째로 가는지 체크하는 함수2. i번째 사다리의 시뮬레이션 결과 어디로 도착할지 판단하는 함수3. 현재 자리에 설치가 가능한지 체크하는 함수(양 옆으로 있으면 못함)4. dfs 함수 (모든 경우를 다 체크하기 위해서) 인자로 (y, x, cnt) cnt == 사다리 설치 개수 완전 탐색을 위해 백트레킹을 해준다.백트레킹을 위해 lad..