개인사

리뷰 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하는 문제다익스트라로 모든 노드까지의 최단 거리를 구한 후, 해당 노드 중 거리가 최대값인 노드를 찾는다.최대값과 동일한 값을 같는 거리를 가진 노드의 개수를 출력해 주었다.  전역 변수nodes : 노드의 개수를 저장할 변수lst : 노드간 인접 리스트를 저장할 정수형 벡터 배열, 노드의 최대 갯수인 2만보다 크게 해주어야 한다.Pos : 다익스트라의 탐색용 구조체, 우선순위 큐용 오름차순 cmp함수를 정의했다. 함수1. dijkstraint dijkstra() 1번 노드로부터 모든 노드까지의 거리를 ..

리뷰 https://www.acmicpc.net/problem/14461D 최단 경로 문제, 알고리즘 분류에 DP가 있긴 한데, 다익스트라를 통해 문제를 풀이하였다. 전역 변수n, d : 주어지는 지름길의 개수 n, 목적지 까지의 거리 dPos : 다익스트라를 진행할 때 직선 상에서의 현재 위치를 나타낼 구조체, 시간을 기준으로 오름차순 정렬한다.lst : 지름길 정보를 저장하기 위한 pair 타입의 벡터, 최대 10001크기로 설정한ㄷ. 함수1. dijkstraint dijkstra() 다익스트라를 통해 목표 지점까지의 최단 경로를 구하는 함수정수형 벡터 dist를 d + 1 크기, 적당히 큰 값으로 초기화 한다, 나는 20억으로 세팅했다.시작 지점인 0을 dist[0] = 0을 통해 거리를 0으로 만..

리뷰 2차원 다익스트라의 기본적인 문제https://www.acmicpc.net/problem/4485 전역 변수n : 각 테스트 케이스마다 주어지는 맵의 한 변의 길이lst : 각 테스트 케이스마다 주어지는 맵 정보를 저장할 2차원 정수 배열, 최대크기는 125*125다.dx, dy : 상하좌우 4방향을 탐색하기 위한 방향 배열Pos : 우선순위 큐에서 현재 위치 정보를 나타낼 구조체, w를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() 다익스트라를 통해 출발지에서 도착지까지의 최단 거리를 구하는 함수Pos타입 우선순위 큐 pq를 초기화 하고 거기에 시작 지점 x, y좌표와 시작 지점의 값을 넣어준다.n * n크기의 2차원 정수형 벡터 dist를 기본값을 매우 크게 지정..

리뷰 백준의 벽부수고 이동하기 시리즈와 유사한 문제였다. SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  전역 변수tc, n, k : 테스크 케이스의 개수 tc, 각 테케당 한 변의 개수 n, 각 테케당 나무를 벨 수 있는 횟수 ksx, sy, ex, ey : 각 테스트 케이스당 시작 및 도착 지점의 x, y좌표lst : 문자열로 이루어진 맵 정보, 최대 10 * 10의 크기이다.dx, dy : 상하좌우 이동시 사용할 방향 배열, 상우하좌 순으로 인덱싱이 되어 있다.Pos : 탐색을 할때 현재 정보에 대한 정보를 담을 구조체, 현재 위치, 방향, 자른 나무의 개수, 시간 정보가 있다. 우선순위 큐를 사용해 주어야..

리뷰 플로이드 와샬을 사용해 풀 수 있는 기초적인 문제https://www.acmicpc.net/problem/11403 전역 변수n : 인접 행렬의 한 변의 길이(노드의 개수) 함수없음  문제풀이n값을 입력 받고 거리를 저장할 2차원 정수 벡터 dist를 n * n크기로 초기화 한다.dist에 인접 행렬을 입력 받아준다, 이때 0이 입력 되었다면 1보다 큰 적절한 수로 변환해 준다.플로이드 와샬을 통해 3중  for문을 통해 갈 수 있으면서 1보다 큰 간선을 찾아 1로 변경해 준다.모든 작업을 마친 후 dist벡터 정보를 출력해 준다, 이때 1보다 큰 수라면 0으로 변환해서 출력해 주면 된다. 참고 사항정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 ..

