같은 것이 있는 순열(복수순열) 배우기 - 숫자 만들기 -

1. 문제 4008. [모의 SW역량테스트] 숫자 만들기 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 주어진 숫자들 사이에 연산자를 집어넣어 왼쪽부터 오른쪽으로 우선순위를 무시하고 순서대로 계산을 할때, 가능한 계산결과의 최댓값과 최솟값의 차이를 구하시오 2. 같은 것이 있는 순열 배열의 원소들 중에 같은 것이 포함된 복수순열은 어떻게 구현할 수 있을까? 일반 순열을 구현할때는 배열의 j번째 원소를 사용했는지 여부를 나타내는 used를 사용해서 구현을 했는데 def permutation(i,n,r): if i == r: print(p) else: for j in range(n..

• format_list_bulleted 브루트포스
• · 2022. 10. 12.
• textsms

다익스트라 알고리즘에서 실제 최단 경로 구하기

1. 실제 최단 경로 역추적 지금까지 다익스트라 알고리즘에선 최단 경로로 가는데 걸리는 가중치의 합을 구해왔는데, 실제 최단 경로가 궁금할 수도 있다 어떻게 하면 구할 수 있을까? 결론부터 말하자면 경로를 역추적해서 구한다 어떤 정점 A에서 목적지 B로 가는데, "A,C,D,E,F,G,B로 가는게 최단 경로다" 이렇게 순방향으로 구하지 않고, 다익스트라 알고리즘에서 테이블에서 최단 거리를 가진 정점 u를 선택할때, u와 인접한 정점 b를 선택하는데, b의 거리가 테이블에서 갱신될때 "b와 가장 가까운 정점이 u이다"라고 테이블에 저장을 해놓는다 모든 과정이 종료되면 목적지 B와 가장 가까운 정점이 G이고, G와 가장 가까운 정점이 F이고 F와 가장 가까운 정점이 E이고, ... C와 가장 가까운 정점이 ..

• format_list_bulleted 최단거리 알고리즘
• · 2022. 10. 10.
• textsms

필요한 위치에 삽입하면서 정렬하는 삽입정렬(insertion sort)

1. 개요 선택 정렬은 실제 사용하기에는 매우 느린편이다. 그렇다면 다른 접근 방법은 없을까? "데이터를 하나씩 확인하면서 각 데이터를 적절한 위치에 삽입하면 어떨까?" 삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉽지만, 구현 난이도가 더 어려운데, 하지만 선택 정렬에 비해 실행 시간 측면에서 효율적이라고 알려져있다 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 "데이터가 거의 정렬되어 있을때" 매우 효율적이다 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 그렇지 않다 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬(insertion sort)이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치..

• format_list_bulleted 정렬 알고리즘
• · 2022. 10. 9.
• textsms

거품이 올라오는 것처럼 정렬하는 bubble sort(버블 정렬)

1. 개요 인접한 두개의 원소를 비교하면서 자리를 계속 교환하면서 정렬하는 알고리즘 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동 한 단계가 끝나면, 가장 큰 원소가 마지막 자리로 이동함 교환하면서 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 부름 2. 예시를 통해 이해하는 버블 정렬 55, 7, 78, 12, 42를 정렬한다고 생각해보자. 먼저 55와 7을 비교하여, 55가 더 크니까 자리를 바꾼다. 다음 55와 78을 비교하여, 78이 더 크니까 자리를 바꾸지 않는다. 다음 78과 12를 비교하여 78이 더 크니까 자리를 바꾼다 마지막으로 78과 42를 비교하여, 78이 더 크니까 자리를 바꾼다. 그러면 배열에서 가장 큰 원소인 ..

• format_list_bulleted 정렬 알고리즘
• · 2022. 10. 9.
• textsms

가장 원시적인 정렬 알고리즘인 selection sort(선택 정렬)

1. 정렬(sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에, 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나 정렬 알고리즘으로 데이터를 정렬하면, 이진 탐색(binary search)이 가능해진다. 즉, 이진 탐색의 전처리 과정이기도 하다. 정렬을 공부하다보면 알고리즘의 효율성을 쉽게 이해할 수 있어 상황에 적절하지 못한 정렬 알고리즘을 이용하면, 당연히 프로그램은 비효율적으로 동작하면서, 필요 이상으로 시간을 많이 소요 여기 숫자 카드 10장이 있다. 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 어떻게 이 카드를 정렬할 수 있을까? 보통은 ..

• format_list_bulleted 정렬 알고리즘
• · 2022. 10. 9.
• textsms

최단 거리를 구하는 2번째 알고리즘 플로이드 워셜 알고리즘 파헤치기

1. 개요 다익스트라 알고리즘은 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우"에 사용할 수 있는 최단 경로 알고리즘이다. 플로이드 워셜 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우"에 사용할 수 있는 알고리즘이다. -------------------------------------------------------------------------------------------------------- 다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하면서 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘은 또한 단계마다 "거쳐 가는 노드"를 기준으로 ..

• format_list_bulleted 최단거리 알고리즘
• · 2022. 10. 9.
• textsms