본문 바로가기

전체 글101

알고리즘 6일차 백트래킹 == 탐색 알고리즘 + 조건(유망) 솔직히 재귀에다가 조건문 박으면 백트래킹이라고 생각함. 백트래킹 알고리즘 # 대략 이런 모습 def backtrack(이번선택): if 종료조건: # add, print 등등 return for 아래선택 in 이번선택의 아래선택들: if 유망여부판단(아래선택): backtrack(아래선택) 선택해제 # 다시 선택을 해제하는 것이 필요할 수 있음 nQueen(https://www.acmicpc.net/problem/9663) 유먕 여부를 판단하는 함수를 만들어보자 가로축: 여왕과 같은 가로축에 여왕을 둘 수 없음 세로축: 세로축에 하나의 여왕만 존재할 수 있다. 2차원으로 진행하면 시간초과(그래도 만들어볼것) 아래처럼 정리하면 1차원으로 가능. queens=[N.. 2024. 3. 11.
퀵정렬 특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까? 리스트에서 임의의 원소를 피벗으로 선택합니다. 피벗보다 작은 원소들은 피벗 왼쪽에, 피벗보다 큰 원소들은 피벗 오른쪽에 위치시킵니다. 피벗 왼쪽과 오른쪽 부분을 각각 재귀적으로 퀵 정렬을 사용하여 정렬합니다. p 3 7 8 1 5 9 6 10 2 4 //3을 피벗으로 선택함 p v v 3 7 8 1 5 9 6 10 2 4 //전체적으로 보았을 때 왼쪽부터 시작하여 '3'보다 큰 값인 7을 선택. //오른쪽으로 시작하였을 떄 '3'보다 작은 2를 선택. p v v 3 2 8 1 5 9 6 10 7 4 //큰 값과 작은 값을 변경합니다. //왼쪽에서 '3'보다 큰 값 8과 오른쪽에서 '3'보다 작은 값인 1을 선택. p v v 3 2 1 8 5 9.. 2024. 3. 11.
병합정렬 일단 반으로 나누고 나중에 합쳐서 정렬하면 어떨까? 리스트를 반으로 나눕니다. 왼쪽 부분과 오른쪽 부분을 각각 병합 정렬을 사용하여 정렬합니다. 정렬된 왼쪽 부분과 오른쪽 부분을 병합합니다. 예시에는 시작에서 리스트에서 전부 나누었습니다. 1번에서는 7,6을 비교하여 정렬을 했습니다. 2번에서는 6,7 과 5,8를 비교하여 정렬했습니다. 3번에서는 5,6,7,8과 1,3,5,9비교 하여 정렬했습니다. 2024. 3. 11.
선택정렬 가장 작은 것을 선택해서 제일 앞으로 보내면 어떨까? 1. 리스트에서 가장 작은 값을 찾습니다. 2. 가장 작은 값을 맨 앞에 위치시킵니다. 3. 맨 앞에 있는 값을 제외한 리스트에서 다시 가장 작은 값을 찾습니다. 4. 찾은 값을 두 번째 위치에 위치시킵니다. 5. 2-4 단계를 리스트의 모든 원소가 정렬될 때까지 반복합니다. //초기모습 10 1 5 8 7 6 4 3 2 9 //가장 작은 1을 골라 맨앞에 배치를 바꿉니다. //1회 1 10 5 8 7 6 4 3 2 9 //다음으로 작은 2를 골라 2번째에 배치합니다 //2회 1 2 10 5 8 7 6 4 3 9 //다음으로 작은 3를 골라 3번재에 배치합니다 //3회 1 2 3 10 8 7 6 4 5 9 //다음으로 작은 4를 골라 4번째에 배치합니.. 2024. 3. 11.
삽입정렬 숫자를 '적절한 위치'에 삽입해보면 어떨까? 다른 정렬들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 떄만 위치를 변경합니다. 위의 글들을 보면 ‘적절한 위치’,’필요할 때’ 같은 글 때문에 제대로 이해가 안됩니다. 예시를 보면 이해에 도움이 됩니다. 맨 처음부터 시작하여 각 원소를 차례대로 확인합니다. 현재 확인하는 원소가 이미 정렬된 리스트의 마지막 원소보다 크면, 삽입할 위치를 찾습니다. 삽입할 위치를 찾으면, 그 위치부터 마지막 원소까지 한 칸씩 뒤로 이동시킵니다. 빈 공간에 현재 확인하는 원소를 삽입합니다. 1. “1”은 가장 앞에 있기 때문에 삽입할 공간이 없습니다. 2. “10”은 1과 비교해서 a,b 중 ‘적절한 위치’에 삽입하면 됩니다. (b에 삽입합니다.) 3. “5”는 1과.. 2024. 3. 11.
버블정렬 옆에 있는 값과 비교해서 더 적은 값을 앞으로 보내면 어떨까? 1. 맨 처음부터 인접한 두 원소를 비교합니다. 2. 앞쪽 원소가 뒤쪽 원소보다 크면 두 원소를 교환합니다. 3. 마지막 원소까지 반복하여 1, 2 단계를 수행합니다. 4. 마지막 반복에서는 정렬이 되어있기 때문에 변화가 없습니다. 위의 이미지를 확인하면 마지막 ‘40’은 정렬되어있기 때문에 교환이 일어나지 않는다. 이보다 많은 횟수로 비교하는 정렬하는것이 있을까?라는 생각이 들고 비효율적이라고 생각이 든다. 2024. 3. 11.

티스토리툴바