아네스의 공부일지

이전에 1로 만들기 1을 풀었던 터라, 그대로 가져와서 백트레킹만 구현해서 제출했다. C++ 풀이 #include using namespace std; int dp[1000001]; vector v; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N,cnt =0; cin >> N; dp[1] = 0; //1부터 시작해서 for(int i = 2; i

와 문제 엄청길다 ㅠㅠ KMP문제인데 이해하는데도 한참걸렸고, 사실 이해한건지 만건지 아직 잘 모르겠다. KMP를 사용하지 않으면 O(n*m)의 시간복잡도를 가지지만, 패턴을 미리 만들어두면 거의 O(N)의 속도로 패턴 매칭을 찾을 수 있다. 간략하게 말하면 makeTable에서 접두사와 접미사에 대한 Table을 미리 만들어 두고, 이를 활용하여 kmp를 진행한다. KMP에 대한 설명은 알고리즘 카테고리에서 다시한번 보도록 하자. C++ 풀이 #include using namespace std; string n,m; int result =0; vector result_vec; vector makeTable(string pattern){ int patternSize = pattern.size(); vec..

KMP이해 잘 안됐는데, 이 영상 보고 이해함.

아이디어 post의 가장 오른쪽 원소를 inorder에서 찾아서 나누면서 분할 정복. C++풀이 #include using namespace std; int n; int inorder[100001]; int postorder[100001]; void solve(pair idx_in, pair idx_post) { int post_left = idx_post.first; int post_right = idx_post.second; int in_left = idx_in.first; int in_right = idx_in.second; cout

아이디어 플로이드 와샬 알고리즘 사용. 동빈나 센세의 글보고 이해하자. 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com C++풀이 #include using namespace std; int n, m; int board[101][101]; void floyd(){ //플로이드는 중간에 거쳐가는것이 핵심이다. for(int k = 1 ; k n >> m; memset(board,0x1f,sizeof(board)); for(int i = 0 ; i> s >> e >> w; if(board[s][e] > w)..

02-23(화) - 02-25(목) 약 30시간? 정도 거래한것 같다. 5만원으로 시작했고, 주식을 원래 했던터라 거래자체는 어렵지 않았다. 제노토큰이 워낙 꿀이였어가지고 잘 빨아먹고, 다른 잡코인들로 단타쳐가면서 꼬박꼬박 모았다. 낙주매매를 즐겨했고, 저점매수 이탈시 물타고 70% 본전 컷 , 3분할(25, 25 , 50) 매수 등등 매매스타일은 내가 주식에서 했던 스타일대로 했다. 참 어이없게도 주식은 마이너스인데 코인은 수익률이 대단하다... 아 처음에 농협계좌가 필요하더라. 업비트는 케이뱅크였는데, 업비트 이메일 인증이 잘 안되서 빗썸 선택해서 했음. 비대면으로 빠르게 만들고 매매했다. 거래내역 이런거 아직 잘 모르겠어서,, 가입축하 쿠폰으로 거래금액 3천만원까지 수수료를 면제해주더라. 개꿀; 다..

아이디어 일단 문제를 보고 가중치도 없고, 최단거리를 찾길레 bfs를 사용했다. 그런데 벽을 부수고 안부수고의 상태를 저장하는 변수를 추가했고, 거리를 저장할 변수를 추가했다. 문제는 visited배열에서 생겼는데, 단순히 visited[x][y] 로는 풀리지 않고, visited[x][y][방문여부]를 추가해줘야한다. 이렇게 바꾸고나면 방문을 했느냐/안했느냐 이지선다가 아니라 아래와 같이 경우가 더 생긴다. 1. 벽을 부수지 않은 상태로 방문한경우 / 방문안한경우 2. 벽을 부순 상태로 방문한 경우 / 방문 안한경우 현재좌표 x,y에서 nx,ny(n : new) 로 이동하는데, 현재 x,y까지 오는데 벽을 부순적이 있는지 없는지에 따라 방문여부를 다르게 체크해주는 것이다. 왜냐하면 벽을 안부수고 nx,..

아이디어 항상 존재하는 루트노드(1번노드)에서 시작해서 가장 먼 곳을 찾고, 그 가장 먼 곳에서 다시 가장 먼곳을 찾으면 지름이 된다. C++풀이 #include using namespace std; //다익스트라를 2번 쓰면 해결되는 문제아닐까. priority_queue pq; // weight, nextnode vector v[10001]; // next node, weight. bool visited[10001]; int dist[10001]; int n; int dijkstra(int s) { //두번 돌릴꺼라 초기화 해주고 시작. memset(visited,false,sizeof(visited)); memset(dist, 0, sizeof(dist)); //시작노드 푸쉬해주고, 방문처리 및 시..

C++ 풀이 #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); string input; vector result; vector op; cin >> input; for(int i = 0; i='A' && input[i]

C++ 시간초과 코드 문제를 보고, 아 음의 싸이클이 있으면 YES로 출력하면 되나보다 하고 풀었다. DFS를 사용해서 start지점과 똑같은 now에 도착하면 cycle이 있으며, sum값이 음수면 음의 싸이클이라 판단하고 return true 약 50%쯤에서 시간초과가 났다. #include using namespace std; //싸이클이 있는가. //음의 싸이클인가. vector v[501]; //index = 출발지점, first = 도착지점, second = 가중치. vector Visit; bool visited[501]; int N,M,W; // 각각 지점의 수, 도로의 개수, 웜홀의 개수. bool dfs(int start,int now,int sum) { if((int)Visit.siz..