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..

출처 :https://www.acmicpc.net/problem/2533 풀이 방법우선 완전 탐색을 이용해서 풀이했었다. 하지만 시간 초과가 발생한다. 해당 문제를 dp로 풀이하기 위해선 문제를 나누는 것이 가장 중요하고(순서를 정하기 위해), 이를 위해서 트리를 만들어야 한다.루트노드는 임의로 설정해도 상관이 없다. (첫 번째 노드로 설정) 트리를 만들었으므로 자식과의 관계만 고려하면 된다.현재가 얼리 아답터면 자식은 얼리 아답터, 얼리 아답터가 아닌경우 상관이 없으므로 둘 중 최솟값을 현재 노드의 dp에 더해준다.만약 현재가 얼리 아답터가 아니면 자식은 무조건 얼리 아답터가 되어야 하기 때문에 해당 경우만 더해준다.모든 자식을 돌며 자식의 dfs 값을 더해주면 된다.그리고 마지막 리프 노드를 처리하기..

출처 : https://www.acmicpc.net/problem/11723 풀이 방법배열을 사용하여 풀이하는 방법도 있지만 비트를 사용한다면 더 빠르게 계산할 수 있다.unsigned int s = 0;을 선언하고 각 연산을 s에 해준다. addn 자리에 or 연산을 통해 1비트를 기록한다.s |= (1  removen 자리에 0을 and연산하여 무조건 0으로 만들어 준다.s &= ~(1  check해당 비트에 1과 and연산을 하여 1이 된다면 1 출력 0이면 0을 출력한다.s &  (1  toggle해당 비트자리에 1과 xor연산을 하여 비어 있으면 채워 넣어주고 값이 있다면 제거해 주는 연산을 수행한다.s ^= (1  all21에서 1을 빼주면 비트는 20자리까지 모두 1로 채워진다. 즉 모든 값..

출처 : https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration/description?page=2&pageSize=5 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 풀이 방법구현 문제이기 때문에 구현해야 할 함수들만 잘 정리해서 구현해 주면 된다. 1. rotate_90(int y, int x, int cnt):  • 특정 좌표 (y, x)를 중심으로 시계 방향으로 cnt만큼 90도 회전시킨다. • 회전할 3x3 영역의 좌표 값을 미리 rotate..