GyuStory

많이 나오는 알고리즘 유형 : DFS, BFS 스택, 큐, PQ, 정렬, 트리, 구현 (이 정도만 마스터해도 코딩테스트에선 통과가능) 설계 1. 시간 복잡도로 방향성 잡자!! //자료구조 뭐 사용할지( 배열, PQ, Map ,,,) / 무슨 알고리즘 사용할지 2. 아이디어를 내자 3. To Do 만들기 4. 검증 (시뮬레이션, 시간복잡도) ---> 성공시에 구현시작하자!! 시간 비중 50%까지는 설계에 투자해도 된다. 설계가 완벽하면 구현은 금방할 수 있음!! 디버깅 trace(가상으로 한줄씩 실행하는 기능) , 로그 디버깅 등등 여러 디버깅 방법이 있지만 좋은 방법은 ide에 있는 trace를 활용하자 breakpoint 걸어놓고 디버깅시작 --> Expression 탭에 보고싶은 변수값을 watch ..

ArrayList list = new ArrayList(); for(int i=0;i

백준 알고리즘 문제를 푸는데 문제에서 %10000000 을 한 결과를 출력하라는 문제가 조금씩 보인다. 연산결과가 엄청 크기 때문에 오버플로우를 방지하기 위해서 힌트를 주는 느낌인 것 같다. 근데 중요한 건 연산과정에서 나머지연산을 진행해야 한다는 것이다! 단순히 결과값에다가 나머지연산을 수행하게 되면 이미 오버플로우 된 값에 나머지연산을 하게되기 떄문이다.. 그래서 우린 나머지연산의 분배법칙을 활용해서 문제를 해결할 수 있겠다 4칙연산중 / 나눗셈을 제외한 3개의 연산이 나머지 연산의 분배법칙이 적용된다. (나눗셈 처리는 페르마의 소정리 이용해야 한다) 뺼셈의 경우에는 음수가 나올 수 있기 떄문에 M을 한번 더해준 후 나머지를 구하는게 편하기떄문에 추가함.

프림 : 그래프상에 존재하는 모든 노드들을 최소비용으로 연결시키는 알고리즘 다익스트라 : 특정 시작 노드 로부터 그래프 상에 존재하는 모든 노드, 즉 두 노드 사이의 최단거리를 구하는 알고리즘 -공통점 BFS 알고리즘과 유사하지만 BFS랑 다르게 방문할 때 해당 visited 배열 인덱스에 true를 마킹한다. (bfs때는 중복 수행을 막기 위해서 그냥 해당 노드 큐에 넣는 동시에 true를 마킹해버린다.) -차이점 1. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다. ※ 프림은 1->3의 비용이 3인 반면에, 다익스트라는 1->3의 비용이 2이다. 2. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다. 3. 프림이 다익스트라를, 다익스트라가 프..

선형 구조 : 앞 , 뒤 관계가 1:1 인 구조 비선형 구조: 원소들 간의 1:n 관계를 가지는 자료구조 트리 : 비선형구조, 원소들 간에 계층관계를 가지는 계층형 자료구조, 하위원소로 내려가면서 확장되는 나무모양구조 비선형구조는 선형구조에서와 같이 선후 연결관계를 알 수 없기 때문에 노드를 중복되지 않게 전부 방문하는 특별한 방법이 필요 하다. - 너비 우선 탐색 ( BFS ) : 자식 노드들을 먼저 모두 차례로 방문한 후, 방문 했던 자식 노들들을 기준으로 하여 다시 해당노드의 자식 노드들을 차례로 방문하는 방식. 인접한 노드들에 대해 탐색을 한후 , 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입 선출 형태의 자료구조인 큐를 활용함 BFS() 큐 생성 루트 v를 큐에 삽입 while( 큐가 비..

싸피에서 알고리즘 스터디를 진행하게 되었다. 매주 한가지 알고리즘 주제에 대해서 공부하고 그 주제에 해당하는 문제를 풀어오는 형식이다. 첫주에는 정렬 알고리즘 중 특히, 선택, 삽입 , 퀵 , 계수 정렬에 대해서 공부해오기로 했다. 사실 내장 라이브러리에 있는 함수를 이용해 배열을 정렬하는 경우가 알고리즘 문제에 대부분인 것으로 알지만, 정렬 알고리즘에 대한 이해는 기본인 것 같다. 4가지 정렬에 대해서 정리해보겠다. 자바에서 제공되는 표준API에서 한 개의 추상메소드를 가지는 인터페이스는 모두 람다식을 이용해서 익명 구현 객체로 표현 가능 -선택 정렬: 모든 인덱스를 순회하며 제일 작은 수를 찾아 앞에 부터 정렬하는 알고리즘 장점: 자료 이동횟수가 미리 결정된다. 단점: 안정성 없음, *안정정렬은 중복..