• multilevel Queue : 공정 X, 차별적임

  • Ready queue를 여러 개로 분할
    • foreground(interactive한 job을 넣음)
    • background(barch-no human interaction 을 넣음)
      • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
      • foreground => RR
  • background => FCFS
  • queue에 대한 스케줄링이 필요
    • Fixed priority scheduling (=> 우선순위에 따라 엄격하게 우선순위가 높은 큐가 비어야 낮은 큐 실행)
      • serve all from foreground then from background
      • possibility of starvation
      • time slice (=> starvation이 발생하지 않음)
        • 각 큐에 CPU time을 적절한 비율로 할당
      • Eg., 80% to foreground in RR, 20% to background in FCFS

• multilevel Feedback Queue

  • 프로세스가 다른 큐로 이동 가능
  • 에이징(aging)을 이와 같은 방식으로 구현할 수 있다
  • multilevel-feedback-queue scheduler를 정의하는 파라미터들
    • Queue의 수
    • 각 큐의 scheduling algorithm
    • process를 상위 큐로 보내는 기준
    • process를 하위 큐로 내쫒는 기준
    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

  

=> 여기까지는 CPU가 한개일 때

Multiple-Processor Scheduling

• CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐

• Homogeneous processor인 경우

  • Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있따
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐

• Load sharing

  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법

• Symmetric Multiprocessing(SMP)

  • 각 프로세서가 각자 알아서 스케줄링 결정

• Asymmetric multiprocessing

  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

• Hard real-time system : 정해진 시간 안에 반드시 끝내도록 스케줄링해야함

• Soft real-time system : 일반 프로세스에 비해 높은 priority를 갖도록 해야함

Thread Scheduling

• Local Schduling : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정 => OS가 스케줄하는게 아니라 사용자 프로세스가 직접 어느 thread에 CPU를 줄지 결정. OS는 thread의 존재를 모름

• Global Schedulig : Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정 => OS가 thread의 존재를 앎

스케쥴링 알고리즘 평가

Queuing models (이론적인 방법)

(server = CPU)

• 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산

Implementation (구현) & Measurement (성능 측정)

• 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

Simulation (모의 실험)

• 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교 (trace: 실제 프로그램을 돌려서 뽑은 input data가 될 수 있음)

• 동기식 입출력 (synchronous I/O)

  • I/O 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램에 넘어감
  • 구현 방법 1
    • I/O가 끝날 때까지 CPU를 낭비시킴
    • 매시점 하나의 I/O만 일어날 수 있음
      • 구현 방법 2
      • I/O가 완료될 때까지 해당 프로그램에게서 CPU를 뺴앗음
    • I/O 처리를 기다리는 줄에 그 프로그램을 줄 세움
    • 다른 프로그램에서 CPU를 줌

• 비동기식 입출력 (asynchronous I/O)

  • I/O가 시작된 후 입출력 작업이 끝나기를 기다리지 않고 제어가 사용자 프로그램에 즉시 넘어감

=> 두 경우 모두 I/O의 완료는 인터럽트로 알려줌

DMA (Direct Memory Access)

• 빠른 입출력 장치를 메모리에 가까운 속도로 처리하기 위해 사용
• CPU의 중재 없이 device controller가 device의 buffer storage의 내용을 메모리에 block 단위로 직접 전송
• 바이트 단위가 아니라 block 단위로 인터럽트를 발생시킴

서로 다른 입출력 명령어

• I/O를 수행하는 special instruction에 의해 (일반적인 방식) : memory instruction 따로, I/O 장치 instruction 따로
• Memory Mapped I/O에 의해 : memory 주소에 연장 주소(device I/O를 가리킴)를 붙임

저장장치 계층 구조

Registers > Cache Memory(SRAM) > Main Memory(DRAM) > Magnetic Disk > Optical Disk > Magnetic Tape 왼쪽을 갈수록, 속도가 빠르고 가격이 비싸고 용량이 적다

Primary => 휘발성, CPU에서 직접 접근 가능(바이트 단위로 접근 가능해야함) => 실행 가능 Secondary => 비휘발성, CPU에서 직접 접근 불가능(섹터 단위로 접근) => 실행 불가능

프로그램의 실행 (메모리 load)

=> 실제로는

• File System: 비휘발성 저장공간
• 프로그램은 File System에 실행 파일 형태로 저장되어 있고, 이를 실행하면 메모리에 올라가 프로세스가 된다. 정확히 말하면, 물리적인 메모리에 프로그램이 바로 올라가는 것이 아니라 가상 메모리 단계를 추가로 거친다. 이때 독자적인 메모리 주소 공간이 형성되는데, 이 공간에는 Code, Data, Stack 영역이 있다.

Code: CPU에서 실행할 기계어 코드를 저장한다. Data: 전역 변수 등 프로그램이 사용하는 데이터를 저장한다. Stack: 함수가 호출될 때 호출된 함수의 수행을 마치고 복귀할 주소 및 데이터를 임시로 저장한다.

그 다음 가상 메모리에서 물리적인 메모리로 프로그램이 올라가는데, 메모리 낭비를 방지하기 위해 프로그램 중 당장 실행에 필요한 부분만 올라가고, 그렇지 않은 부분은 디스크 중 메모리의 연장 공간으로 사용되는 스왑 영역에 내려 놓는다. 즉, 주소 공간을 쪼개서 어떤 부분은 메모리에 있고, 어떤 부분은 스왑 영역에 있게 된다.

커널 주소 공간의 내용

사용자 프로그램이 사용하는 함수

• 사용자 정의 함수: 자신의 프로그램에서 정의한 함수

• 라이브러리 함수: 자신의 프로그램에서 정의하지 않고 가져다 사용한 함수 자신의 프로그램 실행 파일에 포함되어 있다.

=> 위의 두 개는 프로그램 내에서 실행됨, 유저 모드에서 동작

• 커널 함수: 운영 체제 프로그램의 함수 커널 함수의 호출 = 시스템 콜 당연하지만, 주소 점프를 할 수 없으므로 인터럽트 라인을 세팅하여 CPU에게 제어권을 넘겨야 한다. => 시스템 콜, 커널 모드에서 동작

참고

https://steady-coding.tistory.com/513#google_vignette

https://school.programmers.co.kr/learn/courses/30/lessons/12946?language=python3

해결방법

https://shoark7.github.io/programming/algorithm/tower-of-hanoi 핵심은 재귀였다!!! 위의 블로그 글을 여러번 읽으면서 이해했다. 재귀는 정말 어렵고 신비롭다...

코드

def solution(n):
    answer = []
    def hanoi(N, start, to, via):
        if N == 1:
            answer.append([start, to])
            return
        hanoi(N-1, start, via, to)
        answer.append([start, to])
        hanoi(N-1, via, to, start)

    hanoi(n, 1, 3, 2)
    return answer

n = 2
print(solution(n))

• 전송 제어 프로토콜(Transmission Control Protocol, TCP)은 인터넷에 연결된 컴퓨터에서 실행되는 프로그램 간에 통신을 안정적으로, 순서대로, 에러없이 교환할 수 있게 한다.
• TCP는 UDP보다 안전하지만 느리다 (체감은 어려움)
• 안정성을 필요로 하지 않는 애플리케이션의 경우 일반적으로 TCP 대신 UDP를 사용함
• 상대방에게 연결 상태를 계속 물어보는 특징이 있음
• Offset: 헤더의 길이를 의미
• Reserved: 예약된 필드, 사용하지 않음
• Window: 남아있는 TCP 버퍼 공간이 얼마나 있는지 정보를 담음 (요청 보내는 측에게 어느 정도 크기의 데이터 보내도 되는지 알려줌)

TCP 플래그 (중요)

U A P R S F 만 알면 된다

• 플래그 => 연결 상태, 응답 메시지 등을 나타냄

• U : urgent flag, 지금 보내는 메시지에 우선순위가 높은 메시지가 담겨 있다는 표시, 이 자리가 1이면 급하다는 의미

  • Urgent Pointer랑 같이 쓰임

• A : ack flag, 승인 비트

  • OK, 보내도 됨~

• P : 밀어넣기 비트, TCP 버퍼가 일정 크기만큼 쌓여야 전송하는데 상관없이 데이터를 밀어넣겠다는 의미 (많이 사용X)

• R : reset 비트, 상대방과 연결이 되어있는 상태에서 연결 관계를 초기화하자는 의미

• S : sync 비트, 동기화 비트, 상대방과 연결을 시작할 때 무조건 사용하는 플래그, 서로 상태를 동기화시키는 용도

