rimugi

해결과정 - 확률a와 b로 이루어진 선분이 몇번 출현하는지 안다면 쉽게 풀수 있는 문제였다.a,b를 제외한 나머지를 일렬로 배치하는 방법은 (n-2)! 이며 배치한 공간중 a,b가 들어갈 수 있는 공간은 n - 1개로 a, b선분은 총 (n - 1)!번 등장하게 된다.따라서 각 점들끼리 의 거리를 한번씩 더해준뒤 출현횟수인 (n - 1)!을 곱한뒤 a,b b,a 양방향을 고려하여 2를 곱한뒤 총 개수 n!으로 나눈다면 답이되는 재미있는 문제였다 #include #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);typedef long long ll;using namespace std;class Point {public: int x,..

해결과정 - 딕셔너리핵심은 아래의 문자부터 확인하여 같은 같은 문자가 있을 경우 그 열에 해당하는 문자를 확인해 나가는 것을 반복하는 것이였다 아이디어는 간단하여 해결은 쉬웠다 대체로 다른 사람들의 코드를 확인해 보니 이진탐색 방식과 해쉬를 사용하여 풀었고 R과 C의 값이 작아 완탐으로도 충분히 풀리는 문제였지만 내 코드가 메모리 측면에서는 별로지만 시간 측면에서는 효율적이라고 생각들었다#include#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);using namespace std;vector inputs;int result = 0;//아래부터 확인하며 같은 문자열의 최고위를 확인한다void dfs(vector c..

해결과정 - 트리 탐색1. 리프노드에서는 반드시 혁준이가 이긴다2. 어떤 노드에서 시작하였을때 누가 반드시 이기는지를 리프노드에서부터 탐색한다3. 동우가 시작하는 노드의 자식노드들중 혁준이가 이기는 노드가 있으면 그 시작노드는 반드시 동우가 이긴다 이 3가지를 이용하니 문제가 수월하게 해결되었다 처음에는 트리의 자식노드의 개수를 묻는 문제인줄알았지만 곰곰히 생각해보니 다른 문제였다. #include #include using namespace std;vector> adj;vector depth; bool dfs(int cur, int parent){ bool check = false; for(int i = 0 ; i > n; adj.resize(n + 1); depth.resize(..

해결과정 - bfs dp?복소수의 특징을 가지고 다룰수 있는 재미있는 문제였다 총 2가지를 고려하면 되었는데1. 복소수는 4번 반복되면 원래 상태로 돌아온다2. 실수부 허수부의 범위가 -500 ~ 500으로 설정되어있다.이 두가지를 이용해 해결하는 문제라는것을 깨달았다 이것저것 고민해본 결과 범위제한이 존재하므로 특정 실수부 허수부에 방문했다면 제일 처음 방문한 그 번지를 저장하고 이후에는 4 번마다 무조건 방문할 수 있으므로 그것을 처리해 준다이렇게 처리한다면 최대 1000 * 1000 번의 방문만 이루어 지고 그 이후의 값은 1, 2 를 통하여 해결할 수 있었던 재미있는 문제였다 #include#define FAST ios_base::sync_with_stdio(false), cin.tie(NULL)..

해결 방안 - 트라이, dfs아호 코라식 알고리즘을 사용하기 전에 트라이를 연습할겸 문제를 해결해 보았다. 이 문제는 트리 형태로 문자를 담아 둔 다음 일치하는 문자열을 발견하면 답을 가져오는 기초적인 트라이 문제였다 트라이에 대한 설명은 다른분들이 더 잘할테니 해결 코드만 남기지만 조금 더럽게 작성하거 같다 ㅎㅎ#include#define FAST ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);using namespace std;char board[4][4];//원래 이렇게 하면 안되지만 귀찮으므로 문자열이 이미 방문한 곳인지 체크한다vector is_visited;int to_number(char key) { return key..

해결과정 - stack첫번째 해결 주어진 문제대로 하나씩하니씩 전진하며 시뮬을 돌려보는 방법을 적용해보았지만 역시 시간초과가 발생했다한턴마다 위에 적용된 예시대로 확인하며 한칸 한칸씩 이동하니 시간초과가 발생할 수 밖에 없었다. 첫번째 방식#include#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);typedef long long ll;using namespace std;int R, C;vector> board;void print() { for (int i = 0; i find_next_pos(int r, int c) { //아래 확인 int down_r = r + 1; if (board[down_r]..

이 문제는 특정한 사정으로 다시 한번 공부하게 되었는데 다른 사람들의 코드를 조금더 쉽게 풀어서 작업하였다. #include#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;int main() { Fast; int n; cin >> n; vector arr; for (int i = 0; i > in; if (arr.size() == 0) { arr.push_back(in); } else { int index = lower_bound(arr.begin(), arr.end(), in) - arr.beg..

해결과정 - bfs, 우선순위 큐처음 해결 방법은 그래프 형식으로 바꾼다음 다익스트라 알고리즘이나 플로이드 워셜 알고리즘을 사용하는 것이였다. 하지만 거리의 개념으로 변환시키는것 자체가 이 문제였기에 기각하였다. 그래서 해결방법의 아이디어를 다익스트라 알고리즘에서 착안하였다 갈수 있는공간의 비용은 0으로 벽은 비용을 1로 취급한다음 이를 이용하여 bfs로 탐색하면서 중복되는 방 탐색없이 n^2 * longn 시간복잡도 안에 이 문제를 해결할 수 있었다 #include #define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)typedef long long ll;using namespace std;int dir[4][2] = { {0,1},{1,0},{0..

해결과정 - DP, 투포인터핵심은 두가지가 있다1. 현재 그림을 보이게 할때 앞에 올수있는 가장 큰 그림 찾기 - 투포인터2. 현재 그림보다 작은 그림들에대한 최대값 미리 구해두기 - DP 1.의 경우 n 시간안에 찾아야 하므로 완전탐색이 아닌 투포인터를 사용해주었다2.의 경우 i번째그림을 걸려고할경우 1에서 구한 그림에대해 계산된 값을 이용해주고 i번째 그림을 걸지 않는경우 그전 그림에대해 계산해주면 된다 #include #define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)typedef long long ll;using namespace std;int main() { FAST; int n, s; cin >> n >> s; /..

해결과정 - 분할정복피보나치 수열을 행렬식으로 나타내면 ((1,1),(1,0))의 제곱꼴로 나타낼 수 있다 이를 이용하여 이 행렬의 제곱을 구하면 logn시간안에 해결이 가능해 진다. 이 문제를 풀기위해서는 단위행렬 * M = M 같이 행렬의 곱셈규칙을 알아야 되고 빠른 거듭제곱을 하는 방법을 알아야 된다빠른 거듭제곱은 30번 거듭제곱을 해야한다 했을때 이를 16 + 8 + 4 + 2 + 1로 만들어 30번이 아닌 5번의 곱셈을 통해 해결하는 방식이다 #include #define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)typedef long long ll;using namespace std;vector> matrix = { {1, 1}, {1, 0..