리뷰 간단한 다익스트라를 통한 시작점 > 도착점으로 가는 최단 경로를 구하는 문제https://www.acmicpc.net/problem/5972 전역 변수n, m : 노드의 개수를 저장할 정수형 변수 n, 간선 개수를 저장할 정수형 변수 mPos : 간선 정보를 저장할 구조체, 다음 노드와 가중치가 저장되며, 우선순위 큐의 compare 함수를 정의했다.path : 각 노드의 인접리스트를 저장할 Pos타입 2차원 벡터 함수1. dijkstraint dijkstra(int start, int end) start에서 end까지의 최단 경로를 구하는 함수Pos타입 우선순위 큐 pq에 start를 삽입하고 end까지 가는길의 최단경로를 dist벡터에 최신화 해준다.pq가 빌때까지 while루프를 통해 위 작업..

리뷰경로 상에 신호등이 있어 기다렸다가 움직여야 하는 최단 경로 문제, 다른 문제와 다른점은 신호등의 방향이 정해져 있어 교차로에 진입하는 경우를 잘 분배해 주어야 했다.https://www.acmicpc.net/problem/1400 문제 풀이행 범위n, 열 범위 m, 시작 좌표 sx, sy 도착 좌표 ex, ey, 방향 배열, 맵 정보 lst배열을 전역 변수로 세팅한다.우선 순위 큐에서 사용할 Pos구조체를 정의하고, compare함수도 넣어준다.신호등 정보를 받을 구조체 Light를 정의하고, 신호등 배열 lights를 60크기로 설정해 준다.main함수에서 무한루프를 실행하고 input함수에서 n, m이 0, 0이라면 while루프를 종료해 준다.input함수를 통해 n, m값을 받고 만약 n과 ..

리뷰 정수형 변수 타입을 잘 확인하자.. 처음에 틀리고 나서 모두 long long으로 바꿔줬으나 다익스트라 리턴 형식을 int로 두었었다.https://www.acmicpc.net/problem/24042 문제 풀이n, m을 지역변수로 설정한다, long long타입 거리 배열을 10만 1 크기로 초기화 해준다.시뮬레이션 상에서 현재 위치 정보가 될 Pos구조체를 정의해 준다. pq를 활용할 것이니 내부에 compare 함수 포함인접 리스트를 표시할 EDGE 구조체를 정의해 준다, 노드와 해당 노드의 신호등 인덱스 정보가 담긴다.EDGE타입의 2차 배열 path를 초기화 해준다. 해당 벡터를 통해 인접리스트를 체크할 것이다.n과 m을 입력 받고 path의 사이즈를 n + 1로 초기화 해준 뒤 거리 배열..

리뷰예상 도착지가 주어 졌을때 출발 노드에서 도착 노드까지의 경로 중 일부 경로가 포함 되어있는지를 확인 해야하는 문제 문제 풀이테스트 케이스를 통해 구분된다, 각 테스트 케이스를 반복문을 통해 열어준다.노드 수 n, 간선의 수 m, 예상 도착지의 수 t, 시작 노드 s, 포함 간선을 나타내기 위한 g, h를 받아온다.간선을 양방향으로 받아 주고, 예상 도착지 t개를 입력 받고 오름차순으로 정렬해 준다.다시 t개의 예상 도착지를 순회하며 출발지 부터 예상 도착지 까지의 최단 거리를 구해준다.g와 h를 포함하여 도착지 까지 가는 거리를 찾고, 둘을 비교하여 같다면 도착 노드를 출력해 준다. 참고 사항g와 h를 포함하여 도착지 까지 가는 거리를 찾는 방법은 s -> g -> h -> 도착노드 이거나 s ->..

개요특징특정 노드에서 연결 되어 있는 모든 노드까지의 최단 거리를 구할 수 있다.가중치는 양수여야만 하며 음수일 경우 해당 간선을 계속 방문하게 되어 루프에 빠지게 된다.양방향 및 단방향 그래프 및 2차 배열 형태에서도 에 모두 사용 가능하다.동작 요약모든 노드 까지의 거리를 2e9 혹은 INT_MAX와 같은 값을 사용하여 최대치로 설정한다.시작점 노드 자기 자신 까지의 거리를 0으로 설정하고, 우선순위 큐에 자신을 추가한다.첫 탐색 시 자신과 연결된 인접 리스트를 참고하여 해당 노드까지의 거리가 현재 거리보다 짧다면 갱신해 주고 해당 노드를 우선순위 큐에 넣어준다.이후 우선순위 큐에 있는 노드와 연결된 인접 리스트를 참고하여 거리 정보가 최소가 되도록 갱신해 주는 작업을 반복한다.우선순위 큐에 더 이상..