뭐든 회상에 잠기는거보다 직접 부딛히는게 좋음 

[정답코드]

from collections import deque
import copy
def solution(name):
    answer = float("inf")
    name = list(name)
    
    origin=['A']*len(name)
    
    now = 0
    
    controll=0
    controll+=min(ord(name[now])-ord('A'), ord('Z')-ord(name[now])+1)#min(ord(name[now])-65, 90-ord(name[now])+1)
    
    origin[now]=name[now]
    q=deque([])
    q.append((now, controll, origin))
    while q:
        now, controll, origin =q.popleft()
        if origin == name:
            answer=min(answer, controll)
            continue

        check=0
        rcontroll = controll
        rnow=now
        while check<1:
            # 오른쪽으로 가는 경우, 
            rnow=rnow+1
            if rnow>=len(name):
                rnow=0
            # 값을 바꿀 필요가 있는 경우 
            if origin[rnow]!=name[rnow]:
                if 0<=rnow<len(name):
                    check=1
                    rcontroll+=min(ord(name[rnow])-65, 90-ord(name[rnow])+1)+1

                    break
                    #q.append((nnow, controll+1, origin))
            # 값을 바꿀 필요가 없는 경우 
            else:
                rcontroll+=1

        check = 0
        lcontroll = controll
        lnow=now
        while check<1:
            # 왼쪽으로 가는 경우,     
            lnow = lnow -1
            if lnow<0:
                lnow=len(name)-1
            # 값을 바꿀 필요가 있는 경우
            if origin[lnow]!=name[lnow]:
                if 0<=lnow<len(name) :
                    check = 1  
                    lcontroll+=min(ord(name[lnow])-65, 90-ord(name[lnow])+1)+1
                    break
            else:
                lcontroll+=1

        originl=origin[:]
        originr=origin[:]
        originl[lnow]=name[lnow]
        q.append((lnow, lcontroll, originl))
        originr[rnow]=name[rnow]
        q.append((rnow, rcontroll, originr))
            
    
    return answer

일단 이 문제는 그리디 문제이긴 한데, 그리디 하지 않다. 

from collections import deque
import copy
def solution(name):
    answer = float("inf")
    name = list(name)
    origin=['A']*len(name)
    now = 0
    controll=0
    controll+=min(ord(name[now])-65, 90-ord(name[now])+1)
    origin[now]=name[now]
    q=deque([])
    q.append((now, controll, origin))
    while q:
        # print('!', now, controll, origin)
        now, controll, origin =q.popleft()
        
        if origin == name:
            
            answer=min(answer, controll)
            #print('answer', answer)
            continue

        check=0
        rcontroll = controll
        rnow=now
        while check<1:
            # 오른쪽으로 가는 경우, 
            rnow=rnow+1
            if rnow>=len(name):
                rnow=0
            
            # 값을 바꿀 필요가 있는 경우 
            if origin[rnow]!=name[rnow]:
                if 0<=rnow<len(name):
                    check=1
                    # print('now controll', controll, 'plus', min(ord(name[nnow])-65, 90-ord(name[nnow])))
                    rcontroll+=min(ord(name[rnow])-65, 90-ord(name[rnow])+1)+1
                    #origin[rnow]=name[rnow]
                    break
                    #q.append((nnow, controll+1, origin))
            # 값을 바꿀 필요가 없는 경우 
            else:
                rcontroll+=1

        check = 0
        lcontroll = controll
        lnow=now
        # print('lnow1',lnow)
        while check<1:
            # 왼쪽으로 가는 경우,     
            lnow = lnow -1
            if lnow<0:
                lnow=len(name)-1
            # 값을 바꿀 필요가 있는 경우
            if origin[lnow]!=name[lnow]:
                if 0<=lnow<len(name) :
                    check = 1
                    # print('now controll', controll, 'plus', min(ord(name[nnow])-65, 90-ord(name[nnow])))
                    lcontroll+=min(ord(name[lnow])-65, 90-ord(name[lnow])+1)+1
                    #origin[lnow]=name[lnow]
                    break
                    #q.append((nnow, controll+1, origin))
            else:
                lcontroll+=1
        # print('lnow2',lnow)
        #print('lcontroll, rcontroll:', lcontroll-controll, rcontroll-controll, ',', lcontroll, rcontroll,'controll', controll)      
        if lcontroll<rcontroll:
            #print('hi', origin)
            origin[lnow]=name[lnow]
            #print('hi2', origin, 'lcontroll',lcontroll)
            q.append((lnow, lcontroll, copy.deepcopy(origin)))
        elif lcontroll>rcontroll:
            #print('hi', origin)
            origin[rnow]=name[rnow]
            
            #print('hi2', origin, 'lcontroll',lcontroll)
            q.append((rnow, rcontroll, copy.deepcopy(origin)))
        else:
            originl=copy.deepcopy(origin)
            originr=copy.deepcopy(origin)
            originl[lnow]=name[lnow]
            q.append((lnow, lcontroll, copy.deepcopy(originl)))
            originr[rnow]=name[rnow]
            q.append((rnow, rcontroll, copy.deepcopy(originr)))
            
        
    # print(controll)
    
    
    return answer

이렇게 작성한 코드에서

이런식으로 도저히 넘어가질 않았음.

그런데 내가 하루종일 찾은 테스트케이스는 모두 통과되는 상태임.

이건 진짜 근본적인 문제가 하나 있다 싶었다. 

내가 이 문제를 풀기위해 사용한 핵심 로직은 

"지금 당장 더 싼 쪽(왼쪽 vs. 오른쪽)만 골라서 다른 쪽은 아예 버린다"
(만약 두쪽 다 값이 같으면 둘다 살려줌)

