알고리즘9 [개념] 사전순으로 가장 앞선 최단거리 경로 보호되어 있는 글 입니다. 2023. 12. 13. [알고리즘 개념] 다익스트라 다익스트라 알고리즘 한 그래프의 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘을 말한다. 다른 정점까지의 최단 경로를 구하는 과정에서 모든 정점을 탐색하기에 최단 경로를 보장할 수 있다. 단, 가중치가 양수일 때 가능하다.(음수일 땐 벨만포드를 사용하면 된다) 참고로 그래프 알고리즘의 종류 대표적으로 다익스트라, 벨만포드, 플로이드 워셜이 있다. 다익스트라 알고리즘을 어떻게 구현하면 될지 알아보자. 예시로 5개의 정점이 있고 1번 정점에서 출발해 2~5번 정점까지의 최단거리를 구해야 할 때 먼저 입력받은 값을 각각 u(시작 위치), v(도착 위치), w(가중치)라고 한다면 u.append(v,w)가 된다. 만약 V(정점)의 개수가 적다면 위의 인접 리스트 방식이 아닌 인접 행.. 2023. 12. 5. [BOJ] 1052 물병 C++ 문제이해 N개의 물병을 가지고 있는 상태에서 차있는 물병이 K개가 되도록 만드려고 한다. 재분배는 같은 양의 물이 들어있는 물병 두 개를 고르고 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. (상점에서 새로운 1리터 물병을 살 수 있다.) 즉, N으로 같은 양의 물이 들어 있는 물병을 합치면서 K개가 될 수 있는지 확인하고 된다면 상점에서 사야하는 물병의 최솟값을 구해야 하는 문제이다. 아이디어 구상 N, K = 3, 1 1 1 1 -> 2 1 -> 2 2 -> 4로 1개의 물병을 구매하면 된다. N, K = 13, 2 1 x 13 -> 2x6, 1 -> 4 4 4 1 -> 8 4 1 -> 8 4 4 -> 8 8 -> 16으로 3개의 물병을 구매하면 된다. 위와 같이 N은 2로 나누면.. 2023. 11. 13. [프로그래머스] 튜플 C++ 문제 이해 문자열이 주어지면 문자열 안에서 튜플을 가려내면 되는 문제. 아이디어 구상 우선 주어진 값을 그대로 사용하기보단 1번 가공해서 사용하는 게 편할 거 같아서 1차적으로 숫자와 , 만 리스트에 담아서 저장했고 그다음 1차원 리스트에 담긴 값을 길이 기준으로 오름차순 정렬했다. 그다음 문자열만큼 반복하면서 문자 -> 숫자로 형태를 변환시키면서 원래 숫자를 만들고 vis로 해당 숫자가 사용 됐는지의 여부를 판별하면서 결과 리스트에 추가했다.(리스트 = 벡터와 같은 의미로 단어를 사용했습니다.) 코드 #include #include #include #include using namespace std; #define MX 100005 int vis[MX]; vector v; int chk(string a.. 2023. 8. 31. 이전 1 2 3 다음
