c++ (5) 썸네일형 리스트형 [C++/11559] puyo puyo - using simulation 11559 puyo puyo https://www.acmicpc.net/problem/11559 solution 전형적인 시뮬레이션 문제이다. 여기서 포인트는 어떻게 "아래로 떨어짐"을 구현하는가 이다. 아래로 떨어지는 걸 구현하기 위해서는 가장 밑에 있는 뿌요가 없애야 하는 것인지 아닌지에 따라 다르다. 만약 가장 밑에 있는 뿌요가 없어져야 한다면 위에서부터 한칸씩 내려오면서 값을 덮어씌우고 마지막에 맨 첫 줄의 뿌요 값을 . 으로 교체해주면 된다. 알고리즘은 다음과 같다. 1. 현재 필드 값을 보고 BFS를 돌려 인접한 색의 개수가 4개인 그룹을 찾는다. 2. 이 그룹의 값들은 없어져야 하기 때문에 이를 표시하기 위해 좌표를 저장했다가 * 으로 바꾼다. 3. 없어져야 하는 값들에 대해서 for문을 돌.. [C++/14502] 연구소 - using BFS 문제: 연구소 아이디어: BFS 전형적인 BFS 문제다. [특정 map에서 무언가가 퍼져나가는 경우의 수 or 시간 or 집합의 수] 등등의 대부분은 BFS/DFS로 해결 가능하다. 이 문제의 핵심은 어떻게 3개의 벽을 세울 수 있는 경우의 수를 계산하느냐에 달려있다. 나의 경우에는 3개의 벽을 세울 수 있는 모든 가능한 경우의 수를 계산했다. 벽은 빈칸에만 세울 수 있고 어떻게 벽을 세울 때 best 결과가 나올지 모르기 때문에 full search를 하도록 했다. 왜냐하면 애초에 제한 사항에 다음과 같이 map의 크기가 8x8이 최대이기 때문에 가능한 모든 경우의 수를 세어도 무방했다. 다음 로직에 따라 알고리즘을 구성했다. 1. map에서 모든 칸을 확인하며 빈칸일 때 3개의 벽을 세울 수 있는 경.. DP + LCS Algorithm에 대한 이해: 최장 공통 부분 수열 (Longest common subsequence problem) LCS : 최장 공통 부분수열 문제 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제이다. 다시 말해서 두개의 수열 사이에서 가장 긴 공통 부분 수열을 구하는 문제이다. 이때 주의할 점은 substring이 아니라 subsequence 이기 때문에 연속하지 않아도 된다는 것이다. LCS 풀이 접근 방법 그럼 LCS는 어떻게 구할 수 있을까? 기본 아이디어는 DP를 사용한다. 예를 들어 ACAYKP, CAPCAK 두 문자열의 LCS를 구한다고 해보자. 이때 두 문자열을 하나씩 늘려가면서 비교해가는 방법이 가장 쉬운 접근이다. 이때 DP를 사용하여 dp 테이블에 값을 저장한다. 문자열 ACAYKP와 두번째 문자열의 첫번째 char인 C와 최장 공통 수열의 길이는 1이다. 이.. [C++/7576] 토마토 - using BFS 문제 아이디어: BFS 진짜 전형적인 BFS 응용 문제이다. 토마토가 익는 시간을 함께 queue에 넣어서 저장한 다음, 익는 시간이 특정 시간을 지나고 나면 하루가 지난 것으로 판별해야 한다. 또한 맨 처음에 queue에 넣는 좌표는 토마토가 있는 좌표를 모두 넣는다. 이때 시간대는 모두 0으로 초기화 한다. 토마토가 이동할 수 있는 동서남북 4 방향에 대해서 토마토가 없는 경우에 값을 바꾸고 queue에 넣어준다. 이때는 (이전시간 + 1)로 설정하여서 넣어준다. 구현 #include #include #include #include using namespace std; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int m, n; int graph[.. [17968/c++] Fire on Field 간단하게 요약하면 등차수열을 만들지 않는 최소의 양의 정수를 구하는 것이었다. 아오 근데 맨날 알고리즘 문제는 영어라서 나는 한참을 읽고...또 읽는다. 방학되면 영어 공부 제대로 해야지;;; 일단 값에 1을 대입하고 검사를 한다. 조건은 k > 0 , i − 2k ≥0, A[i] − A[i − k] ≠ A[i − k] − A[i − 2k]. 만약에 조건을 위배하면 즉 등차수열이 완성되면 1을 더해준다. 여기서 고려해야할 점은 1을 더한 후에 또 등차수열을 만들지는 않는지 검사를 해줘야한다. 이게 숫자가 작으면 상관없는데 8이상이 되면 문제가 생기기 때문임 그래서 어떻게 검사를 또 시킬까 하다가 걍 재귀함수 사용함 덕분에 4ms나 걸림 #include using namespace std; void che.. 이전 1 다음
