Stargazer

문제: 접근: 그냥 하나씩 접근해서 비교하여 푸는 방식으로 하면, 시간내로 풀지 못한다. 따라서 점화식을 이용해서 풀면 된다. 즉, DP로 풀면 시간내로 풀린다. 전략: 시간을 최소로 사용해야하기 때문에 데이터를 메모라이징하여서 저장한다. 점화식은 구간 [i,j] 가 있을때, i==j(구간길이 1)이면 true, 구간길이가 2일때, 입력데이터 input[i] == input[j] 가 같으면 true 아니면 false로 저장하고, 나머지 구간은 dp[i,j] = dp[i+1, j-1] && input[i] == input[j] 이면 된다. (이전 데이터를 이용해서, 양옆 한번만 비교하면 된다.) 코드: #include #include using namespace std; int n,m; vector su;..

접근: 노드간 순서를 정렬하는 것이기 때문에, 위상정렬로 해결하면 된다. 전략: 각 순서에 대해서 그래프를 그려주고, 그래프 중에서 진입차수가 0인 노드부터 처리하면서, 그 노드로 부터 진입하는 노드의 진입차수를 하나 씩 줄여간다. 그리고 줄인 차수 중 0인 노드를 다시 탐색하면서 반복한다. 만약 처리하지 못한 노드가 있는데, 진입차수가 0인 것이 없다면 순서를 처리 할 수 없는 상태이고, 처리 수랑 전체 노드 수가 같다면, 그 처리 순서대로 출력하면 된다. 코드: #include #include #include using namespace std; int n,m; vector edge[1002]; int num[1002]; int main(){ cin >> n >> m; for(int i=0;i> t;..

접근: 사실상 구현을 잘하는지 묻는 문제.(덕분에 복붙의 향연을 볼 수 있었다..) 크기가 20x20 미만이므로 dfs(백트래킹)를 이용해서 풀어도 무방하다. 전략: 구현 부분은 대략적으로만 설명하면, 모듈화를 위해서 판에 있는 줄들을 한 줄씩 가져와서, 줄을 이동하는 좌우로 이동 가능한 함수를 만든다. 각 줄에 대해 이동을 한 후에 다시 복사하여 다음 count 에 해당하는 map 변수로 저장하여 다음 함수로 넘어간다. (이렇게 따로 저장해 놓으면 따로 백트래킹 처리를 하지 않아도 된다) 그 외 5번 내로 가장 최대로 구할 수 있는 수를 구해야 하므로 DFS를 이용하여, 시뮬레이션을 진행한다. 그 후에 가장 큰 수를 map을 스캔 해서 가장 큰 것을 취하여 반환한다. 코드: #include #inclu..

접근: DP(Dynamic Programming)을 이용해서 푸는 문제. 발상은 행렬 곱셈이 이루어진 후에 두 행렬이 하나의 행렬로 이루어지기 때문에 작은 문제를 뭉쳐서 큰 문제를 해결 할 수 있음을 암시한다. 전략: 전체 행렬의 곱을 큰 문제로 보았을 때, 두 행렬의 곱으로 나눌 수 있고(구간 단위로), 이는 작은 문제로 나누어서 해결한다는 뜻이다. 그 행렬을 구할 수 있는 모든 경우의 수 중에 가장 연산이 가장 작으려면, 구간을 어떻게 나누었을 때 가장 곱 연산이 작은 지를 알면된다. 따라서 구간을 잘게 쪼개어 DP적으로 해결한다. 맨 아래(기본 행렬 곱)에 도달 했을 때, 두 행렬의 곱 연산 수를 구하여서 그 값을 저장한다. 이를 쌓아서 올리면 전체 곱셈 순서를 구할 수 있게 된다. -> 행렬을 나..

접근: 접근은 처음에는 DP로 하려다가 너무 길 것 같아서 포기하였고, 아이디어가 떠오르지 않아서 검색을 해보았다. 그랬더니, 이분 탐색을 이용한 풀이가 있었다. 전략: 가장 긴 수열을 만들기 위해서는 그 숫자들의 간격이 가장 작게 숫자를 설정하는 것인데, 하나 씩 조사를 할 때, 해당하는 값을 포함하는 새로운 수열을 만드는 것처럼 배열 내의 값을 inplace 하여 계속 해서 업데이트 해나가는 방식이다. (작동 방식은 그러한데 직접 해보기 전에는 이해하기 어려웠다.) 매 값을 입력 받을 때, 수열 맨 뒤의 값이 더 작으면 뒤로 삽입 해주고 작다면, 배열 내에 그 값보다 크면서 제일 작은 것을 찾아서 이 값으로 바꾼다. 코드: #include #include using namespace std; int ..