• F : finish 비트, 연결을 끝내는 비트

• TCP 플래그 예시

TCP 3Way Handshake

(웹 통신, 파일 전송, 게임 => 모두 TCP 통신) 둘 사이 연결을 수립하는 과정 TCP를 이용한 데이터 통신을 할 때 프로세스와 프로세스를 연결하기 위해 가장 먼저 수행되는 과정

1. 클라이언트가 서버에게 요청 패킷을 보냄
2. 서버가 클라이언트의 요청을 받아들이는 패킷을 보냄
3. 클라이언트는 이를 최종적으로 수락하는 패킷을 보냄 => 3Way Handshake

• 각 단계에서 SYN, ACK 플래그 숫자 규칙
  • 처음에 S: 랜덤값, A: 0
  • 두번째 S: 랜덤값, A: 이전 S값 + 1
  • 세번째 S: 이전 A, A: 이전 S값 + 1

TCP를 이용한 데이터 전송 과정

3Way handshake를 해서 연결이 된 후, 페이로드(데이터)를 포함한 패킷을 주고 받는 경우

1. 보낸 쪽에서 또 보낼 때(클라이언트의 요청)는 SYN 번호, ACK 번호가 그대로
2. 받는 쪽(웹 서버)에서 SYC 번호는 받은 ACK 번호가 된다
3. 받는 쪽(웹 서버)에서 ACK 번호는 받은 SYC 번호 + 데이터 크기

TCP의 연결 상태 변화

이 중에서 LISTEN, ESTABLISHED만 중요

• LISTEN : 포트 번호를 열어놓고 있는 상태 (서버 쪽에서 프로그램이 사용하고 있는 상태), 클라이언트의 요청을 계속 듣고 있는 상태
• ESTABLISHED : 연결이 수립된 상태 (3way handshake 끝나면)

TCP 프로토콜 분석 실습

1. wireshark를 연다
2. 현재 통신하고 있는 것을 클릭한다 (ex: Wi-Fi)
3. 상단 필터에 tcp를 검색한다
4. 인터넷으로 어딘가 들어가본다, 상단에서 (패킷 캡쳐 정지)를 클릭한다.
5. 아래와 비슷한거 찾는다
6. 우클릭, 따라가기 > TCP 스트림 클릭한다 => 통신 흐름이 쭉 나옴
7. 상단바에서 통계 > 플로 그래프를 클릭한다 (표시 필터로 제한 클릭)
8. 수업 자료와 같은 TCP 통신 플로우를 확인할 수 있다 (처음 3way handshake => 데이터 주고 받음)

• 컴퓨터끼리는 IP주소로 통신한다
• IP주소는 3계층에서 쓰는 주소 체계, 논리적 주소
• MAC주소는 2계층에서 쓰는 주소 체계, 물리적 주소

3계층의 기능

• 멀리 떨어진 곳에 존재하는 네트워크(다른 네트워크 대역)까지 어떻게 데이터를 전달할지 제어하는 일을 담당

• 가까운 네트워크 대역: LAN

• LAN —— (WAN) —— LAN

• 대표적인 장비: 라우터 (2계층 대표적인 장비: 스위치)

• 발신에서 착신까지의 패킷의 경로를 제어함

• powershell에서 Ipconfig 쳐보면 현재 IP 주소를 확인할 수 있음

• IPv4 주소: 현재 PC에 할당된 IP주소
• 서브넷 마스크: IP주소에 대한 네트워크의 대역을 규정하는 것
• 게이트웨이 주소: 외부와 통신할 때 사용하는 네트워크 출입구 ⇒ 이렇게 있으면 멀리 있는 네트워크와 통신할 수 있음

3계층 프로토콜

• ARP 프로토콜
• IPv4 프로토콜 (IPv6와 완전히 다른 프로토콜)
• ICMP 프로토콜

일반적인 IP 주소 (=IPv4 주소)

Classful IP 주소

• 필드 4개, 콤마(.) 으로 구분
• 내부는 이진수이지만 십진수로 기재
• 한 필드당 1byte(=8bit) ⇒ 한 필드당 0 ~ 255까지 가능)
• 옛날, 초창기 방식임

• A 클래스
  • 첫번째 필드만 네트워크 대역 구분에 쓰임(=> A 클래스의 네트워크 대역은 128가지 있을 수 있음)
  • 두번째~네번째 필드는 하나의 네트워크 대역 내의 PC 종류를 구분하는데 쓰임 (=> 0.0.0 -> 255.255.255 : 256256256 개의 PC 구분 가능함)
  • 구분 가능한 네트워크 대역 수 << 구분 가능한 PC 수 => 엄청나게 규모가 큰 네트워크 대역에서 사용하는 IP 주소체계
• B 클래스
  • 두번째 필드까지 네트워크 대역 구분에 쓰임 (=> A클래스보다 구분 가능한 네트워크 대역이 늘어남)
  • 세번째, 네번째 필드는 하나의 네트워크 대역 내의 PC 종류를 구분하는데 쓰임 (=> 256*256 개의 PC 구분 가능함)
• C 클래스
  • 세번째 필드까지 네트워크 대역 구분에 쓰임 (=> A클래스보다 구분 가능한 네트워크 대역이 훨씬 늘어남)
  • 네번째 필드는 하나의 네트워크 대역 내의 PC 종류를 구분하는데 쓰임 (=> 256개의 PC 구분 가능함)
  • 일반적으로 가장 많이 사용됨
• D 클래스
  • 멀티캐스트용으로 남겨둔 주소
• E클래스
  • 실험용으로 남겨둔 IP주소

⇒ 문제점: 낭비가 심하다

ex) A클래스를 한 장소에서 사용한다고 하면, 하나의 네크워크 대역을 차지할텐데, 해당 네트워크 대역에 연결된 컴퓨터가 10대라고 하면, (256256256 – 10)개의 IP주소가 쓰이지 못하고 낭비된다.

Classless IP주소

• 하나의 큰 네트워크를 여러 개의 작은 네트워크로 쪼개서 쓰자.
• 서브넷 마스크로 (어디까지가 네트워크 대역에 대한 구분)이고 (어디서부터가 PC(=호스트) 구분)을 위한 IP 주소인지 알 수 있음
• 규칙
  • 8bit * 4로 이루어져 있음
  • 2진수로 표기했을 때 1로 시작해야함
  • 1과 1 사이에는 0이 올 수 없음
  • 1의 위치 = 네트워크 대역 구분에 쓰이는 IP 주소 위치
  • 0의 위치 = PC 구분에 쓰이는 IP 주소 위치 ex) 255.255.255.192 => 1111111.11111111.11111111.11000000
• 예시
  • IP 주소에서 1111111.11111111.11111111.11000000 => 이 부분은 네트워크 대역 구분에 쓰임 (256256256*4가지)
  • IP 주소에서 1111111.11111111.11111111.11000000 => 이 부분은 PC 구분에 쓰임 (64가지)
  • 서브넷마스크가 255.255.255.0(=1111111.11111111.11111111.00000000)이면 C 클래스를 의미함

⇒ 이렇게 해도 이진수 기준이라서 낭비가 됨

ex) 20대 PC가 있는데 255.255.255.224 (=1111111.11111111.11111111.11100000) 서브넷마스크를 쓰면 32대 구분이 가능해서 12개의 IP주소가 낭비된다

• 한 필드에 16bit를 담을 수 있는 IPv6를 쓰자는 이야기가 나왔다.

사설 IP와 공인 IP

• 현재 사용하는 IPv4의 개념
• 공인IP 1개당 256256256*256개의 사설IP가 생길 수 있다
• 공인 IP : 인터넷 세상, 즉, 네트워크 통신망과 통신할 때 사용하는 IP 주소. 인터넷과 통신할 때 같은 네트워크 대역에 있으면 하나의 IP 사용
• 사설 IP : 같은 네트워크 대역에서 사용하는 IP 주소
• NAT(Netword Address Translation) : 특정 IP를 특정 IP로 변환하는 기술 ⇒ 공유기
• 집에 인터넷 설치하는건 공유 IP 하나를 돈 주고 사는 개념임

• 실제 인터넷 세상에서는 공인 IP로만 통신 ⇒ 외부 네트워크 대역에서 사설 IP 대역은 보이지 않음

