벨만 포드 알고리즘?

출발지로부터 다른 목적지들로 최단 거리를 구할 수 있음다익스트라와 다르게 음수 사이클에 대해서 확인 가능시간복잡도는 O(V \* E)거리 배열을 출발지만 0으로 만들어놓고 나머지는 모두 최댓값으로 갱신매 단계에서 모든 간선을 검사하므로, 출발지부터 점차 확장되면서 거리

2021년 5월 17일
·
0개의 댓글

Hash?

해쉬 자료구조의 Key는 중복이 없음HashSet은 Key만 존재 HashMap은 Key와 Value가 존재Hash 자료구조에 사용되는 Key는 해쉬 관련 함수를 오버라이딩 해야함eKey값이므로, 고유한 값Key가 동일하면, 이전 객체가 덮어씌워짐equals에 의해서

2021년 5월 9일
·
0개의 댓글
post-thumbnail

DFS vs BFS?

깊이 우선 탐색호출되는 함수의 구조를 트리로 보면, 매 호출마다 트리의 높이가 증가BFS와 다르게 리턴 동작이 존재(이전 높이로 돌아온다)시간복잡도는 O(V + E), 모든 V를 방문해서 총 E번만큼 움직이므로너비 우선 탐색호출되는 함수의 구조가 트리라면, 같은 높이의

2021년 5월 9일
·
0개의 댓글
post-thumbnail

Split VS StringTokenizer?

나도 처음엔 같은줄 알고, 무분별하게 사용했었다. 하지만, 그걸 깨준 문제가 있어서 공유하려고 한다.https://www.acmicpc.net/problem/15681위 문제를 풀어보면, Split으로 풀어보면 무조건 틀린다. 무슨 입출력으로 장난을 치냐 생각

2021년 5월 9일
·
0개의 댓글

머지소트란?

배열을 반으로 나눠서 재귀적으로 호출해서 정렬을 하는 방식리턴이 이루어질때, 정렬된 상태로 리턴시간복잡도는 O(NlogN), 공간복잡도는 O(N)이다.함수를 호출하는 공간복잡도는 O(logN)이지만, 배열을 선언하는 공간복잡도가 O(N)이므로 O(N)안정 정렬재귀적으로

2021년 5월 6일
·
0개의 댓글

퀵소트란?

배열을 피벗을 기준으로 나눠서 정렬하는 방식피벗을 어떻게 선택함에 따라, 성능 차이가 존재최악의 경우 O(n^2)까지 발생할 수 있음베스트 케이스의 경우 O(nlogn)의 시간 복잡도를 가짐공간복잡도는 O(1)피벗을 선택하고, 피벗과의 값 비교를 통해서 왼쪽과 오른쪽

2021년 5월 5일
·
0개의 댓글

힙소트란?

힙트리의 성질을 이용해서 정렬시간복잡도는 O(NlogN)이며, 공간복잡도는 O(1)이다.부모 노드 1개와 자식 노드 2개의 구조를 이룬다.Stable하지 않은 정렬 알고리즘이다.루트 노드가 왼쪽 서브 트리의 노드들보다 크고 오른쪽 서브 트리의 노드들보다도 크도록 만들어

2021년 5월 5일
·
0개의 댓글

다익스트라 알고리즘이란?

A에서 C라는 점을 거쳐서 B로 갈 수 있을 때, A에서 C로 가는 거리가 A에서 B로 가는 거리보다 더 크므로 절대로 C를 통해 연결된 경로로 B에 최단 거리로 도달할 수 없다.A가 특정 노드가 아니라 최단 거리가 구해진 노드들의 집합으로 생각해보자. 매순간 집합들과

2021년 5월 1일
·
0개의 댓글
post-thumbnail

[BOJ 2873] 롤러코스터

완전 탐색을 하면 안되는 이유? 이 문제의 최대 행과 열은 1000이다, 2차원 배열의 한 원소에서 최대 4가지 방향으로 나아갈 수 있다. 방문 배열을 제외한다고 치더라도, (N - @) ^ 1000 * 1000이므로 TLE가 발생할 수 밖에 없다. > 가장 기쁨

2021년 4월 30일
·
0개의 댓글