100개 이하 도시 10만개 이하 버스노선(이동비용)이 주어졌을 때, 모든 도시 간의 이동 비용의 최솟값을 구해야한다.플로이드와샬 알고리즘으로 v세제곱의 시간복잡도로 비용들을 구한다.두 도시간의 비용을 2차원 배열 x,y로 대입시켜두고 x,y가 동일한 같은 도시면 0으
요구사항 O(ElgE)의 시간복잡도로 모든 정점까지 그래프 최단경로를 찾아야한다. V : 정점(노드)의 갯수 E : 간선의 갯수 문제접근 힙을 이용한 최소비용의 경로를 우선순위로 연산하여 노드가 2만개까지 대량으로 주어줘도 빠르게 찾을 수 있도록 목표를 잡았다.
Dual Priority Queue를 구현하라는 문제이다. 다음의 3가지 명령이 들어온다. 임의의 수를 삽입, 최솟값 삭제, 최댓값 삭제.위 3가지 명령 조합으로 100만개의 연산을 N \* logN의 속도로 해결해야한다.힙을 이용하여 해결하기로 했다. 삽입과 삭제가
10만개 이하 정점에 양방향 간선이 여러개 주어졌을 때, 가장긴 정점간의 거리를 구해야한다.임의의 정점을 하나고른뒤 가장 먼 지점을 찾고 다시 그 지점에서 가장 먼 지점간의 거리를 찾도록 하였다.입력으로 주어지는 정점간의 비용들을 음수로 저장하고, 본인이 임의로 지정한
boj 1865번 문제를 풀면서 공부한 알고리즘이다.기존 bf알고리즘 조건을 변형해야 풀 수 있었는데 아래bf함수의 2중for문안의 if문에 조건하나를 삭제하여 풀 수 있었다. "dcurr != inf"라는 조건을 넣으면 시작지점 부터의 정확한 최단시간을 얻을 수 있지
한번 벽을 부수는 것이 가능한 2차원배열 최단거리 찾기 문제이다. 같은 좌표에 재방문 하지 않도록 방문여부를 기록하는 평범한 bfs풀이로 접근했더니 문제가 발생하였다. 벽을 아직 부수지않은 (부술 수 있는 기회가 있는) 큐보다 먼저 벽을 부수고 방문여부를 기록해버린 큐
어느 트리의 인오더와 포스트오더의 출력물을 가지고 트리를 추정하여 preorder로 출력해야하는 문제이다.포스트오더의 맨뒤가 항상 루트노드이고 인오더는 그 루트노드를 기준으로 좌우 노드를 구분할 수 있다는 힌트를 이용해야한다.재귀를 시작하기전에 주어진 인오더 노드들의
스택을 활용하여 연산자를 처리한다. 중위식을 하나씩 읽어서 1. 피연산자이면 반환할 문자열에 바로 합친다.2\. 연산자 +또는-를 읽으면 기존스택에 쌓았던 '('직전까지 반환문자열에 저장하고 +-를 스택에 저장한다.3\. 곱셉또는 나누기를 만나면 기존스택에 꼭대기부터