• 개인 PC에서 어떠한 요청을 보내면(사설IP → 공인IP → 바깥 세상) 공유기가 NAT 테이블에 기록
• 응답이 오면, NAT 테이블을 보고 요청 보냈던 사설 IP로 응답 보내줌
• 응답이 왔는데, NAT 테이블에 기록된 요청이 없으면 공유기가 응답을 받음(안 보내줌)
• 요청이 있어야만 응답이 외부에서 내부로 들어올 수 있어서 서버는 사설 IP를 잘 쓰지 않는다 ⇒ 포트포워딩이라는 추가적인 설정을 하면 가능

특수한 IP 주소

• 0.0.0.0 : 나머지 모든 IP
  • IPv4 경로 테이블에서 네트워크 대상에 적힌 IP 주소들 외의 모든 IP
• 127.0.0.1 : 나 자신을 나타내는 주소 (localhost)
• 게이트웨이 : 일반적으로 공유기의 주소, 외부랑 통신할 때 쓰는 기본 IP

https://school.programmers.co.kr/learn/courses/30/lessons/12952

풀이과정

N-Queen은 아주 유명한 백트래킹 문제인데... 배웠는데... 풀지 못했다...

인터넷 세상에서 도움을 받았다.

N-Queen의 문제와 해결방법은 아주 심플하다

Queen 은 가로, 세로, 대각선으로 움직일 수 있다 Queen이 서로 한번에 공격할 수 없는 위치에 배치할 수 있는 방법의 수를 구하라 => 이전에 놓은 곳과 같은 열, 대각선에 놓을 수 없음

코드 비교

def solution(n):
    answer = 0
    row = [0] * n

    def Queen(x):
        nonlocal row, answer
        if x == n:
            # print(row)
            answer += 1
            return

        for y in range(n):
            row[x] = y
            for i in range(x):
                # 위의 행에서 y 열에 퀸을 놓은 적이 있거나 대각선 위쪽에 퀸이 있는지 확인
                if row[i] == y or abs((x - i) / (y - row[i])) == 1:
                    break
            else:
                Queen(x+1)
    Queen(0)

    return answer

위의 풀이는 for문을 이용하고 각 행의 어떤 열에 퀸이 놓였는지 기록하는 row 배열이 존재한다.

갹 행마다 모든 열에 퀸을 배치해보고 현재 행보다 위쪽 행을 순회하면서 같은 열 또는 대각선에 퀸이 존재하는지 확인한다. 없으면 다음행으로 진행 있으면 해당 열에는 놓을 수 없으므로 다른 열에 놓아본다

각 행마다 모든 열에 퀸을 배치한 후, 이전 행을 모두 확인하는 것이라 시간이 오래 걸리는 듯 하다.

def solution(n):
    check_col = [False] * 100; check_d1 = [False] * 100; check_d2 = [False] * 100
    def process(row):
        answer = 0
        if row == n+1:
            return 1
        for i in range(1, n+1):
            d1 = row+i
            d2 = n + (row - i)
            if check_col[i] == False and check_d1[d1] == False and check_d2[d2] == False:
                check_col[i] = True
                check_d1[d1] = True
                check_d2[d2] = True
                answer += process(row+1)
                check_col[i] = False
                check_d1[d1] = False
                check_d2[d2] = False
        return answer

    answer = process(1)

    return answer

위의 풀이는 퀸이 놓인 열, 대각선을 미리 체크해서 True인 곳은 뛰어넘는 방식이고 재귀함수를 사용했다. 윗 행을 모두 확인해야하는 과정이 빠지면서 훨씬 코드가 효율적으로(빠르게) 동작한다.

대각선은 (행 + 열) 값이 같거나 (행 - 열) 값이 같다는 점을 잘 기억하고 이용해야겠다.

https://school.programmers.co.kr/learn/courses/30/lessons/135807

풀이과정

1. 각 배열의 최대공약수를 구한다
2. 최대공약수 약수의 배열을 만든다
3. 약수의 배열 원소 중 상대 배열을 나눌 수 없는 값을 answer로 업데이트 한다
4. 이때, 기존 answer과 비교해서 큰 값만 남긴다

이렇게 어렵고 복잡하게 풀고 나서 다른 사람의 풀이를 보니, 자신의 배열의 약수이고 상대 배열을 나눌 수 없는 수 중 가장 큰 수가 답이 되므로 최대공약수만 비교하면 되는 것이었다..! (예를 들어 42는 50으로 나누어 떨어지지 않는다. 왜냐면, 50이 더 큰 수니까.)

코드

# 프로그래머스 Lv2 숫자 카드 나누기
import math

# arrayA의 약수 중 arrayB를 나눌 수 없거나
# arrayB의 약수 중 arrayA를 나눌 수 없는 숫자 a 중 가장 큰 값, 없으면 0
def solution(arrayA, arrayB):
    answer = 0
    gcd_A = arrayA[0]
    gcd_B = arrayB[0]
    i = 1
    while i < len(arrayA):
        gcd_A = math.gcd(gcd_A, arrayA[i])
        gcd_B = math.gcd(gcd_B, arrayB[i])
        i += 1

    if gcd_A == 1 and gcd_B == 1:
        return 0

    div_A = []
    div_B = []
    if gcd_A != 1:
        a = 2
        while a < (gcd_A)**(1/2):
            if gcd_A % a == 0:
                div_A.extend([a, gcd_A//a])
            a += 1
        div_A.append(gcd_A)
    if gcd_B != 1:
        b = 2
        while b < (gcd_B)**(1/2):
            if gcd_B % b == 0:
                div_B.extend([b, gcd_B//b])
            b += 1
        div_B.append(gcd_B)

    # print(div_A, div_B)
    while div_A:
        tmp = div_A.pop()
        if all([i % tmp != 0 for i in arrayB]):
            answer = max(answer, tmp)

    while div_B:
        tmp = div_B.pop()
        if all([i % tmp != 0 for i in arrayA]):
            answer = max(answer, tmp)

    return answer

arrayA = [10, 17]
arrayB = [5, 20]
arrayA = [10, 20]
arrayB = [5, 17]
# arrayA = [14, 35, 119]
# arrayB = [18, 30, 102]
print(solution(arrayA, arrayB))

다른 사람의 풀이

from functools import reduce
from math import gcd


def solution(nums1, nums2):
    gcd1, gcd2 = reduce(gcd, nums1), reduce(gcd, nums2)
    answer = []
    if all(each % gcd2 for each in nums1):
        answer.append(gcd2)
    if all(each % gcd1 for each in nums2):
        answer.append(gcd1)
    return max(answer) if answer else 0

오 파이써닉... reduce 함수라는 것을 처음 접했다. 강력하다.

functools의 reduce

https://docs.python.org/3/library/functools.html

functools.reduce(function, iterable[, initializer])

Apply function of two arguments cumulatively to the items of iterable, from left to right, so as to reduce the iterable to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). The left argument, x, is the accumulated value and the right argument, y, is the update value from the iterable. If the optional initializer is present, it is placed before the items of the iterable in the calculation, and serves as a default when the iterable is empty. If initializer is not given and iterable contains only one item, the first item is returned.

javascript 배열의 메서드 reduce와 닮아있는 듯 하다.

functools.reduce(함수, 반복 가능한 배열)을 하면 함수에 인자 두 개씩 넣어서 계산하고 반복 가능한 배열에서 하나 씩 빼와서 앞선 함수의 결과와 다시 함수에 넣어서 계산하고... 반복반복 => reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5) 이렇게

https://school.programmers.co.kr/learn/courses/30/lessons/12905

풀이과정

처음 풀이: 반복문으로 하나하나 보면서 값이 1인 블럭에서 오른쪽으로 한칸씩 가면서 최대 길이 구하고 아래도 한칸씩 가면서 최대 길이를 구한 뒤 그 둘의 최솟값을 구한다. 그 최솟값만큼이 정사각형인지 확인한다.

이런 방식으로 함수를 두 개 짜서 반복문에 넣었더니 1개의 테스트 케이스에서 실패가 나왔고 효율성 테스트에서 모두 시간초과가 떴다.

해법은 DP였다!!

코드

def solution(board):
    n_row = len(board)
    n_col = len(board[0])
    MAX = 1

    dp = [[0] * (n_col + 1) for _ in range(n_row + 1)]
    if sum([sum(line) for line in board]) == 0:
        return 0
    if n_row == n_col and sum([sum(line) for line in board]) == n_col**2:
        return n_col**2

    for r in range(1, n_row+1):
        for c in range(1, n_col+1):
            if board[r-1][c-1] == 1:
                dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
                MAX = max(dp[r][c], MAX)
    return MAX ** 2

꼭 알고 가자

0, 1로 이루어진 2차원 배열에서 최대 크기 직사각형을 알고 싶으면 해당 블럭의 값이 1일 때, min(왼쪽, 위쪽) + 1 한 값을 해당 블럭에 담는 방식을 DP를 하고 최대 크기 정사각형을 알고 싶으면 해당 블럭의 값이 1일 때, min(좌상대각선, 왼쪽, 위쪽) + 1 값을 해당 블럭에 담는 방식으로 DP 코드를 작성해야 한다.

https://school.programmers.co.kr/learn/courses/30/lessons/42890

풀이방법

유일성과 최소성을 만족하는 후보키를 선정하는 로직에 대해서 생각했다. 컬럼의 조합은 전체 컬럼을 (1 ~ 전체 컬럼의 개수) 만큼 고르는 경우의 수만큼 가능하다. 예시) 컬럼의 개수: N 컬럼의 조합의 개수: (N개에서 1개를 뽑는 경우) + (N개에서 2개를 뽑는 경우) + ... + (N개에서 N개를 뽑는 경우)

이때, 유일성을 만족하려면 set 자료형을 이용해서 겹치는 부분이 없는지 확인하면 되고 최소성을 만족하려면 이전에 유일성을 만족해서 후보키로 선정된 컬럼 조합이 포함된 경우에는 pass 하면 된다고 생각했다.

처음에는 전체 컬럼(1,2,3,4,...,N)에서 후보키로 선정된 컬럼의 번호를 빼는 방식으로 조합을 만들고 각 경우 유일성을 확인하는 방식으로 작성했다. 예시) 1개 뽑는 경우를 살펴본 결과, 컬럼 1이 후보키가 됨 => (2,3,4,...,N)에서 2개 뽑는 경우를 따져봄 2개 뽑는 경우를 살펴본 결과, 컬럼 (2,4)가 후보키가 됨 => (3,...,N)에서 3개 뽑는 경우를 따져봄 and so on...

