104%

쉽게 설명 됨 WebSocket 을 활용한 Server to Client 메시징 기능구현 제이쿼리 sockjs를 이용한 실시간 채팅 웹소켓 구현

엄청난 시간초과 재시도 후에 겨우 성공.. 우선 문제를 어떻게 풀었는지 설명하고 나서 시간초과가 난 원인까지 분석을 해보겠다. 처음에는 이문제를 그냥 DFS로 풀어봤는데 시간 초과가 났다 그냥 DFS로 풀게되면 너무나 많은 경로를 탐색하기 때문에 당연히 시간초과가 날수밖에 없다. 상하좌우 4방향으로 이동이 가능하고 칸수가 최대 500x500 = 250000개이므로 4의 250000승이라는 어마어마한 경로의 경우의수가 존재하기 때문에 그냥 DFS로는 절대 풀수 없는 문제이다. 그래서 DP로 풀어야 하는데, DP로 풀때도 주의사항이 있다. 우선 코드를 먼저 보면 123456789101112131415161718int dfs(int x, int y){ if (dp[x][y] != -1) return dp[x]..

dfs는 데이터의 개수가 조금만 커져도 시간초과가 날 확률이 높은 방법이다. 왜냐하면 50x50칸의 2차원 배열이 있을때 0,0에서 50,50으로 가는 경우의 수를 찾을때 dfs를 사용해야 하고, 상하좌우 네방향으로 이동 가능하다고 했을때4의(50x50)승이라는 어마어마한 연산의 횟수가 발생한다. 물론 범위 벗어나는거 제외하고 이러다보면 저것보단 적겠지만, 어쨌든 그래도 엄청난 연산횟수라는것은 부정할수없다. 그렇기 때문에 우리는 같은 계산을 피해야 한다. 그것이 바로 동적계획법(Dynamic Programming)이고 다른말로 메모이제이션이라고도 한다. 즉 DFS는 DFS인데 예전에 구해놨던 값이 있으면 그 값을 쓰겠다는 뜻이다. 예를 들어 0,0에서 1,1을 거쳐 50,50으로 가는 경로가 있다고 하자..

내 생각에 버블,선택,삽입정렬 정도는 아무런 참고 없이 손코딩 할줄 아는게 좋다고 생각하지만, 머지소트부터는 손코딩 하기도 힘들뿐더러 그럴필요도 없다 왜냐하면 어차피 이런것들은 아주 잘짜여진 미리 만들어져있는 코드들이 수많이 존재하기 때문이다. 그렇기 때문에 머지소트의 동작과정과 빅오, 어떤 경우에 사용해야 좋은지, 장단점 등등만 잘 알아놓는게 중요한것 같다. 그래야 상황에 맞는 자료구조를 잘 선택할수 있게 될것이다. 머지소트의 동작과정은 다음과 같다. 이 그림에서 처럼 하나의 배열을 반으로 계속해서 자르면서 마지막에 원소가 1개일떄까지 계속 잘라나간다. 그리고 난뒤, 잘라진 조각들이 합쳐지면서 정렬이 완료되게 되는데, 위의 코드는 분할을 하는 과정을 나타낸것이다. 보면 알겠지만 재귀를 통해서 계속해서 ..

첫번째 자리에 나머지 것들(1~6번쨰)중 최소값 넣는다. 두번째 자리에 나머지 것들(2~6번쨰)중 최소값 넣는다.......다섯번째 자리에 5~6번째 중 최소를 넣는다. ---> 즉 나머지것들 중에서 제일 작은 혹은 제일 큰 것을 선택해서 정해진 자리에 넣는것이 선택정렬 for(int i=0; i

알고리즘 눈으로 확인하기 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 12345678for(int i=0; i

이 문제는 BFS를 연습하기 가장 좋은 문제인것 같다. 오랜만에 넣자마자 성공.. 문제를 풀면서 느낀건데 BFS와 큐 벡터등 기초적인 내용을 잘 익힐수있는 문제라고 생각한다. 문제 예시가 너무 잘나와있어서 문제 해석에는 별로 어려움이 없었다. 풀이과정을 대충 설명하자면 우선 M x N 의 칸을 배열로 매칭시켜야 한다. 그리고 나서 각 나눠진 영역에 대해서 BFS를 돌려야 한다. DFS도 해보진 않았지만 시간제한이 1초이기때문에 왠지 시간초과가 날것같지만 해보진 않았다. DFS같은경우에는 모든 경우를 탐색할수있지만 한곳을 계속해서 파내려가므로 시간이 오래걸릴수있다는 단점이 있다. 그래서 이문제는 BFS 로 접근하는게 맞는것 같다. 우선 정사각형을 2차원 배열에 맵핑 시켜야 하는데, 아래 코드가 그 코드이다..

이 문제는 DFS 기초 문제이다. 하지만 재귀로 풀려고했을때 처음에는 시간 초과가 나서 약간 삽질을 좀 했다.. 문제는 우선 1->2->3으로 갈수 있을때 1->3으로도 갈수있으므로 W[1][3]도 갈수있다고 1로 체크해주는 문제이다. 즉 중간에 몇개를 거쳐서라도 갈수 있으면 그 경로는 갈수있다고 체크를 해준다. 워셜-플로이드 알고리즘으로도 풀수 있지만 나는 dfs를 연습하고 싶어서 굳이 dfs로 풀었다. 첫번째 예제로 설명을 하자면, 1->2 , 2->3 , 3->1로 갈수있는 경로가 있다. 먼저 첫번째 정점인 1번 정점에서 갈수있는 경로를 모두 조사한다. for(int i=1; i