이였고, 오히려 그리디한 그리디 분기(pruning) 로직임.

그런데 이게 문제를 해결할 수 없는 결정적인 오류였음. 

이렇게 하면, 현재 상황에서 비용이 더 큰 쪽 경로를 전혀 탐색하지 않는데, 이 경우에서 만약 나중에 더 긴 A 구간이 나와버리면,  “한 번에 건너뛰어서” 전체 이동 횟수를 줄여 줄 수도 있는 상황을 전부 잘라 버림. 

결과적으로, 단편적인 부분에서 싸 보인다고 더 비싼 쪽 경로를 잘라 버리는 순간, 전역 최적해를 놓치게 되는거임;

결국 더 싼쪽 골라서 q에 넣기보다는 아예 저 조건 싹 지워버렸음

느낀점 : 그리디 문제도 깊게 생각할 부분이 있구나 하는것을 알게되었음.

병목현상(Bottleneck)이란?

현실 세계에서 병목은 병의 목 부분이 좁아 액체가 병에서 천천히 나오는 것을 비유한 것이다. 병의 몸통은 넓어 많은 양의 액체를 담을 수 있지만, 목이 좁아져 한 번에 흐를 수 있는 양이 제한되는 것처럼 컴퓨터 시스템에서도 병목현상이 발생하면 처리 능력이 낮아지고 제한된다. 

컴퓨터 시스템에서 병목현상은 시스템의 처리 속도를 제한하거나 성능 저하를 유발하는 가장 느린 부분을 뜻한다. 

이 현상은 시스템의 여러 구성 요소 중 특정 부분이 다른 부분에 비해 처리 속도가 느려 전체 시스템의 성능에 부정적인 영향을 미칠 때 발생한다. 

병목현상의 예시

현실세계에서의 병목 현상

• 고속도로에서 모든 차선이 잘 흐르다가 톨게이트에서 줄을 서서 기다리는 상황에서 줄이 늘어나는 톨게이트가 병목임.

서버에서의 병목현상:

• DB 부하: 서버 요청이 많아져 DB 조회나 쓰기 작업이 느려지면, 전체 시스템 속도가 느려짐.
• API 지연: 하나의 API가 처리 속도가 느리면, 다른 API 요청들도 대기하게 되어 응답 시간이 길어짐.

네트워크에서의 병목현상:

• 데이터가 네트워크를 통해 전달될 때, 특정 라우터나 네트워크 장치의 처리 용량이 한계에 도달하면 병목이 발생함.

개발 프로세스에서의 병목현상:

• 팀의 특정 작업이 완료되지 않아 다른 작업들이 지연되는 상황.
  • 예시: 백엔드 API 개발이 늦어져 프론트엔드 개발이 멈춰 있는 경우.

병목현상의 원인

하드웨어 문제:

• CPU, 메모리, 디스크, 네트워크 등 자원의 제한
• 예: DB 서버의 CPU가 과부하 상태일 경우

소프트웨어 문제:

• 비효율적인 코드, 잘못된 알고리즘, 동시성 문제 등
• 예: 불필요한 중복 요청이나 반복 계산

설계 문제:

• 시스템 설계 단계에서 특정 구성 요소에 부하가 몰리도록 설계된 경우
  • 예시: 모든 요청이 한 곳으로 집중되는 단일 장애점(Single Point of Failure)

병목현상을 해결하는 방법

분석 및 모니터링:

• 성능 테스트 도구(JMeter, Locust)를 사용하여 병목 구간을 찾아냄
• 서버 로깅, APM(Application Performance Monitoring) 도구를 활용함

최적화:

• 코드 개선: 비효율적인 로직을 최적화함
• 데이터베이스 최적화: 인덱스 추가, 쿼리 개선 등
• 캐싱 도입: 자주 사용하는 데이터를 캐시에 저장하여 DB 부하를 감소시킴

리소스 확장:

• 더 좋은 서버로 업그레이드하거나 서버를 추가함
• CDN(Content Delivery Network)이나 로드 밸런싱 활용
  
  

병목을 해결하면 시스템 전체의 성능이 대폭 향상됨

import heapq

n, m = map(int, input().split())
tmp = list(map(int, input().split()))

heapq.heapify(tmp)

for i in range(m):
    # 최소값 두 개 꺼내기
    smallest1 = heapq.heappop(tmp)
    smallest2 = heapq.heappop(tmp)
    
    # 두 값을 합친 후 다시 삽입
    summ = smallest1 + smallest2
    heapq.heappush(tmp, summ)
    heapq.heappush(tmp, summ)
    
print(sum(tmp))

이를 이해하기 최소힙을 이해하기 좋은 백준 문제 

: 15903 카드 합체 놀이(https://www.acmicpc.net/problem/15903)

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

문제 해결 방법

파이썬에서는 힙 자료구조를 heapq 를 통해 제공한다. 이때 최소힙 기능만 사용할 수 있고, 최대힙 기능은 지원하지 않는다. 

최소값일 수록 우선순위를 가지고 맨 앞에 배치되니, 최대 힙을 사용하고 싶으면 값들을 넣을 때 -를 붙여 넣고, 출력할때는 -를 달아서 출력하면 최대힙 처럼 사용할 수 있다. 

코드 구현

정답 코드 

'''
# 최대 힙
'''
import heapq
import sys
input = sys.stdin.readline
n = int(input())

tmp = []
for i in range(n):
    value = int(input())
    if value !=0:
        heapq.heappush(tmp, -value)
    else:
        if not tmp:
            print(0)
        else:
            print(-heapq.heappop(tmp))

시간/공간 복잡도

log(n)

어려웠던 점

알게된 점

• heapq 모듈 사용방법