그러나, 그렇게 짜니 몇 가지 케이스에서 오답이 나왔는데 그 이유는 전체 컬럼이 (0,1,2,3,4)이고, (1,2)컬럼이 후보키가 된 경우 1,2를 빼고 (0,3,4)에서 다시 조합을 구하게 되면 1,2 컬럼 중 하나만 포함되면서 유일성을 만족하여 후보키가 되는 경우(예를 들어 (2,3,4)가 유일성을 만족하는 경우)도 고려할 수 없게 되기 때문이다.

따라서, 이미 후보키라고 선정된 컬럼의 조합이 새롭게 살펴보는 컬럼의 조합의 부분집합인 경우에만 pass하는 방식으로 코드를 수정했더니 통과할 수 있었다.

부분집합인지 아닌지를 따질 때 set([1,2]) < set([1,2,3]) 이렇게 해서 True가 나오면 부분집합, False면 부분집합이 아닌 것으로 판별할 수 있다. (파이썬은 대단해!!!)

코드

from itertools import combinations as comb

def isExist(index_list, key):
    for k in key:
        if set(k) < set(index_list):
            return True
    return False

def get_multiple_element(my_list, index):
    return [my_list[i] for i in index]

def solution(relation):
    n_col = len(relation[0])
    org = list(range(n_col))

    key = []
    n = 1
    while n <= n_col:
        # print(org)
        for index_list in list(comb(org, n)):
            if isExist(index_list, key):
                continue
            else:
                # print(index_list)
                SET = set()
                for row in relation:
                    SET.add(''.join(get_multiple_element(row, index_list)))

                # print(SET)
                if len(SET) == len(relation):
                    key.append(index_list)

            # print("key:", key)
        n += 1

    return len(key)

다른 사람의 풀이

from itertools import combinations


def solution(relation):
    n_row = len(relation)
    n_col = len(relation[0])

    candidate = list()
    for i in range(1, n_col+1):
        candidate.extend(combinations(range(n_col), i))  #종목별로 만들 수 있는 모든 조합갯수 찾기

    final = []
    for keys in candidate:
        tmp = [tuple([item[key] for key in keys]) for item in relation] # 주어진 키로 리스트의 index별 아이템 뽑아내기
        if len(set(tmp)) == n_row: #set로 변경후 사라진게 없다면 key로 사용해도 무방
            final.append(keys)

    print(final)
    answer = set(final[:])
    print("answer", answer)
    for i in range(len(final)):
        for j in range(i+1, len(final)):
            if len(final[i]) == len(set(final[i]).intersection(set(final[j]))): # key 중에 겹치는 부분이 있는 것을 삭제
                answer.discard(final[j])
    return(len(answer))

가능한 조합 모두 구하고 유일성 확인하고 최소성 만족하지 않는거 삭제하기

나의 경우, 최소성 만족하지 않는 경우 유일성을 따지지 않고 넘겼기 때문에 시간 효율은 나의 풀이가 좋을 것이라 생각된다.

https://school.programmers.co.kr/learn/courses/30/lessons/160585

풀이과정

규칙을 어기는 경우에 대해서 생각해보았다. 다음과 같은 4가지 경우가 정해졌고 그것을 코드로 그대로 구현했다.

올바른 게임이 아닌 경우 (게임은 항상 O가 먼저 시작한다)

1. O의 개수 > X의 개수+1
2. O의 개수 < X의 개수
3. O가 한 줄이 되는 경우가 있는데(O가 승리하는 경우), O가 X보다 한 개 더 많지 않은 경우
4. X가 한 줄이 되는 경우가 있는데(X가 승리하는 경우), O와 X의 개수가 같지 않은 경우

Lv2의 다른 문제에 비해 쉬운 편이라고 생각이 된다.

코드

def solution(board):
    cnt_o, cnt_x = 0, 0
    # 숫자로 기록하는 보드 => O: 1, X: 10, . = 0
    n_board = [[0] * 3 for _ in range(3)]

    for i in range(3):
        for j in range(3):
            if board[i][j] == 'O':
                cnt_o += 1
                n_board[i][j] = 1
            elif board[i][j] == 'X':
                cnt_x += 1
                n_board[i][j] = 10

    if cnt_o < cnt_x or cnt_o > cnt_x+1:
        return 0

    for k in range(3):
        if (sum(n_board[k]) == 3 or sum(list(zip(*n_board))[k]) == 3) and cnt_o != cnt_x + 1:
                return 0
        if (sum(n_board[k]) == 30 or sum(list(zip(*n_board))[k]) == 30) and cnt_o != cnt_x:
                return 0


    if n_board[0][0] + n_board[1][1] + n_board[2][2] == 3 and cnt_o != cnt_x + 1:
        return 0

    if n_board[0][0] + n_board[1][1] + n_board[2][2] == 30 and cnt_o != cnt_x:
        return 0

    if n_board[0][2] + n_board[1][1] + n_board[2][0] == 3 and cnt_o != cnt_x + 1:
        return 0

    if n_board[0][2] + n_board[1][1] + n_board[2][0] == 30 and cnt_o != cnt_x:
        return 0

    return 1


board = ["O.X", ".O.", "..X"]
board = ["OOO", "...", "XXX"]
board = ["...", ".X.", "..."]
board = ["...", "...", "..."]
print(solution(board))

다른 사람의 풀이

# Check if there is a winning row, column, or diagonal
def check_win(player, board):
    # Check rows
    for i in range(3):
        if all(cell == player for cell in board[i]):
            return True

    # Check columns
    for j in range(3):
        if all(board[i][j] == player for i in range(3)):
            return True

    # Check diagonals
    if all(board[i][i] == player for i in range(3)):
        return True
    if all(board[i][2-i] == player for i in range(3)):
        return True

    return False

def solution(board):
    num_x = sum(row.count('X') for row in board)
    num_o = sum(row.count('O') for row in board)

    if num_x - num_o > 0 or abs(num_x - num_o) > 1:
        return 0

    elif (check_win('O', board) and num_x != num_o - 1) or (check_win('X', board) and num_x != num_o):
        return 0

    return 1

이기는 경우를 판별하는 함수를 따로 빼서 작성한 덕분에 코드가 깔끔해졌다. check_win 함수에서 all 내장함수를 쓴 점이 파이써닉하다!

https://school.programmers.co.kr/learn/courses/30/lessons/159993

풀이과정

문제를 이해하는데 시간이 걸렸다. 처음에 "이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다."를 보고 출구타일을 지나가기만 하면 탈출이 가능하다고 생각했는데, 다시 보니 문은 레버에서 열 수 있는 것이었다. 한번 지나간 칸을 또 갈 수 있다는 점 또한 알고리즘을 작성할 때 중요한 포인트였다. 최단시간이므로 다익스트라 알고리즘처럼 visited +1 보다 다음 타일에 있는 수가 크면 이동하도록 작성했다(아래의 코드 참고)