접근: 대충 봐도 탐색 문제이고, 맵 전체를 탐색 해야 하기 때문에 BFS로 탐색하기로 결정함 전략: 우선 시작점은 (0,0)으로 하고, 건물 외벽부터 시작이므로 맵의 변을 2씩 증가시켜서, 패딩을 주어 갈수 있는 경로를 만들면 뚫려있는 곳이나 열쇠를 가지고 있는 문은 통과가 가능하다. 그 다음 주어진 키에 맞게 먼저 전체 탐색을 BFS로 진행하고, 그 중에 발견된 키(중복 포함)가 있으면, 다시 한번 전체 탐색을 한다. 더 이상 새로운 키가 발견되지 않을 때까지 반복해서 전체 탐색을 진행 한다. 그 과정에서 발견된 문서는 합계하여 출력한다. 코드: #include #include using namespace std; int test; char map[102][102]; bool visit[102][10..

접근: 최소 길이를 찾는 문제이기 때문에 BFS로 접근한다. 전략: D,S,L,R 의 연산 과정과 현재 숫자를 큐에 넣고, 한번 씩 돌린다. 이때 이전 상태를 반복하지 않기 위해서 visit 한 상태를 저장하는 배열을 만들어 사용한다. 코드: #include #include using namespace std; //DSLR int t; bool visit[10001]; void bfs(int a , int b){ queue q; q.push({a,""}); for(auto& a : visit){ a = false; } while(!q.empty()){ auto cur = q.front(); q.pop(); if(cur.first == b){ cout t; for(int test=0;test> a >> b..

솔직히 DP는 매번 접근법을 잘 모르겠다... 대충 느낌은 DP 일거라 생각이 들지만 어떻게 해야할 지는 상세히는 모르겠다. (열심히 공부하자..ㅠㅠ) 접근: 이전 결과를 이용하여 현재 결과를 결정하는 방식으로 풀 수 있기 때문에 DP로 풀면된다. 전략: 이전 정보를 저장하는 dp[101][10000] 배열을 만들고, 매 앱을 하나씩 확인하면서, 이전 상태를 참고하여 앱의 cost를 선택하거나 선택하지 않았을때의 최대 확보 할 수 있는 메모리를 비교한다. 끝에는 모든 앱을 비교한 상태들 중 cost가 가장 작은 것을 선택한다. 코드: #include #include using namespace std; int n,m; struct App{ int mem; int cost; }; vector app; in..

얼떨결에 두 번 풀어가지고, 해답을 두번 올리겠다. 접근: 뒤집기 - 순서만 바꿔서 출력하면 됨 삭제 - 뒤집은 상태에 따라 앞뒤 판단만 잘해서 하나씩 삭제 하면됨 전략: 먼저 주어진 데이터를 split해서 실제 배열 변수로 저장한다. 1. deque를 이용한 방법 - 현재 상태에 따라 앞뒤 구분해서 pop_front, pop_back을 방향에 맞게 제거하고, 출력할 때 방향에 맞게 출력 하면 된다. 2. vector를 이용한 방법 - 실제 제거는 하지 않고, 주어진 배열 양 끝 인덱스(left, right) 를 지정하고, 범위를 명령에 맞게 앞 또는 뒤를 하나씩 좁힌다. 출력은 위와 같이 방향에 맞게 출력하면 된다. 코드: *두 코드 작성 시점이 거리가 있어서 스킬이 조금씩 다르니 각각 참고하는 것도 ..

접근: 처음에는 어떻게 접근 해야 할지 직접 그려보면서, 관계를 파악해보았다. 대충 봐도 그래프 이론으로 풀어야 하는데, 그 중 순서 정렬이 필요하기 때문에 위상 정렬로 풀어야 한다는 걸 알 수 있다. 전략: 대소 관계를 표현하기 위해 입력을 digraph(유향그래프) 형태로 입력을 받는다.(형식은 자유 - 행렬, 인접리스트) 진입 차수가 0인 노드부터 큐에 넣고, 큐에서 하나씩 제거하면서 출력한다. 제거한 노드가 가리키는 다른 노드의 진입 차수를 한개 줄이고, 만약 0이라면 큐에 삽입한다. 코드: #include #include #include using namespace std; int n,m; vector comp; vector income; int main(){ cin >> n >> m; comp..