[TIL]24-12-03

김슬아·2024년 12월 2일

📅 오늘의 기록 (2024.12.03)

🚀 오늘 한 일

[공부]
- 알고리즘 1문제 풀이 https://www.acmicpc.net/problem/10819
[문제 해결]
- 알고리즘 문제 안 N이 3개 부터 8개 까지 범위로 제한되어있어, 무식한 방법(브루트포스)으로 풀어도 풀릴것같아 한번 도전해봤는데 풀렸다.이게되네?그래서 실버 문제인건가보다..

🧐 새롭게 알게 된 것

핵심 포인트
- 첫번째는 배열의 모든 경우의 수(순열)을 구하기 위해 itertools라는 내장함수를 import 해서 썼다.
  -두번째는 실전 코테에서 내장함수를 몰라도 풀어야하기 때문에,
  백 트래킹 방법을 활용해서 풀었다.

활용 방법
- 첫번째 방식(내장함수 사용)

import itertools 

N=int(input())
arr=list(map(int,input().split()))
i=0
result=0
for perm in itertools.permutations(arr):
    temp=0
    perm_list = list(perm)
    for i in range(len(perm_list)-1):
        temp += abs(perm_list[i]-perm_list[i+1])
    temp = max(temp,result)
    result=temp

print(result)

두번째 방식(재귀함수를 이용한 백트래킹)

import sys
input= sys.stdin.readline
N=int(input())
arr=list(map(int,input().split()))
i=0
visited = [False]*len(arr)
pickednum=[]
result=0
def permutation(cnt,depth):
    global result
    if cnt ==depth:
        temp=0
        for i in range(len(pickednum)-1):
            temp += abs(pickednum[i]-pickednum[i+1])
        temp = max(temp,result)
        result =temp
        return
    for index in range(len(arr)):
        if visited[index]==False:
            visited[index]=True
            pickednum.append(arr[index])
            permutation(cnt+1,depth)
            # 백트래킹 하기 위해 되돌림
            pickednum.pop()
            visited[index]=False

permutation(0,len(arr))

print(result)