코드는 시작, 레버, 도착 지점의 좌표를 구한 후, 시작->레버 최단시간 + 레버->출구 최단시간을 구하는 방식으로 작성했다.

이렇게 풀이하니 시간초과가 2개의 테스트 케이스에서 떴다. BFS에서 시간초과 뜨면 뭐다? => deque로 바꿔본다. 통과! 파이썬은 알고리즘을 풀기 정말 편한 언어인 것 같다...ㅎ

코드

from collections import deque

def solution(maps):
    def BFS(point):
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        R, C = len(maps), len(maps[0])
        visited = [[False] * C for _ in range(R)]
        queue = deque([point])
        visited[point[0]][point[1]] = True

        while queue:
            x, y = queue.popleft()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if (0 <= nx < R) and (0 <= ny < C) and maps[nx][ny] != 'X':
                    if not visited[nx][ny] or visited[nx][ny] > visited[x][y] + 1:
                        queue.append([nx, ny])
                        visited[nx][ny] = visited[x][y] + 1

        return visited

    for i in range(len(maps)):
        if 'S' in maps[i]:
            start = [i, maps[i].find('S')]
        if 'E' in maps[i]:
            end = [i, maps[i].find('E')]
        if 'L' in maps[i]:
            lever = [i, maps[i].find('L')]

    start_lever = BFS(start)
    if start_lever[lever[0]][lever[1]] == False:
        return -1
    else:
        lever_end = BFS(lever)
        if lever_end[end[0]][end[1]] == False:
            return -1
        else:
            return start_lever[lever[0]][lever[1]] -1 + lever_end[end[0]][end[1]] - 1


