개발자 아지트

병목현상(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 모듈 사용방법 

두 가지 모두 테스트 코드를 작성할 때 필수적인 도구로서 각각의 역할이 있습니다.

1. JUnit 5:

• 테스트 프레임워크: JUnit은 자바에서 가장 널리 사용되는 테스트 프레임워크 중 하나이다. 버전 5에서는 JUnit Jupiter로 불리며, JUnit의 최신 버전이다. 
• 주요 특징:
  • 단위 테스트와 통합 테스트를 위한 풍부한 기능을 제공합니다.
  • 어노테이션 기반: @Test, @BeforeEach, @AfterEach와 같은 어노테이션을 통해 테스트 실행 전후의 동작을 정의할 수 있다. 
  • Assertions 및 Assumptions: 테스트에서 특정 조건을 검증할 수 있게 해주는 assertEquals, assertTrue 등의 메서드를 제공한다. 
  • 확장 가능한 아키텍처: 커스텀 확장 기능을 만들 수 있으며, 다양한 라이브러리와 쉽게 연동할 수 있다.

2. AssertJ:

• 테스트 검증 라이브러리: AssertJ는 JUnit의 Assertions 메서드보다 더 풍부하고 가독성이 좋은 메서드 체이닝 스타일의 Assertions를 제공합니다.
• 주요 특징:
  • 가독성: AssertJ의 검증 구문은 사람이 읽기 쉽게 설계되어 있습니다. 예를 들어 Assertions.assertThat(actual).isEqualTo(expected);와 같은 구문으로 검증할 수 있습니다.
  • 유연성: 다양한 타입의 데이터(List, Map, Optional 등)에 대한 검증 메서드가 제공되어 복잡한 조건도 쉽게 검증할 수 있습니다.
  • 메서드 체이닝: 다양한 검증 메서드를 체이닝하여 간결하고 직관적인 테스트 코드를 작성할 수 있습니다.

// JUnit 5에서 제공하는 어노테이션을 불러온다.
import org.junit.jupiter.api.Test; 

// AssertJ 라이브러리에서 제공하는 정적 메서드 assertThat을 불러옴 
// 이렇게 static import를 하면 메서드 클래스 이름 없이 바로 사용할 수 있다. 
import static org.assertj.core.api.Assertions.assertThat; 


// 테스트 클래스를 정의하는 부분
class MyServiceTest {
	
    // 해당 어노테이션을 통해 메서드가 테스트 메서드 임을 표시함
    // JUnit이 이 어노테이션이 붙은 메서드를 실행함 
    // JUnit 5의 어노테이션
    // 이 어노테이션이 붙은 메서드는 테스트 메서드로 실행됨
    @Test 
    void testService() {
    	// 테스트를 위해 필요한 데이터나 상태 설정
        // 준비 (Given)
        // 테스트 할 값을 actual 변수에 할당함
        String actual = "Hello World";
		
        
        // AssertJ라이브러리에서 제공하는 검증 시작 메서드
        // assertThat(actual)은 검증대상 (actual)을 지정함
        // 이후 체이닝 방식으로 다양한 검증 메서드를 연결할 수 있음 
        // 검증 (Then)
        assertThat(actual)
            .isNotNull() // 체이닝 메서드 중 하나로, actual이 null이 아닌지 검증, actual이 null이면 테스트 실패
            .startsWith("Hello") // actual 문자열이 "Hello"로 시작하는지 검증
            .endsWith("World") // actual 문자열이 "Word"로 끝나는지 검증 
            .isEqualTo("Hello World"); // actual 문자열이 정확히 "Hello World"인지 검증
    }
}

위의 예시에서 @Test 어노테이션은 JUnit 5에서 테스트 메서드를 나타내고, assertThat은 AssertJ에서 제공하는 검증 메서드이다. 이런 식으로 JUnit 5로 테스트 환경을 설정하고, AssertJ로 더 가독성 있는 검증을 수행할 수 있다.

package baseball;

import java.util.ArrayList;
import java.util.List;
import camp.nextstep.edu.missionutils.Randoms;
import camp.nextstep.edu.missionutils.Console;

public class Application {
    public static void main(String[] args) {
        List<Integer> computer = new ArrayList<>();


        while(true) {
            int exitval = 0;
            String num;
            String con;

            while (computer.size() < 3) {
                int ranValue = Randoms.pickNumberInRange(1, 9);
                if (!computer.contains(ranValue)) {
                    computer.add(ranValue);
                }
            }
//
            //System.out.println("computer:"+ computer);

            System.out.println("숫자 야구 게임을 시작합니다. ");

            System.out.println("숫자를 입력해주세요 : ");

            num = Console.readLine();
            if (num.length() != 3 || !num.matches("[1-9]{3}") || hasDuplicateDigits(num)) {
                throw new IllegalArgumentException();
            }
            // 첫 번째 자리수
            int tmpNum = Integer.parseInt(num);
            int one = (tmpNum / 100);

//                System.out.println("one:"+one);
            // 두 번째 자리수
            int two = ((tmpNum % 100) / 10);

//                System.out.println("two:"+two);
            // 세 번째 자리수
            int thr = (tmpNum % 10);
//                System.out.println("thr:"+thr);

            // 100의 자리 수가 같은 경우
            int checkS = 0;
            int checkB = 0;

            // 리스트를 계속 사용하고 싶다면:
            // 만약 리스트를 사용하고 싶다면, 리스트에 맞는 방식으로 처리하도록 코드를 수정해야 한다.
            // 예를 들어, 리스트의 요소에 접근하려면 배열이 아닌 리스트의 메서드(get() 등)를 사용해야 한다.
            if (one == computer.get(0)) {
                checkS += 1;
            } else {
                if (one == computer.get(1) || one == computer.get(2)) {
                    checkB += 1;
                }
            }

            //System.out.println("checkS"+ checkS+ "checkB"+ checkB);

            if (two == computer.get(1)) {
                checkS += 1;
            } else {
                if (two == computer.get(0) || two == computer.get(2)) {
                    checkB += 1;
                }
            }
            //System.out.println("checkS"+ checkS+ "checkB"+ checkB);

            if (thr == computer.get(2)) {
                checkS += 1;
            } else {
                if (thr == computer.get(0) || thr == computer.get(1)) {
                    checkB += 1;
                }
            }

            int t3check = 0;
            if (checkS == 3) {
                System.out.println("3스트라이크");
                System.out.println("3개의 숫자를 모두 맞히셨습니다! 게임 종료");
                System.out.println("게임을 새로 시작하려면 1, 종료하려면 2를 입력하세요.");
                con = Console.readLine();
                int tmpCon = Integer.parseInt(con);
                if (tmpCon == 2) {
                    //System.out.println("그만?");
                    exitval = 1;
                    break;
                }
                computer = new ArrayList<>();
                checkS = 0;
                t3check = 1;
            }

            if (checkS >= 1 && checkB >= 1) {
                System.out.println(checkB + "볼 " + checkS + "스트라이크");
            }

            if (checkS >= 1 && checkB == 0) {
                System.out.println(checkS + "스트라이크");
            }

            if (checkB >= 1 && checkS == 0) {
                System.out.println(checkS + "볼");
            }


            if (checkS == 0 && checkB == 0) {
                if (t3check != 1) {
                    System.out.println("낫싱");
                }
            }
            t3check = 0;


            if (exitval == 1) {
                break;
            }

        }

    }

    // 입력값의 숫자에 중복이 있는지 확인하는 메서드
    private static boolean hasDuplicateDigits(String input) {
        char[] chars = input.toCharArray();
        return chars[0] == chars[1] || chars[0] == chars[2] || chars[1] == chars[2];
    }
}

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

문제 해결 방법

이 문제는 문제 설명에 올라와있는대로 그대로 풀면 된다. 

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90도 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

다만 문제는 반시계 방향으로 90도씩 회전을 해야한다는 것이고, 

현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 발견되는 즉시!! 반시계 방향으로 90도 회전해야한다. 

코드 구현

정답 코드 

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
startY, startX, dir = map(int, input().split())
mapp = []
for i in range(n):
    mapp.append(list(map(int, input().split())))

dx=[0, -1, 0, 1] # 북 서 남 동
dy=[-1, 0, 1, 0] # 북쪽을 y, x 기준 1, 0으로 표기해서 틀렸음 ....... 정신차려!! 

def solutions(x, y, dir):
    cnt = 0 # 청소하는 칸의 개수 
    while 1:
        # 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
        if mapp[y][x] == 0:
            mapp[y][x]=9
            cnt+=1

        check = 0 # 주변 4칸이 모두 청소된 칸인지 확인용 1은 청소필요, 1은 청소 불필요 
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
        
            if mapp[ny][nx]==0:
                #청소 필요한 칸 발견
                check =1
                break
            
        if check == 1:
            # 반시계 방향으로 90도 회전
            dir=dir+1
            if dir==4:
                dir = 0
            sx=x+dx[dir]
            sy=y+dy[dir]
            
            if mapp[sy][sx]==0:
                # 전진함 
                x = sx
                y = sy
        
        # 청소가 필요 없는 경우 
        if check ==0:
            nny = y-dy[dir]
            nnx = x-dx[dir]
            
            if mapp[nny][nnx]==1:
                return cnt
            else:
                x=nnx
                y=nny

if dir ==1:
    dir = 3
elif dir ==2:
    dir =2
elif dir == 3:
    dir = 1
print(solutions(startX, startY, dir))

시간/공간 복잡도

시뮬레이션 문제라 고려하지 않았다. 

어려웠던 점

• 반시계 반향으로 회전하려면, 문제에서 제시한 방향 기준으로 델타 x, y의 배열을 미리 선언할 때 조심해야 한다. 
• 우측 상단 방향이 행, 열 값이 증가하는 상황이라면  북쪽 방향으로 가는것이 (1, 0)이겠지만 해당 문제의 경우, 우측 하단으로 가야 행, 열이 값이 증가하는 상황이다. 이런 경우 북쪽으로 가는 것은 (-1, 0)이다.

알게된 점

• 좌표 문제의 경우, 쪽이 행과 열을 증가시키는 쪽인지 잘 확인하고 이를 고려하여 문제를 풀어야한다. 
• 델타 x, y좌표 배열을 선언할 때도, 문제에서 관련 조건이나 방법을 제시하는지 잘 확인하여 선언해야 한다. 

*패리티 비트

정의: 정보 전달 과정에서 오류가 생겼는지 검사하기 위해 추가하는 비트

사용법: 전송하고자 하는 데이터의 각 문자에 1 비트를 더해 전송한다. 

예를들어서 "김민수" 라는 데이터가 있으면

김에 +1 = 8+1 = 9비트

지에 +1 = 8+1 = 9비트

연에 +1 = 8+1 = 9비트

이런식으로 각 문자에 1비트를 더해서 전송한다. 

종류: 짝수패리티, 홀수패리티

종류는 전송 시스템이나 프로토콜 설계하거나 설정할 때 미리 결정됨

송, 수신측에서 같은 규칙을 따를 수 있도록 사전에 합의 해야함

짝수패리티가 짝수개수를 다루기 쉬워서 일반적으로 더 많이 사용됨

종류는 전체 비트에서 1이 짝수개인지 홀수개인지에 따라 종류가 나뉜다는 의미이다. 

전체 비트에서 1의 개수가 (짝수, 홀수)에 맞도록 비트를 정하는 것

[짝수 패리티]

짝수 패리티 일 때 7비트 데이터가 1010001 (7자)라면?

1이 총 3개이므로, 1을 짝수로 맞춰주기 위해 1을 더해야 함 

만약 1의 개수가 짝수개라면? 0을 맨뒤에 추가한다. 

=> 11010001 (맨 앞이 패리티비트) (8자)

[홀수 패리티]

만약 데이터가 1010110이고, 1의 개수가 짝수라면, 홀수 패리티에서는 1의 개수가 홀수가 되도록 패리티 비트를 정해야함.

따라서 1을 추가해야함 1은 맨뒤에 추가함

만약 1의 개수가 이미 홀수라면, 패리티 비트로 0을 추가해 홀수를 유지한다. 

=> 10101101

지금 사이트에 있는 방식은 맨 앞에 추가하는 방식인데, 

패리티 비트를 맨 앞에 추가하는 것은 흔하지 않은 방식이고, 대부분 시스템이서는 패리티 비트를 맨 뒤에 추가함. 이것이 표준임.

이런 방식으로 검사하는 패리티 비트는 데이터를 수신 하는 쪽, 송신하는 쪽 모두에서 이뤄짐. 

만약 규칙이 맞지 않을 경우, 수신된 데이터에 오류가 발생한 것이라고 간주하고 처리함. 

오류가 발견되면 데이터 재전송을 요청하거나 오류를 알림.

앞에서 본 것처럼 패리티 비트는 단순한 오류 검출 매커니즘이라, 하드웨어나 소프트웨어에서 간단하게 구현할 수 있음

이 검사 과정은 보통 데이터 링크 계층이나 전송 계층에서 이뤄지고, 네트워크 카드나 모뎀, 통신 프로토콜 등에서 처리함

그러나,

패리티 비트는 1비트 오류만 검출할 수 있고, 2비트 이상의 오류는 검출하지 못하는 한계가 있다. 

예를들면, 

원래 데이터가 1010001 이고, 짝수 페리티를 사용하는 경우 전송데이터는 10100011이 되는데,

만약에 2비트 오류가 11100010 이런식으로 발생한 경우, 수신측에서 오류가 없다고 판단할 수 있음. 

또한 오류의 위치도 파악할 수 없음 

그래서 보다 복잡한 오류 검출 및 수정이 필요한 경우 CRC(Cyclic Redundancy Check), 해밍 코드 등의 다른 오류 검출 방식이 사용됨. 

*해밍코드 

정의:데이터 전송 시 1비트의 에러를 정정할 수 있는 자기 오류정정 코드를 말한다. 

페리티비트를 보고, 1비트에 대한 오류를 정정할 곳을 찾아 수정할 수 있다.

(패리티 비트는 오류를 검출하기만 할 뿐 수정하지는 않기 때문에 해밍 코드를 활용함)

사용법: 2의 n승 번째 자리인 1, 2, 4번째 비트가 패리티 비트라는 것 부터 시작함.

이 숫자로부터 시작하는 세개의 패리티 비트가 짝수인지, 홀수인지 기준으로 판별함. 

1, 2, 4 번째의 각 패리티 비트들은 데이터 내의 특정 비트 집합을 검사하는데, 

이때 비트 집합은 다음과 같다. 

1=> 1, 3, 5, 7 번째 비트 확인

2=> 2, 3, 6, 7번째 비트 확인

4=> 4, 5, 6, 7번째 비트 확인

비트를 확인할 때 앞에서 부터 읽는다. 

0011011

-> 이 방향 (1번째 비트 부터 시작)

짝수 패리티의 해밍코드가 0011011일때 오류가 수정된 코드는?

1. 1, 3, 5, 7 번째 비트 확인: 0101로 짝수이므로 '0'

2. 2, 3, 6, 7번째 비트 확인: 0111로 홀수이므로 '1'

3. 4, 5, 6, 7번째 비트 확인: 1011로 홀수이므로 '1'

역순으로 패리티 비트 110을 도출할 수 있음

10진법으로 바꾸면, 6으로, 6번째 비트를 수정하면 됨

0011001

재귀 함수란?

: 재귀 함수는 자기 자신을 호출하여 원래 문제에 속한 더 작은 하위 문제를 해결하는 함수이다.

이를 통해 문제를 반복적으로 분해하다가, 더 이상 분해할 수 없는 기본 조건(base condition)에 도달하면 함수 호출을 종료한다. 

재귀 함수의 장점과 단점은 무엇인가?

 장점

• 코드가 반복적인 구조를 가진 문제(예: 특정 패턴의 탐색)를 간결하게 작성할 수 있습니다.
• 문제를 작게 나누어 해결하는 경우 구현이 상대적으로 단순해집니다.

단점

• 잘못된 구현이나 불필요한 깊이의 호출이 발생하면 성능이 저하될 수 있습니다.
• 깊은 재귀 호출로 인해 프로그램이 강제 종료될 가능성도 있습니다.

 재귀 함수에서 재귀 깊이를 줄이기 위한 방법

재귀 함수는 깊이(호출의 반복 횟수)가 깊어질수록 성능에 악영향을 줄 수 있다.

이때, 재귀 깊이를 줄이기 위한 몇 가지 방법을 사용할 수 있다.

메모제이션(Memoization)
이전에 계산한 값을 저장해 두었다가 재사용하는 기법이다.

이를 통해 동일한 계산을 여러 번 반복하지 않게 되어 재귀 호출 횟수를 줄일 수 있다.

memo = {}
def fibonacci(n):
   if n in memo:
       return memo[n]
   if n <= 1:
       return n
   memo[n] = fibonacci(n-1) + fibonacci(n-2)
   return memo[n]

반복문으로 변환
재귀로 풀 수 있는 문제는 대부분 반복문을 통해 해결할 수도 있다.

반복문으로 변환할 경우, 재귀 함수 호출로 인한 추가적인 메모리 사용을 방지할 수 있다.

 def fibonacci_iterative(n):
       a, b = 0, 1
       for _ in range(n):
           a, b = b, a + b
       return a

최적화된 종료 조건 설정
재귀 호출의 종료 조건을 잘 설정하면 불필요한 깊은 호출을 방지할 수 있다.

특히, 매번 상태를 변경하거나 갱신하여 기본 조건에 빨리 도달하도록 설계해야 한다.

재귀 함수를 구현하는 절차

1. 기본 조건 설정 (Base Condition):

기본 조건은 재귀 호출이 끝나야 할 시점을 정의하는 것이다.

만약 기본 조건이 없다면, 함수가 계속해서 자기 자신을 호출하여 무한 루프에 빠지게 되고, 결국 스택 오버플로우 오류를 발생시킨다.

기본 조건은 문제의 가장 작은 단위를 처리하는 코드로 작성해야 하며, 일반적으로 재귀 호출의 종료를 의미합니다. 

2. 더 작은 문제로 분할:

재귀의 핵심은 문제를 작은 문제로 나누는 것이다. 원래 문제를 더 작은 하위 문제로 분할함으로써, 최종적으로 기본 조건에 도달할 수 있다. 하위 문제는 원래 문제와 동일한 성질을 가져야 한다. 이렇기 때문에 재귀 호출이 문제를 반복적으로 해결할 수 있게 되는 것이다. 

또한 각 재귀 호출에서 문제의 크기를 줄여야 한다는 것이다. 만약 문제의 크기가 줄어들지 않으면, 기본 조건에 도달할 수 없게 되어 함수가 계속해서 호출되는 문제가 발생한다.

3. 재귀 호출:

마지막 단계는 재귀적으로 자기 자신을 호출하는 것이다. 이때, 더 작은 문제를 해결하기 위해 동일한 함수를 호출하게 된다. 재귀 호출은 기본 조건에 도달할 때까지 계속되며, 기본 조건에 도달하면 결과가 반환되기 시작한다.

이 과정에서 주의할 점은, 함수가 재귀 호출을 할 때마다 상태가 변화해야 한다는 것이다. 그렇지 않으면 문제의 크기가 줄어들지 않아 무한 루프에 빠질 수 있다.

재귀 함수 구현 시 주의해야 할 점

1. 기본 조건을 확실하게 설정해야 한다.
2. 재귀 깊이 고려해야 한다. 

재귀 호출은 호출할 때마다 메모리의 스택 공간을 사용한다. 따라서 재귀 호출이 너무 깊어지면 메모리가 부족해질 수 있다. 특히, Python에서는 재귀 깊이가 기본적으로 제한되어 있어, 그 한도를 넘어서면 RecursionError가 발생한다.

따라서 재귀 깊이를 고려하여 설계해야 하며, 가능한 경우 반복문을 통해 문제를 해결하는 방법도 고려해야 합니다. 혹은 sys.setrecursionlimit() 함수를 사용해 최대 재귀 깊이를 조정할 수 있습니다.

import sys

# 재귀 깊이 제한을 늘리기
sys.setrecursionlimit(2000)

그러나 이 방법은 메모리 사용량을 늘리기 때문에 신중히 사용해야 한다.

3. 반복적 재계산을 방지해야한다. 
많은 재귀 함수에서 동일한 하위 문제를 여러 번 계산하는 경우가 발생할 수 있다. 이로 인해 중복 계산이 일어나고 성능이 크게 저하될 수 있다. 이를 방지하기 위해 메모이제이션(Memoization)을 사용하여 이미 계산된 값을 저장하고 재사용하는 방법을 고려해야 한다.

출처: "코딩 테스트 합격자 되기-박경록" 

7-1. 큐의 개념

큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 

일상생활에서 줄 서는 것이 큐 구조이다. 먼저 선 사람이 먼저 들어간다. 

이런 큐의 특징을 선입선출, FIFO(First in First out) 이라고 한다. 

큐도 스택처럼 꺼내는 연산을 팝, 삽입하는 연산을 푸시라고 한다. 

*큐의 특성을 활용하는 분야 

큐의 동작 방식은 프로그래밍 언어에서 많이 활용된다. 대표적으로 여러 이벤트가 발생했을때 발생한 순서대로 처리가 필요할 때 큐가 활용된다. 작업 대기열이나 이벤트 처리의 경우 큐 구조로 처리된다. 

큐의 ADT(abstract data type, 추상자료형)

*연산

*상태

front는 큐의 앞, rear는 큐의 뒤를 의미한다. 

큐는 앞에서 데이터를 꺼내고(팝), 뒤에서 데이터를 넣으므로(푸시) 이렇게 앞 뒤의 최종 데이터의 위치를 기억해야한다. 

초기에는 front와 rear모두 초깃값을 -1로 설정한다. 

*큐의 세부동작 이해하기 

푸시 연산 

1. isFull() 연산을 통해 현재 큐가 가득 찼는지 확인한다. 

2. 큐가 가득 차지 않았다면, rear을 +1 하고 다음 rear가 가리키는 위치에 값을 푸시한다. 

팝 연산

1. isEmpty() 연산을 통해 큐가 비었는지 확인한다. 해당 연산을 통해 front, rear의 값이 같은지 확인해서 큐에 원소가 없는데 팝하는 동작을 방지한다. 

2. 만약 큐가 비어있지 않다면 front을 +1 한다. 이렇게 하면 front, rear가 0으로 같아지고, 

3. isEmpty() 연산 시 큐가 빈것으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리할 수 있다. 

front의 다음 부터 rear까지만 큐가 관리하는 데이터라고 생각해야 한다. 

이런식으로 큐를 관리하다보면, 실제 data 공간에 비해 큐가 관리하는 데이터가 줄어들게 되면 메모리 공간을 낭비한 상황을 만날 수 있다. 이렇게 된 이유는 큐를 한 방향으로 관리하기 때문이다. 이렇게하면, fornt 이전의 부분을 활용할 수 없게된다. 

이를 개선하기 위해 원형 큐를 사용한다. 

코딩테스트에서 파이썬을 사용하면 그냥 리스트만 사용해도 충분하게 이런 형태들의 큐를 사용할 수 있다. 

* 큐 구현하기 

큐를 간단하게 구현하는 방식은 크게 2가지가 있다. 

1. 리스트를 활용하는 방식

queue = []

# 큐에 데이터 추가
queue.append(1)
queue.append(2)

# 큐의 맨 앞 데이터 제거, 스택과의 차이는 pop()에 인수로 0을 넣어 맨 앞 데이터를 제거했다는 점이다
first_item = queue.pop(0)
print(first_item) # 출력: 1

2. 덱을 활용하는 방식

from collections import deque

queue = deque()

# 큐에 데이터 추가 
queue.append(1)
queue.append(2)

# 큐의 맨 앞 데이터 제거
first_item = queue.popleft()
print(first_item) # 출력: 1

실제로 큐를 구현할 때 덱을 사용하는 이유는 속도 때문이다. 

pop(0)을 10 만번하면 0.79초가 소요되고,

popleft()를 10 만번하면 0.007초로 매우 크게 차이가 난다. 

[문제]

1. 큐를 이용하여 주어진 데이터를 순차적으로 처리하는 알고리즘을 설계하고 구현하세요. 이 알고리즘의 시간 복잡도는 어떻게 되나요? 큐를 사용하지 않고도 데이터를 순차적으로 처리할 수 있는 다른 방법을 설명하세요.

=>

from collections import deque

queue = deque()

# cnt를 인덱스 삼아 순회 
cnt = 0
while queue:
	print(queue[cnt])
	# value = queue[cnt].popleft() # 팝 코드
    	# queue.append(value) # 푸시 코드

이 알고리즘의 시간 복잡도는 큐의 원소 개수가 n이라고 하면, O(N)이다. 

큐를 사용하지 않고도 데이터를 순차적으로 처리할 수 있는 다른 방법은 배열을 순회하여 순차적으로 처리하는 방법이 있다. 

2. 주어진 문자열에서 연속된 중복된 문자를 제거한 새로운 문자열을 반환하는 알고리즘을 설계하고 구현하세요. 단, 문자열 내에서 문자의 순서는 유지해야 합니다. 시간 복잡도를 분석하세요.

=> 

from collections import deque

test = 'aaappllee'
test = deque(test)
newT=[]

for i in range(len(test)):
        if not newT or newT[-1] != test[i]:
            newT.append(test[i])
print(newT)


#=> 이렇게 시도했더니 문자열 순서가 안맞는 문제가 있음
# check = 0
# ok = 0
# cnt = 0
# while 1:
#     if check == 0:
#         value = test.popleft()
#         rem = value
#         test.append(value)
#         check =1
#     else:
#         if test:
#             value = test.popleft()
#             if value == rem:
#                 ok = 1
#                 pass
#             else:
#                 test.append(value)
#                 rem = value
#                 ok = 0
        
#     # cnt+=1
#     # if cnt == len(test):
#     #     break
#     print(test)

# print(test)

큐의 크기가 n이라면 O(n) 인 시간복잡도를 가지는 알고리즘이다. 

3. 큐와 스택의 차이점을 설명하고, 각각의 자료구조가 적합한 상황을 예시와 함께 설명해보세요. 두 자료구조의 시간 복잡도에 대한 일반적인 차이도 설명하세요.

=>

*큐와 스택의 차이점

      큐: 앞에서도 pop할 수 있다. (먼저 들어간 것을 pop 할 수 있다.) 

      스택: 앞에서는 pop할 수 없다. (먼저 들어간 것을 pop 할 수 있다.) 뒤에서부터 pop할 수 있다. 

*각각의 자료구조가 적합한 상황

*각각의 구조가 적합한 상황의 예시

* 두자료구조의 시간 복잡도에 대한 일반적인 차이

  두 자료구조의 시간 복잡도에 대한 일반적인 차이는 다음과 같은 경우에서 확인할 수 있다.

  스택이 맨 앞에서 원소를 꺼내려고 할때 O(N)의 시간복잡도가 걸리지만, 큐의 경우 O(1)의 시간복잡도가 걸린다. 

4. 큐를 이용하여 우선순위가 있는 작업을 처리하는 방법에 대해 설명하세요. 우선순위가 높은 작업을 먼저 처리할 수 있는 자료구조의 동작 원리와 그에 따른 시간 복잡도를 설명해보세요.

* 큐를 이용해 우선순위가 있는 작업을 처리하는 방법

이때, 우선순위 큐(Priority Queue)를 사용할 수 있다. 우선순위 큐는 각 작업에 우선순위를 부여하고, 우선순위에 따라 요소를 삽입하고  삭제 처리하는 자료구조이다. 

* 우선순위 큐의 동작 원리

우선순위 큐는 요소를 큐에 추가하거나, 가장 높은 우선순위를 가진 요소를 큐에서 제거하는 동작이 있다. 

이러한 동작을 수행하기 위해 완전 이진 트리 구조를 가진 자료 구조인 힙(Heap)을 사용한다. 

(완전 이진 트리 구조란? 모든 레벨이 완전히 채워져 있으면서, 마지막 레벨만 왼쪽부터 차례대로 노드가 채워진 형태)

*힙의 종류

힙은 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 최소 힙(Min Heap), 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 최대 힙(Max Heap)이 있다. 

우선 순위 큐에서 작업을 처리할 때는, 우선순위에 따라 요소가 정렬된다. 우선순위가 가장 높은 요소가 루트에 위치하게 된다. 

이후에 우선순위가 높은 요소가 먼저 처리된다. 

* 우선순위 큐의 시간 복잡도

힙 (Heap)이란?

힙은 이진 트리 기반의 자료구조로, 최소 힙 (Min-Heap)과 최대 힙 (Max-Heap)으로 나뉜다. 

• 최소 힙: 각 부모 노드가 자식 노드보다 작거나 같은 값을 가지는 구조.
• 최대 힙: 각 부모 노드가 자식 노드보다 크거나 같은 값을 가지는 구조.

파이썬의 heapq 모듈은 기본적으로 최소 힙을 사용하며, heapify() 함수는 주어진 리스트를 이러한 힙 구조로 정렬한다. 

heapq.heapify()의 동작

heapify()는 주어진 리스트를 인덱스 0부터 힙의 조건에 맞게 재배치한다. 이때, 첫 번째 원소(인덱스 0)가 최소값을 가지도록 정렬된다.  힙은 완전 이진 트리의 성질을 가지기 때문에, heapify()의 시간 복잡도는 O(n)이다. 

사용 예시 

'''

우선순위 큐 구현

'''

import heapq

tasks = [(3, 'Task A'), (1, 'Task B'), (2, 'Task C'), (1, 'Task D')]

heapq.heapify(tasks)
result = [i[1] for i in tasks]


print(result)

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

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

문제 해결 방법

딕셔너리를 잘 활용하여 문제를 해결한다. 

코드 구현

정답 코드 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dic = {}
revDic = {}
for i in range(n):
    tmpS = input().strip()
    dic[i+1]=tmpS
    revDic[tmpS]=i+1

for i in range(m):
    tmpV = input().strip()
    if tmpV.isdigit():
        tmpV= int(tmpV)
        print(dic[tmpV])
    else:
        print(revDic[tmpV])

시간/공간 복잡도

O(n)

어려웠던 점

• 자료구조 조회할 때, 시간초과를 해결하기 위해서는 리스트보다 해시테이블을 구조인 딕셔너리 사용(O(1)) 이 더 빠르기 때문에 효과적이다.  

알게된 점

• 키 값을 통해 값을 찾거나 밸류 값을 통해 값을 찾아야 하는 경우, 두개의 딕셔너리를 활용하면 아주 효율적이다. 
• 문자열이 숫자 값인지 확인할때, 대상.isdigit()함수를 사용하면 확인할 수 있다. (숫자일 경우 True 반환)

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

문제 해결 방법

재귀함수 혹은 DP를 활용한다. 

코드 구현

정답 코드 

import sys
input = sys.stdin.readline
t = int(input())


def fibonacci(n, count):
    if n<=1:
        if n ==0:
            count[0]+=1
        if n==1:
            count[1]+=1

        print(count[0], count[1])
        return n
    
    a = 0
    b = 1

    for i in range(2, n+1):
        c = a + b
        a = b
        b = c


    print(a, b)
    return b 
        

for i in range(t):
    n = int(input())
    count = [0, 0]
    fibonacci(n, count)

# 0 1 1 2 3 5 8

시간/공간 복잡도

O(n)

최적화 및 개선

• 피보나치 함수 알고리즘을 구현할 때, 재귀함수로 구현후 시간 초과가 나면 DP로 구현하면 시간 복잡도를 줄일 수 있다.