Algorithm TIL (240924)

> [백준] 후보 추천하기 (1713)

https://www.acmicpc.net/problem/1713

 

 

문제 풀이 과정

• 주어지는 조건에 따라 문제를 '구현'하면 되는 문제였다.
• 다만, 사진을 삭제하는 조건을 구현하는 부분을 코드로 구현하는 것이 어려웠다. 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고 그 자리에 새롭게 추천받은 학생의 사진을 게시한다를 구현하는 로직을 처음에 데크로 풀어야 하나? 하고 잘못 생각했던 점이 실패의 원인이었다고 생각한다.
• 핵심 아이디어 : stack에 넣고 추천 횟수가 가장 적은 학생의 사진 중, stack에서 최소 추천 횟수가 동일한 원소들 중 최소 인덱스를 삭제하면 된다.

 

문제 풀이

python

• index() : 배열에서 값의 위치를 찾아주는 함수이며, 중복된 값이 있으면 가장 최소의 위치를 리턴
• 배열의 삭제
  • del 배열[인덱스] : 배열에서 해당 인덱스 위치의 원소를 삭제 
  • remove() : 배열에서 해당 값을 삭제
  • pop() : 배열에서 해당 인덱스 위치의 원소를 삭제

# 후보추천하기
# 사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.

n = int(input()) # 사진틀의 개수
m = int(input()) # 추천 횟수
arr = list(map(int, input().split())) # 추천 학생 번호 배열 (순서대로)

cnt = [] # 총 학생의 개수는 20개까지
pictures = [] # 사진틀
oldest_idx = 0

for i in range(m) :
    # 추천받은 학생의 사진 게시
    if arr[i] in pictures :
        # 추천 받은 횟수 1추가
        cnt[pictures.index(arr[i])] += 1
        
    else :
        # 비어있는 사진틀이 없다면, 추천횟수가 가장적은 학생의 사진 삭제
        # 추천횟수가 가장적은 학생이 여러면인 경우 가장 오래된 사진을 삭제
        if len(pictures) >= n :
            idx = cnt.index(min(cnt)) # index 함수는 배열에서 값의 위치를 찾아주는 함수리며, 중복된 값이 있으면 가장 최소의 위치를 리턴
            pictures.pop(idx)
            cnt.pop(idx)
        pictures.append(arr[i])
        cnt.append(1)

pictures.sort()
print(' '.join(map(str, pictures)))

 

회고 및 느낀점

아이디어 수집 : 배열에서 최소의 인덱스 = 배열에 들어온지 가장 오래된 순서

 

 

---

> [백준] 외판원 순회

https://www.acmicpc.net/problem/10971

 

 

문제 풀이 과정

• '백트래킹' 을 이용한 현재 도시에서 모든 여행 경로 비용 계산
• n까지의 모든 도시들을 순회하면서 가장 적은 비용을 들이는 순회 최소 비용을 출력한다.
• 각 도시부터 시작하여 n개의 모든 도시를 돌도록 한다.

 

문제 풀이

python

• for문을 통해 n개의 모든 도시에 대해 탐색 함수를 수행한다.
  • 시작 도시 방문 여부 True로 변경 -> 함수 완료 후 시작 도시 방문 여부 False로 변경
• 시작(i) 도시에서 다른(j) 도시로 이동하는 for문을 돌릴 때, 방문한 적이 없으며, map[i][j]가 0이 아닌 경우 함수 수행
• 만일 모든 도시에 방문했으며, 마지막 도시에서 시작도시로 돌아올 수 있는 경우, 최소 비용값을 갱신한다.

# 외한원 순회문제

# 어떤 i에서부터 어떤 j로까지 가는 이동 비용 중 최소 비용을 출력한다. => dfs

n = int(input()) # 도시의 수
map = [list(map(int, input().split())) for i in range(n)] # 도시 이동 비용 행렬
visited = [False] * n

ans = int(1e9) # 최소 비용

# 각 시작 도시에서 드는 비용 계싼
def func(k,start,dist) :
    global ans
    # base condition
    if all(visited) and map[start][k] != 0 :
        ans = min(ans, dist+map[start][k])
        return
    
    for i in range(n) :
        if not visited[i] and map[start][i] != 0 :
            visited[i] = True
            func(k,i,dist+map[start][i])
            visited[i] = False

# i~ j까지 도시에서 모두 시작해본다.
for i in range(n) :
    visited[i] = True
    func(i,i,0)
    visited[i] = False
    
print(ans)

 

회고 및 느낀점

아이디어 수집 : 2중 배열에서의 백트래킹은 현재 시점(즉, 시작 단계)가 여러 개이므로 현재 시점에서 모든 후보군을 따라 들어가보며 확인하면 된다!