문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다. 위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과 예상요금을 보여주고 있습니다. 그림에서 A와 B 두 사람은 출발지점인 4번 지점에서 출발해..
구현 전, 알아두어야 할 것 Lower Bound 및 Upper Bound는 모두 경계값을 찾는 함수다. 이 함수는 반드시 정렬이 된 값들에서만 사용할 수 있다. Lower Bound 파이썬 코드 구현 : O(logn) Lower Bound는 찾고자 하는 값이 가장 처음으로 나오는 위치를 찾는 함수다. 예를 들어, 4를 찾는다면 4가 가장 처음으로 나오는 위치를 찾는 함수다. 아래 표를 예시로 들 경우, Index는 6이 정답이 된다. Index 0 1 2 3 4 5 6 7 8 Value 1 1 1 2 2 3 4 4 4 Lower Bound 함수를 구현할 때, 나는 다음과 같이 구현했다. 1. 이진 검색을 기준으로 값을 찾는다. (logn의 시간복잡도 구현) 2. 이진 검색 시, 다음과 같은 로직으로 접..
파이썬 리스트 정렬을 할 때, 참고할만한 것들 1. 리스트 내에 있는 것이 실수계열이라면.. 대소비교를 기준으로 리스트가 정렬된다. 2. 리스트 내에 있는 것이 문자열이라면.. 문자열의 길이 상관없이, 사전순으로 정렬된다. 예를 들어 11111, 972, 972999, 98091라는 문자열이 들었다면, 정렬 시 사전순으로 11111, 972, 972999, 98091 순으로 정렬이 된다.
문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다. 입력 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤..
다익스트라 - 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단거리를 구하는 알고리즘이다. - 다익스트라 알고리즘의 핵심을 최단거리는 최단거리와 최단거리의 합으로 표현될 수 있다는 것이다. 이런 이유로 다익스트라는 현재까지 알고 있는 최단거리를 계속 갱신해나가는 방법으로 구현된다. - 현재 최단거리 테이블에 저장된 최단거리는 지금까지 방문한 모든 노드를 고려했을 때, 최단 거리가 된다. 따라서 한번 방문한 노드를 다시 방문할 필요가 없다. - 다익스트라 알고리즘은 음의 값을 가지는 케이스에서는 사용할 수 없다. 음의 값을 가지는 노드가 있을 경우, 그 노드를 여러번 방문하는 것이 가장 최단 거리가 작아지는 현상이 발생하기 때문이다. 다익스트라 알고리즘 방법 1. 먼저 출발 노드를 설정한다...