ALGORITHM/c&c++ baekjoon (17) 썸네일형 리스트형 [C++/14499] 주사위 굴리기 - using simulation 14499 주사위 굴리기 https://www.acmicpc.net/problem/14499 solution 주사위를 굴리는 방향에 따라 달라질 수 있는 맨 위의 숫자를 출력하는 시뮬레이션/구현 문제이다. 이때 주사위 전개도에 따라서 다음과 같이 크게 2개의 배열로 구분 가능하다. 1. 세로 배열 2. 가로 배열 주사위를 굴리는 방향에 따라서 특정 배열만 회전해주면 된다. 입력이 1, 2 인 경우: 동쪽과 서쪽으로 움직이는 것이기 때문에 가로 배열 회전 입력이 3, 4인 경우: 북쪽과 남쪽으로 움직이는 것이기 때문에 세로 배열 회전 이때 중요한 점은 가로 배열과 세로 배열은 값이 공통인 부분이 존재한다는 것이다. (위쪽과 아래쪽) 따라서 이 부분은 특정 배열을 회전할 때마다 다른 하나의 배열에 값을 복사.. [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이다. 이.. 음수 간선을 가지는 그래프의 최단 경로: 벨만-포드 알고리즘 최단 경로 알고리즘은 대표적으로 플로이드 워셜, 다익스트라 등등 있지만 이 중에서도 한 노드에서 다른 노드까지의 최단 경로에는 다익스트라 알고리즘이 사용된다. 하지만 다익스트라 알고리즘은 양수에서만 동작한다. 왜 다익스트라 알고리즘은 양수 간선에서만 해를 찾을 수 있을까? 벨만 포드 알고리즘의 대표적인 문제들 11657 타임머신 문제를 해석하면 위와 같다. 한 노드에서 다른 노드까지의 최단 경로인데, 이때 음수 간선이 있을 수 있다. 따라서 벨만 포드 알고리즘을 사용하면 쉽게 해결할 수 있는 문제이다. 구현 // 11657 타임머신 #include #include using namespace std; vector graph[501]; long dist[501];// long type이어야 함 int N,.. [C++/1697, 11779] 탐색 중 이전 값를 저장해야 하는 유형의 문제들 경로나 값을 저장해서 다음에 그 값을 참조해야 하는 경우의 문제들을 정리해보자. 대부분 그래프 탐색이나 BFS, DFS 문제에서 경로 찾기, 걸린 시간 등 출발지에서의 값을 가지고 있어야 하는 경우가 많다. 1697 문제 아이디어: BFS 현재 값인 N에서 가능한 동작은 3가지이다. +1, -1, 2배 이다. 이 경우로 탐색 가능한 값에 대해서 (현재 값까지 걸린 시간 + 1)을 더해서 저장해두고 이에 대해서 다시 탐색을 도는 방식으로 문제를 해결할 수 있다. 이때 저장해두는 값은 시작 노드인 N에서부터 걸린 시간이 된다. 구현 // 1697 숨바꼭질 #include #include using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(f.. [C++/3665] 최종 순위 - using 위상 정렬 (topology sort) 문제 아이디어: 위상 정렬 문제에서는 "순위"를 나열해야 하기 때문에 방향 그래프라는 것을 쉽게 알 수 있다. 이를 순위에 맞게 나열하는 것은 방향 그래프를 정렬하는 것과 같으므로 위상 정렬을 사용할 수 있다. 이때 사이클이 없는 위상 정렬은 항상 노드가 N개 일때 queue를 N번 돌기 때문에, 사이클이 생긴다면 N보다 작은 횟수로 종료하게 된다. 왜냐하면 진입 차수가 0이 되는 노드가 없어서 더 이상 탐색을 진행할 수 없기 때문이다. 따라서 이 경우 쉽게 "IMPOSSIBLE" 인 경우를 알 수 있다. 데이터의 일관성이 없는 경우 "?"를 출력하라고 하였는데 이는 같은 등수인 노드가 여러개인 경우이다. 이 오류는 queue에 들어간 node의 갯수가 몇개인지에 따라 알 수 있다. 즉 2개 이상의 no.. [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[.. 이전 1 2 3 다음