maps = ["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]
maps = ["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]
maps = ["SOOOOL","XXXOXO","OOOOOO","OXXOXX","OOOOEO"]
print(solution(maps))

다른 사람의 풀이

특별히 다른 코드를 찾지 못해서 PASS~

https://school.programmers.co.kr/learn/courses/30/lessons/60057

풀이과정

2020 카카오 블라인드 채용 기출문제이다. 카카오는 문자열 문제가 많은 것 같다. 이번 문제는 알고리즘 분류를 하자면, 나는 '구현'으로 풀었다고 생각한다. 제한사항에서 문자열의 길이가 1이상 1000이하였기 때문에, 효율성 측면에서 깊이 생각하지 않았다.

그래서 1 ~ 문자열 길이//2 까지 완전 탐색하고 압축된 문자열 최솟값을 반환하는 방식으로 코드를 작성하였다.

이 문제에서 복병은 문자열의 길이가 1인 경우였는데, 런타임 에러로 한 테케만 실패가 떠서 금방 눈치챌 수 있었다. 하지만 만약에 테스트 케이스 어떤 것이 어떤 이유로 틀리는지 말해주지 않는 코테라면 나는 반례를 생각하지 못해서 틀렸을 확률이 높다. 항상 코드 제출 전에 반례를 생각해보자. 명심명심

코드

def solution(s):
    if len(s) == 1:
        return 1

    answer = float("inf")
    for n in range(1, len(s)//2+1):
        partial = s[0:n]
        tmp = ''
        cnt = 1
        idx = n
        while idx < len(s):
            if partial == s[idx:idx+n] :
                cnt += 1
                idx += n
            else:
                if cnt >= 2:
                    tmp = tmp + str(cnt) + partial
                else:
                    tmp += partial
                partial = s[idx:idx+n]
                idx += n
                cnt = 1
        if idx >= len(s):
            tmp = tmp + str(cnt) + partial if cnt >= 2 else tmp + partial
        answer = min(answer, len(tmp))
    return answer

s = "aabbaccc"
s = "ababcdcdababcdcd"
s = "abcabcdede"
s = "abcabcabcabcdededededede"
s = "xababcdcdababcdcd"
print(solution(s))

다른 사람의 풀이

def compress(s,length):
    target,s,cnt = s[:length], s[length:],1
    answer = ''
    while s:
        if target==s[:length]:
            s,cnt = s[length:], cnt+1
        else:
            answer+=str(cnt)+target if cnt>1 else target
            target,s,cnt = s[:length], s[length:], 1
    return len(answer+str(cnt)+target if cnt>1 else answer+target)
def solution(s):
    answer = len(s)
    for i in range(1,len(s)+1):
        answer = min(answer,compress(s,i))
    return answer

이번에는 특별히 눈에 띄는 놀라운 코드가 없었다. 이 코드는 압축하는 함수를 따로 빼서 깔끔하게 작성한 점이 마음에 든다.

https://school.programmers.co.kr/learn/courses/30/lessons/62048

풀이과정

이 문제는 아이디어 + 시간초과 해결이 포인트인 것 같다.

문제를 이해하는 데 시간이 조금 걸렸고, 풀이 아이디어가 생각나지 않았다. 규칙을 찾아보려 했지만 1시간이 넘도록 생각이 나지 않아 다른 사람이 적어둔 힌트를 보았다. 힌트는 기울기를 이용하는 것. y = 1.5x 인 상황이라면, x=1일 때 y=1.5가 된다. 이때, 대각선 아래에 위치하는 멀쩡한 사각형은 x=1, y=1 인거 1개이다. x=2일때는 y=3이다. 이때는 (2,1), (2,2), (2,3) 이렇게 멀쩡한 사각형이 3개가 된다. 이런 방식으로 x=1 ~ 7 까지 생각해보면 1 + 3 + 4 + 6+ 7 + 9 + 10 이 되어서 대각선 아래쪽에 총 40개의 멀쩡한 사각형이 존재할 수 있고 대각선 위로는 대칭이므로 총 80개가 존재하는 것을 구할 수 있다. 이 로직으로 코드를 파이썬으로 작성하면 시간초과가 나온다. w, h가 1억까지 커질 수 있기 때문이다.

따라서, 최대공약수로 나누어주고 반복되는 부분만큼 곱해주는 방식으로 작성하여 효율성을 증가시켰다. 이렇게 해도 11번 테스트케이스는 시간초과가 해결되지 않았다. 이 부분은 'w, h 중 더 작은 것을 기준으로 반복문을 돌린다.'가 포인트였다!

여러 힌트 덕분에 풀이할 수 있었던 문제라서 개인적으로 아쉬움이 남는다. 체화시켜서 다음에는 스스로 생각해내기...

코드

import math
def solution(w,h):
    gcd = math.gcd(w, h)
    sub_w = int(w / gcd)
    sub_h = int(h / gcd)

    answer = 0
    if sub_w <= sub_h:
        for i in range(1, sub_w):
            answer += int(sub_h * i / sub_w)
        answer *= 2
        answer += ((w - sub_w) * sub_h)
    else:
        for i in range(1, sub_h):
            answer += int(sub_w * i / sub_h)
        answer *= 2
        answer += ((h - sub_h) * sub_w)
    return answer * gcd

다른 사람의 풀이

def solution(w,h):

    from math import gcd

    k = gcd(w,h)

    w2 = w/k
    h2 = h/k

    return int(w*h-(w2+h2-1)*k)

대각선이 지나가는 사각형의 수는 w+h-gcd 라는 규칙이 있는 듯 하다. (신기)

https://school.programmers.co.kr/learn/courses/30/lessons/81302

풀이방법

구현 문제였다고 생각된다. 로직은 간단했으나 코드가 길어졌다.

코드

# 프로그래머스 거리두기 확인하기

def solution(places):
    outer = [[0, 2], [2, 0]]
    diag = [[1, 1], [1, -1]]
    inner = [[0, 1], [1, 0]]
    def distance_check(i, j, place):
        # 2칸 아래, 위, 좌, 우에 P 있는지 확인 -> 있으면 중심과 P 사이 X 있는지 확인
        for di, dj in outer:
            ni, nj = i + di, j + dj
            if (0 <= ni < 5) and (0 <= nj < 5) and place[ni][nj] == 'P':
                if place[i + (di//2)][j + (dj//2)] != 'X':
                    return 0
        # 대각선 1칸 거리에 P 있는지 확인 -> 있으면 중심과 P 사이 X 있는지 확인(2개)
        for di, dj in diag:
            ni, nj = i + di, j + dj
            if (0 <= ni < 5) and (0 <= nj < 5) and place[ni][nj] == 'P':
                if place[i][nj] != 'X' or place[ni][j] != 'X':
                    return 0
        # 상하좌우에 P 있는지 확인
        for di, dj in inner:
            ni, nj = i + di, j + dj
            if (0 <= ni < 5) and (0 <= nj < 5) and place[ni][nj] == 'P':
                return 0
        return 1

    answer = []
    for place in places:
        flag = 1
        for row in range(5):
            if flag == 0:
                break
            for col in range(5):
                if place[row][col] == 'P':
                    flag = distance_check(row, col, place)
                    if flag == 0:
                        break
        answer.append(flag)

    return answer

places = [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]
print(solution(places))

다른 사람의 풀이

def check(place):
    for irow, row in enumerate(place):
        for icol, cell in enumerate(row):
            if cell != 'P':
                continue
            if irow != 4 and place[irow + 1][icol] == 'P':
                return 0
            if icol != 4 and place[irow][icol + 1] == 'P':
                return 0
            if irow < 3 and place[irow + 2][icol] == 'P' and place[irow + 1][icol] != 'X':
                return 0
            if icol < 3 and place[irow][icol + 2] == 'P' and place[irow][icol + 1] != 'X':
                return 0
            if irow != 4 and icol != 4 and place[irow + 1][icol + 1] == 'P' and (place[irow + 1][icol] != 'X' or place[irow][icol + 1] != 'X'):
                return 0
            if irow != 4 and icol != 0 and place[irow + 1][icol - 1] == 'P' and (place[irow + 1][icol] != 'X' or place[irow][icol - 1] != 'X'):
                return 0
    return 1

def solution(places):
    return [check(place) for place in places]

보고 공부하기

https://school.programmers.co.kr/learn/courses/30/lessons/12936

풀이과정

문제는 정말 간단하다. 1부터 n 까지의 수를 나열하는 방법 중 사전 순으로 나열 했을 때, k번째 나열된 순서를 반환하는 함수를 작성하면 된다.

가장 간단한 풀이는 아래와 같이 itertools의 permutations 함수를 써서 정렬하고 k번째에 위치한 값을 반환하는 것이라 생각한다.

from itertools import permutations as perm

def solution(n, k):
    lst = sorted(list(perm(range(1,n+1), n)))
    return list(lst[k-1])

그러나 이 방법을 사용하면 시간 초과가 난다.

그래서 k번째를 바로 구할 수 있는 방법은 없을까 고민했다. 어렴풋이 생각은 나는데 그것을 정리하고 코드로 작성하는 과정이 쉽지는 않았다.

먼저, 제일 앞자리에 대해서 생각해본다. n이 3인 경우, 1XX, 2XX, 3XX 이렇게 될 수 있는데 각각 뒤에 2! 개의 경우의 수가 존재한다. n이 4인 경우에는 1XXX, 2XXX, 3XXX, 4XXX 이렇게 될 수 있고 각각 뒤에 3! 개의 경우의 수가 존재한다.

그렇다면 n=4, k=10인 경우에 대해서 생각해보자. 1XXX : 1 - 6번째 2XXX : 7 - 12번째 3XXX : 13 - 18번째 4XXX : 19 - 24번째 이므로 k번째 수는 2XXX이 될 것이다. 두번째 수는 21XX : 7 - 8번째 23XX : 9 - 10번째 24XX : 11 - 12번째 이므로 k번째 수는 23XX이 되고 23XX 의 두 가지 경우 중 사전 순으로 정렬했을 때 뒤에 있는 수가 될 것이다.

이 로직을 팩토리얼과 while 반복문, if 조건문을 사용하여 구현하였다.

코드

import math

def solution(n, k):
    answer = []
    org = list(range(1, n+1))
    idx = 1
    # i = 0
    while k > 0:
        # print(i, '번째:', n, k, idx, org, answer) # 디버깅용 코드
        if k - idx * math.factorial(n-1) > 0:
            idx += 1
        elif k - idx * math.factorial(n-1) < 0:
            k -= (idx-1) * math.factorial(n-1)
            tmp = org[idx-1]
            answer.append(tmp)
            org.remove(tmp)
            idx = 1
            n -= 1
        else:
            tmp = org[idx-1]
            answer.append(tmp)
            org.remove(tmp)
            answer.extend(sorted(org, reverse=True))
            break
    # i+=1
    return answer

다른 사람의 풀이

def solution(n, k):
    from math import factorial
    answer = []
    order = list(range(1,n+1))
    while n!=0 :
        fact = factorial(n-1)
        answer.append(order.pop((k-1)//fact))
        n,k = n-1, k%fact
    return answer

유사한 로직이지만 훨씬 깔끔하다. (k-1)//fact 부분과 k = k%fact으로 처리하는 부분이 인상 깊다.

https://school.programmers.co.kr/learn/courses/30/lessons/12978

풀이과정

문제를 보자마자 "이건 가중치 무방향 그래프다!" 생각이 들었다. 뒤에 알고리즘은 MST일까, 다익스트라일까 두근두근

코드를 작성할 때는 MST라고 생각하지 못하고 BFS인데, 최소 시간만 담도록 해야지. 생각했는데, 풀고보니 MST인 듯 하다.

주어진 road 리스트를 사용하여 가중치를 담은 인접 행렬을 만들었다. 이때, 두 마을 간 도로는 여러 개가 존재할 수 있다는 점이 함정이었다. 그래서 인접 행렬의 초기 값을 inf로 하고 최소값을 담도록 코딩하였다.

인접 행렬을 만든 다음에는 visitied 행렬을 만들었고 초기 값은 -1로 해주었다. false로 하니 시작점 방문처리가 어려웠기 때문이다. 그러나 다시 생각해보니, 시작 마을은 항상 1로 고정이기 때문에 1은 방문했다고 치면 되는 것이었다...

다음으로는 BFS 방식 코드를 작성하였다. 두 마을 간 도로가 있으면서, (현재까지의 시간 + 도로 이동 시간)이 가려는 도시에 해당하는 visited 칸에 담긴 값보다 작거나 같으면 queue에 넣는 방식으로 작성하였다.

그 후, 0부터 K까지의 수가 visited에 몇 개나 있는지 센 값을 answer로 구하였다.

코드

# 프로그래머스 배달

def solution(N, roads, K):
    adj_arr = [[float("inf")] * (N+1) for _ in range(N+1)]
    for road in roads:
        # 무방향 그래프
        adj_arr[road[0]][road[1]] = min(road[2], adj_arr[road[0]][road[1]])
        adj_arr[road[1]][road[0]] = min(road[2], adj_arr[road[1]][road[0]])

    visited = [-1] * (N+1)
    queue = [1]
    visited[1] = 0

    while queue:
        now = queue.pop(0)
        for next in range(2, N+1):
            if now != next and adj_arr[now][next] != float("inf"):
                if visited[next] != -1 and visited[next] < visited[now] + adj_arr[now][next]:
                    continue

                visited[next] = visited[now] + adj_arr[now][next]
                queue.append(next)

    # print(visited)
    answer = 0
    for i in range(K+1):
        answer += visited.count(i)
    return answer


N = 5
roads = [[1,2,1], [2,3,3], [5,2,2], [1,4,2], [5,3,1], [5,4,2]]
K = 3

N = 6
roads = [[1,2,1], [1,3,2], [2,3,2], [3,4,3], [3,5,2], [3,5,3], [5,6,1]]
K = 4

print(solution(N, roads, K))

다른 사람의 풀이

def solution(N, road, K):
    visited = [False] * (N + 1)
    costs = [float('inf')] * (N + 1)
    costs[1] = 0
    parents = [1]          
    while (parents):
        parent = parents.pop(0)
        visited[parent] = True
        for a, b, cost in road:
            if (a == parent or b == parent):
                target = b if a == parent else a
                if costs[target] > costs[parent] + cost:
                    costs[target] = costs[parent] + cost
                    parents.append(target)

    return sum(1 for c in costs if c <= K)

같은 알고리즘이지만, 훨씬 간략하고 메모리를 덜 사용했으며 가독성이 좋게 작성한 것 같다. 굿...

https://school.programmers.co.kr/learn/courses/30/lessons/152996

풀이과정

문제는 굉장히 간단하다. 시소는 중심으로부터 2, 3, 4m 떨어진 곳에 좌석이 있다(양쪽으로) 중심으로부터의 거리 * 사람의 무게 가 양쪽이 같으면 둘이 시소 짝궁이라고 할 수 있다. 주어진 몸무게를 가진 사람들 중 시소 짝꿍이 몇 쌍 존재하는지 구해야한다.

Weight_A * Distance_A = Weight_B * Distance_B 가 되는 경우의 수를 구하면 된다고 생각했다.

처음에 아주 단순하게, 4중 반복문을 생각했다.

answer = set()
for idx_a, w_a in enumerate(weights):
    for d_a in [2, 3, 4]:
        for idx_b, w_b in enumerate(weights[idx_a + 1:]):
            for d_b in [2, 3, 4]:
                if w_a * d_a == w_b * d_b:
                    answer.add([idx_a, idx_b + idx_a + 1])

 answer = len(answer)

위의 방식으로 풀이하니 예시 테스트 케이스는 맞았지만 시간이 아주 오래 걸렸다. weights의 길이가 최대 100000 였으니, 최악의 경우 10000000000 번의 연산이 필요하므로 시간 초과 + 실패가 떴다.

다음으로는 이것 저것 시도하다가 딕셔너리를 사용해보자는 아이디어가 떠올랐다.

풀이과정은 다음과 같다.

1. 원본 weights에 중복된 수가 있는지 찾아서 same_dict1에 weight와 갯수를 저장하고 중복이 없는 unique_weight 배열을 새로 만든다
2. 시소 중심으로부터의 거리(2, 3, 4)를 unique_weight 각 요소에 곱한 값을 이어붙인 multiply_weight 배열을 만든다
3. multiply_weight의 요소를 앞에서부터 하나씩 꺼내서 뒤에 같은 값이 있는지 확인 후, 같은 값이 있다면 same_dict2에 그 값을 key로 추가하고 value는 []로 둔다.
4. same_dict2의 key를 순회하면서 key를 2, 3, 4로 나눈 값이 unique_weight에 있는지 확인 후, 있다면 value에 추가한다 (weight * distance를 해서 같아지는 값이 존재한다는 의미이므로)
5. same_dict2의 value를 순회하면서, 5-1. value의 길이가 3보다 크거나 같으면 2개를 뽑는 경우가 1보다 크다는 의미이므로 모든 경우를 구하고, 각 경우 사용되는 weight에 대해서 원본 weights에 존재하는 횟수를 구해서 곱해준다 (ex: value에서 100, 200이 한 쌍으로 존재하는데 원본 배열에서 100이 3번, 200이 2번 있다면 100, 200 쌍은 3 * 2번 나올 수 있음) 5-2. value의 길이가 2라면, 각 요소가 원본 weights에 존재하는 횟수를 구해서 곱해준다 => 곱한 값들은 cnt(=answer)에 더해줌
6. 마지막으로 원본 weights에 동일한 값이 있었던 weight에 대해서 중복 갯수 중 2개를 고르는 경우의 수(조합의 수)를 cnt에 더해준다

이렇게 저렇게 해서... 풀긴 풀었는데 코드가 아주 길다는 점이 아쉽다. 의미 있었던 예시 테스트 케이스는 weights = [100, 100, 100, 150, 150, 200, 300] 였다. 이 경우, 결과가 18이 나와야 하는데 오류가 나는 코드에서는 19가 나왔다. (테스트케이스 3-11 실패) 그 부분을 고쳤더니 통과 되었다!

코드

import math
from itertools import combinations

def solution(weights):
    # 같은 수 있는지 확인하고 하나만 남기고 제거 O(N)
    unique_weight = [weights[0]]

    same_dict1 = {} # weights에 같은 수가 있으면, 어떤 수가 몇 번 나오는지 기록하는 딕셔너리
    for w in weights[1:]:
        if w in unique_weight:
            same_dict1[w] = same_dict1.get(w, 1) + 1
        else:
            unique_weight.append(w)

    # print(same_dict1)

    # 2, 3, 4를 곱한 값을 이어 붙이기
    multiply_weight = [i * 2 for i in unique_weight] + [i * 3 for i in unique_weight] + [i * 4 for i in unique_weight]

    # print(multiply_weight)

    # 앞에서부터 하나씩 꺼내서 뒤에 같은 값 있는지 확인
    i = 0
    same_dict2 = {}
    while i < len(multiply_weight) - 1:
        w = multiply_weight[i]
        if w in multiply_weight[i+1:]: # 같은 값이 뒤에 존재하면, same_dict2에 key를 추가하고 value는 빈 리스트로 설정
            same_dict2[w] = []
        i += 1

    for key in same_dict2.keys(): # 같은 값이 존재하는 수에 대해서, 2, 3, 4로 나눈 뒤 unique_weight에 있는 값인지 확인하고, 있으면 same_dict2[key]에 추가한다
        if key / 2 in unique_weight:
            same_dict2[key].append(int(key/2))
        if key / 3 in unique_weight:
            same_dict2[key].append(int(key/3))
        if key / 4 in unique_weight:
            same_dict2[key].append(int(key/4))

    cnt = 0
    for value in same_dict2.values():
        if len(value) >= 3:
            # value가 3개 이상이면 2개를 뽑는 경우의 수가 1보다 커진다
            # -> combinations를 이용해서 2개 뽑는 경우를 모두 구하고,
            # 원본 배열에서 중복이 있었는지 확인하고, 있다면 중복 갯수를 곱해주는 방식으로 계산
            combs = list(combinations(value, 2))
            tmp = 0
            for comb in combs:
                tmp += same_dict1.get(comb[0], 1) * same_dict1.get(comb[1], 1) # 중복이 없었다면 1이 곱해지는 것

        else:
            tmp = same_dict1.get(value[0], 1) * same_dict1.get(value[1], 1) # 여기도 마찬가지로 원본 배열에 중복이 있다면 중복 숫자의 갯수, 없다면 1이 곱해짐

        # print(value, tmp)
        cnt += tmp

    for value in same_dict1.values(): # 처음 weights에서 동일한 값이 있던 수에 대해서 해당 수 중 2개를 고르는 경우의 수를 cnt에 더해준다
        cnt += math.comb(value, 2)

    # print(same_dict2)
    return cnt


weights = [100, 100, 180, 360, 270]
weights = [100, 100, 100, 150, 150, 200, 300]
# weights = [100, 100, 180, 180, 360, 100, 270]
print(solution(weights))

다른 사람의 풀이

from itertools import combinations
from collections import Counter

def solution(weights):
    cnt = 0
    weights = Counter(weights)
    for a, b in combinations(weights.keys(), 2): # 서로 다른 무게
        if a*2 == b*3 or a*2 == b*4 or a*3 == b*4 or b*2 == a*3 or b*2 == a*4 or b*3 == a*4:
            cnt += weights[a] * weights[b]
    for v in weights.values(): # 같은 무게
        if v > 1:
            cnt += sum([i for i in range(1, v)])
    return cnt

counter와 combinations를 사용한 깔끔한 풀이. 배워야지...

https://school.programmers.co.kr/learn/courses/30/lessons/67257

풀이과정

수식 문제라서 보자마자 후위표기식으로 변환해야겠다는 생각을 했다. 그러나, 변환방법을 까먹은 것이다... 원리를 생각하며 코드를 생각해내보려했지만, 실패해서 결국 검색해서 공부를 했다.

후위표기식 변환방법은 아래의 블로그를 참고했다. https://woongsios.tistory.com/288

중위표기식으로 쓰인 수식을 후위표기식으로 변환하는 과정(괄호가 없는 경우) 0. 연산자를 담는 stack을 만든다

1. 숫자를 만나면 push
2. 연산자를 만나면, 2-1. 연산자 stack이 비었다면, stack에 연산자 push 2-2. 연산자 stack에 연산자가 있다면, 현재 연산자와 stack의 마지막에 위치한 연산자의 우선순위를 비교하고, 현재 연산자의 순위가 낮을 때까지 연산자를 stack에서 pop해서 후위표기식에 push 한다(=> 현재 연산자의 순위가 stack[-1]보다 높거나 같으면 stack.pop(), 낮으면 그때 현재 연산자를 stack에 push)
3. 주어진 중위표기식을 모두 살펴보았으면, stack에 남은 연산자를 끝에서부터(stack개념으로 LIFO) 빼서 후위표기식에 추가한다

해당 문제는, 문자열로 주어진 expression에서 숫자와 연산자를 잘 분리할 수 있는지 + 중위표기식을 후위표기식으로 변환하여 계산할 수 있는지 가 중요했다고 생각된다.

수식의 우선순위로 가능한 모든 경우를 미리 리스트화한 후, 이를 순회하면서 후위표기식으로 바꾸고 계산한 결과에 절댓값을 씌워 answer에 추가한 다음 answer의 최댓값을 구했다.

코드

from collections import deque

# 수식의 우선순위가 가능한 모든 경우를 미리 리스트화한 후 순회하면서, 중위표기식을 후위표기식으로 바꾸어 계산한 결과의 절댓값의 최댓값을 구함
def solution(expression):
    op_orders = [['-','*','+'], ['-','+','*'], ['*','-','+'], ['*','+','-'], ['+','*','-'], ['+','-','*']]
    answer = []

    for order in op_orders:
        start = 0
        postfix = deque()
        operators = deque() # stack

        for i in range(len(expression)):
            if not expression[i].isdigit():
                postfix.append(int(expression[start:i]))
                start = i+1
                while operators:
                    op1 = operators[-1]
                    op2 = expression[i]
                    if order.index(op1) <= order.index(op2):
                        postfix.append(operators.pop())
                    else:
                        operators.append(op2)
                        break
                else:
                    operators.append(expression[i])

        postfix.append(int(expression[start:]))
        while operators:
            postfix.append(operators.pop())

        stack = []
        idx = 0
        while idx < len(postfix):
            if type(postfix[idx]) != int:
                a = stack.pop()
                b = stack.pop()
                if postfix[idx] == '+':
                    stack.append(a+b)
                elif postfix[idx] == '-':
                    stack.append(b-a)
                elif postfix[idx] == '*':
                    stack.append(a*b)

            else:
                stack.append(postfix[idx])
            idx += 1

        # print(order)
        # print(postfix)
        # print(stack)
        answer.append(abs(stack[-1]))

    return max(answer)



ep = "100-200*300-500+20"
ep = "50*6-3*2"

print(solution(ep))

• 처음에 deque를 안쓰고 list로만 구현했을 때, 테스트케이스 별 실행 시간
• deque를 적용한 후, 테스트케이스 별 실행 시간

이 정도 범위에서는 큰 차이가 없는 듯 하다.

다른 사람의 풀이

eval이라는 내장 함수를 사용한 풀이

def solution(expression):
    operations = [('+', '-', '*'),('+', '*', '-'),('-', '+', '*'),('-', '*', '+'),('*', '+', '-'),('*', '-', '+')]
    answer = []
    for op in operations:
        a = op[0]
        b = op[1]
        temp_list = []
        for e in expression.split(a):
            temp = [f"({i})" for i in e.split(b)]
            temp_list.append(f'({b.join(temp)})')
        answer.append(abs(eval(a.join(temp_list))))
    return max(answer)

https://school.programmers.co.kr/learn/courses/30/lessons/148653

엘리베이터가 10의 c 제곱에 해당하는 만큼의 층을 움직이는 버튼 밖에 없다. (c>=0) 최소한의 버튼 사용으로 현재 층(storey)에서 0층까지 움직이도록 하고 이때 필요한 버튼 클릭 횟수 구해라

풀이과정

<생각의 흐름> DFS로 -1, 1, -10, 10, -100, 100... 숫자들을 넣고 주어진 층에 해당하는 수가 나올 때까지 구하는 방식으로 짜볼까? 아냐아냐 자릿수만 생각해도 되는거 아닌가? 오?! 자릿수?! 그리고 재귀?!

라고 생각하며 코드가 생각보다 금방 작성되었다.

1번, 3번, 12번 테스트 케이스에서 오류가 났다. 도저히 반례가 생각나지 않았다... 질문하기를 보았다(이거 그만 봐야하는데ㅜㅜ 실제 코테에서는 못 보잖아... 그만둬..!)

유레카.. 반례는 95였다!!!!!

95가 잘 계산되도록, 7이 아니라 6이 나오도록! 코드를 수정했더니 통과되었다.

코드

처음 코드(1, 3, 12번 실패)

def solution(storey):
    if storey < 10:
        if storey <= 5:
            return storey
        else:
            return 10 - storey + 1

    if storey % 10 <= 5:
        return storey % 10 + solution(storey//10)
    else:
        return 10 - (storey % 10) + solution(storey//10)

수정한 코드(통과)

def solution(storey):
    if storey < 10:
        if storey <= 5:
            return storey
        else:
            return 10 - storey + 1

    if storey % 10 <= 5:
        cnt = storey % 10
        storey = round(storey/10) # 여기서 반올림 해주는게 포인트
        return cnt + solution(storey)
    else:
        cnt = 10 - storey % 10
        storey = round(storey/10)
        return cnt + solution(storey)

가장 뒤의 숫자는 따로 cnt로 계산해두고(5보다 클 때, 작을 때 조건 나눠서), 반올림을 하는 것이 포인트이다.

다른 사람의 풀이

def solution(storey):
    if storey < 10 :
        return min(storey, 11 - storey)
    left = storey % 10
    return min(left + solution(storey // 10), 10 - left + solution(storey // 10 + 1))

짧고 강력하다...! min 내장함수와 재귀를 사용해서 깔끔하게 풀이했다. 오늘도 감탄하며 마무리...

https://school.programmers.co.kr/learn/courses/30/lessons/155651

풀이 과정

문제는 매우 간단하다. 주어진 대실 예약 리스트를 만족시키는 최소한의 방의 개수를 구하는 것

숙박이 아니라 대실이라서 시간이 한정적이다. 따라서, 각 분을 인덱스로 가지는 리스트를 만들어서 풀 수도 있을 것이다.

나는 rooms라는 리스트를 만들어서 시간을 요소로 추가하고 들어오는 대실 시간을 비교해서 넣고 빼고 하는 방식으로 코드를 작성했다.

코드

def solution(book_time):
    for i, time in enumerate(book_time):
        book_time[i] = [int(time[0][0:2]) * 60 + int(time[0][3:]), int(time[1][0:2]) * 60 + int(time[1][3:]) + 10] 
        # 시간을 분으로 바꾸는 코드인데, 이 부분을 따로 함수로 만든 사람이 많았다.
    book_time.sort(key=lambda x: (x[0], x[1]))
    # print(book_time)

    rooms = [book_time[0]]
    for time in book_time[1:]:
        start = time[0]
        for n_room, room in enumerate(rooms):
            if room[1] <= start: # 방에 이미 있는 손님의 퇴실 시간 + 10분 <= 들어올 손님의 입실 시간 이면, 그 방에 손님 넣고 break
                rooms[n_room] = time
                break

        else:
            rooms.append(time)

    answer = len(rooms)
    return answer

다른 사람의 풀이

Counter 내장함수 사용

from collections import Counter
def solution(book_time):
    def get_time(t):
        HH, MM = map(int, t.split(":"))
        return HH*60 + MM
    m = 0
    n = 0

    in_time = Counter([get_time(b[0]) for b in book_time])
    out_time = Counter([get_time(b[1])+10 for b in book_time])
    total_time = set(list(in_time.keys())+list(out_time.keys()))
    total_time = list(total_time)
    total_time.sort()
    for t in total_time:
        n -= out_time[t]
        n += in_time[t]
        m = max(m, n)
    return m

Counter를 이용해서 book_time에 있는 시간과 횟수를 세고 total_time을 정렬한 다음, 입실이면 +횟수, 퇴실이면 -횟수하는 방식과 각 반복문에서의 n의 최댓값을 구하는 방식

각 분을 인덱스로 가지는 리스트 사용

def solution(book_time):
    time_table = [0 for _ in range(60 * 24)] # 0시 00분 ~ 23시 59분의 각 분을 인덱스로 가지는 리스트 생성
    for start, end in book_time:
        start_minutes = 60 * int(start[:2]) + int(start[3:])
        end_minutes = 60 * int(end[:2]) + int(end[3:]) + 10

        if end_minutes > 60 * 24 - 1: # 인덱스가 time_table을 넘지 않도록 방어코드 작성
            end_minutes = 60 * 24 - 1

        for i in range(start_minutes, end_minutes):
            time_table[i] += 1

    return max(time_table) # 시간이 겹친다 -> 방이 겹치는 시간 횟수만큼 필요하다
    # 추가 아이디어: 위의 반복문 대신에 시작 시간은 +1, 끝 시간은 -1만 하고 마지막에 max(누적합)을 구해도 됨

0시 00분 ~ 23시 59분의 각 분을 인덱스로 가지는 리스트를 생성해서 book_time에서 입실~퇴실 사이의 분에 대해 모두 +1하는 식으로 book_time을 순회한 후, max값을 구하는 방식

시간은 더 오래 걸릴 것 같지만, 현재 나의 수준에서는 아래 방식이 더 직관적으로 와닿고 다음에 써먹을 수 있을 것 같다.