꾸준히 개발하기

https://programmers.co.kr/learn/courses/30/lessons/42576

try1. in 연산자

썼다가 효율성 0점 맞음 (당연함... 시간복잡도 O(n)... )

try2. binary_search

찾아가면서 진행했더니 효율성 테케 2개 fail

try3. 계수 정렬에서 착안해서 collections.Counter 사용해서 값 찾음

처음에는 set 연산 써서 참가자와 완주자의 차집합을 구해서 그 차집합의 길이가 0이 아니면 동명이인이 있다고 생각해서 동명이인 숫자를 most_common() 써서 출력했음. 

근데 생각해보면 동명이인이 여러명 있고, 그 여러명이 다 통과할지 안할지 모르는 부분임..

try4. Counter 사용해서 등장횟수 체크하고, 완주하지 못한 선수는 딱 1명이니까 Counter 객체의 key, value값 비교해서 다른 요소를 찾아냄

만약 키값이 존재하고 value가 다를때와, 키값이 아예 존재하지 않을때 두가지 경우만 존재해서 풀음.

-> 다른 사람 코드 보니까 Counter객체는 빼기 연산이 가능해서 ... 단순히 빼주고 그 요소의 key값만 출력해줘도 됬었다. 그래도 목표 시간 1시간 안에는 품!

from collections import Counter

def solution(participant, completion):
    answer = ""

    c_p = Counter(participant)
    c_c = Counter(completion)

    for key_cp, value_cp in c_p.items():
        # 만약 key가 존재하고 value값이 다르면 answer에 추가
        if key_cp in c_c and value_cp != c_c.get(key_cp):
            answer += key_cp
            break
        # key가 없으면 answer에 추가
        elif not key_cp in c_c:
            answer += key_cp
            break

    return answer

과거의 내가 진짜 진짜 진짜 코테를 못한다고 생각했는데 한동안 코테를 놓고 다시 풀기 시작한 지금이 더 퇴화했다....

와 코테는 진짜.. 꾸준함이구나.... 진짜.... 1일 1커밋하면서 그날 푼 문제들 같이 티스토리에 적으면서 기록해야겠다...

충격적인 나의 퇴화

2020년의 내가 더 잘 풀었어 눈물 줄줄 

프로그래머스 고득점 kit 정렬 파트에 있는 문제다.

https://programmers.co.kr/learn/courses/30/lessons/42746

내부에서 제공하는 sort() 함수를 써야 시간 복잡도 상 유리한 걸 머리로는 알면서도 어떻게 써야될지 감이 안와서 무식하게 비교했더니 시간 초과가 났다. 당연한 결과지만서도... 

def solution(numbers):
    answer = ''
    
    while len(numbers) > 0:
        max_num = -1
        for i in range(len(numbers)):
            if str(max_num)*3 < str(numbers[i])*3:
                max_num = numbers[i]
        
        numbers.remove(max_num)
        answer += str(max_num)
    
    return str(int(answer))

마지막에 str(int(answer)) 해준 이유는 숫자 배열이 [0,0,0,0] 이라고 주어질 때 '0000'이 아니라 '0'으로 나와야해서 정수형으로 바꿔주고 다시 문자열로 바꿔준 것이다. 테케 11번이 이건듯?

문자열에 *3을 해주는건 "3" 이랑 "30" 이랑 비교했을 때 후자가 더 커서 그 부분을 해결해주기 위해 작성했다.

그나저나 이 코드로는 시간 초과가 잡힐 수가 없어서 파이썬 기본 제공 라이브러리 sort함수 + 람다 함수써서 어떻게 하나 검색해봤더니 기가 막히는 코드가 있더라... 어떻게 이렇게 깔끔하게 쓰는지 ㅠㅠ

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x * 3, reverse=True)
    return str(int("".join(numbers)))

위 코드로 하면 깔끔하게 통과한다. join 함수랑 sort 함수에 람다로 넘겨주는 방법에 더 익숙해지자

1. 컴퓨팅 사고

알고리즘은 입력(input)에서 받은 자료를 출력(output)형태로 만드는 처리 과정

즉, 알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열

알고리즘을 평가할 때는 정확성도 중요하지만, 효율성도 중요

3. 배열

1) 컴파일링

make나 clang을 사용해서 프로그램을 실행할 때 아래 네 개의 단계를 거칩니다.

• 전처리
• 컴파일링
• 어셈블링
• 링킹

우리가 명령어를 실행할 때 정확히 어떤 일이 일어나는지 알아보도록 하겠습니다.

전처리(Precompile)

컴파일의 전체 과정은 네 단계로 나누어볼 수 있습니다. 그 중 첫 번째 단계는 전처리인데, 전처리기에 의해 수행됩니다. # 으로 시작되는 C 소스 코드는 전처리기에게 실질적인 컴파일이 이루어지기 전에 무언가를 실행하라고 알려줍니다.

예를 들어, #include는 전처리기에게 다른 파일의 내용을 포함시키라고 알려줍니다. 프로그램의 소스 코드에 #include 와 같은 줄을 포함하면, 전처리기는 새로운 파일을 생성하는데 이 파일은 여전히 C 소스 코드 형태이며 stdio.h 파일의 내용이 #include 부분에 포함됩니다.

컴파일(Compile)

전처리기가 전처리한 소스 코드를 생성하고 나면 그 다음 단계는 컴파일입니다. 컴파일러라고 불리는 프로그램은 C 코드를 어셈블리어라는 저수준 프로그래밍 언어로 컴파일합니다.

어셈블리는 C보다 연산의 종류가 훨씬 적지만, 여러 연산들이 함께 사용되면 C에서 할 수 있는 모든 것들을 수행할 수 있습니다. C 코드를 어셈블리 코드로 변환시켜줌으로써 컴파일러는 컴퓨터가 이해할 수 있는 언어와 최대한 가까운 프로그램으로 만들어 줍니다. 컴파일이라는 용어는 소스 코드에서 오브젝트 코드로 변환하는 전체 과정을 통틀어 일컫기도 하지만, 구체적으로 전처리한 소스 코드를 어셈블리 코드로 변환시키는 단계를 말하기도 합니다.

어셈블(Assemble)

소스 코드가 어셈블리 코드로 변환되면, 다음 단계인 어셈블 단계로 어셈블리 코드를 오브젝트 코드로 변환시키는 것입니다. 컴퓨터의 중앙처리장치가 프로그램을 어떻게 수행해야 하는지 알 수 있는 명령어 형태인 연속된 0과 1들로 바꿔주는 작업이죠. 이 변환작업은 어셈블러라는 프로그램이 수행합니다. 소스 코드에서 오브젝트 코드로 컴파일 되어야 할 파일이 딱 한 개라면, 컴파일 작업은 여기서 끝이 납니다. 그러나 그렇지 않은 경우에는 링크라 불리는 단계가 추가됩니다.

링크(Link)

만약 프로그램이 (math.h나 cs50.h와 같은 라이브러리를 포함해) 여러 개의 파일로 이루어져 있어 하나의 오브젝트 파일로 합쳐져야 한다면 링크라는 컴파일의 마지막 단계가 필요합니다. 링커는 여러 개의 다른 오브젝트 코드 파일을 실행 가능한 하나의 오브젝트 코드 파일로 합쳐줍니다. 예를 들어, 컴파일을 하는 동안에 CS50 라이브러리를 링크하면 오브젝트 코드는 GetInt()나 GetString() 같은 함수를 어떻게 실행할 지 알 수 있게 됩니다.

이 네 단계를 거치면 최종적으로 실행 가능한 파일이 완성됩니다.

2) 디버깅

버그와 디버깅

버그(bug)는 코드에 들어있는 오류입니다. 버그로 인해 프로그램의 실행에 실패하거나 프로그래머가 원하는 대로 동작하지 않게 됩니다. 버그를 만들고 싶지 않겠지만 모든 프로그래머들은 버그와 마주하게 되어있습니다. 디버깅(debugging)은 코드에 있는 버그를 식별하고 고치는 과정입니다. 프로그래머는 디버거라고 불리는 프로그램을 사용하여 디버깅을 하게 됩니다.

디버깅의 기본

디버거는 프로그램을 특정 행에서 멈출 수 있게 해주기 때문에 버그를 찾는데 도움이 됩니다. 프로그래머는 멈춰진 그 지점에서 무슨 일이 일어나는지 볼 수 있습니다. 프로그램이 멈추는 특정 지점을 중지점이라고 합니다. 또한 프로그래머가 프로그램을 한번에 한 행씩 실행할 수 있게 해줍니다. 이로써 프로그래머는 프로그램이 내리는 모든 결정들을 단계별로 따라갈 수 있게 됩니다.

help50

아래와 같이 make 앞에 help50 을 붙여서 실행하면 다시 컴파일시 생기는 오류를 해석해줍니다.

help50 make 파일이름

debug50

CS50 IDE를 사용하면 debug50이라는 프로그램도 사용할 수 있습니다.

아래와 같이 소스 코드에 직접 브레이크포인트를 지정하고 소스파일을 컴파일한 후에 “debug50 파일명” 으로 실행하면, 오른쪽 패널을 통해 변수의 값을 확인하거나 브레이크포인트부터 한 줄씩 코드를 실행해 볼 수 있습니다.

디버깅 종료를 위해서는 Ctrl + c를 누르면 됩니다.

7) 문자열의 활용

strlen은 문자열의 길이를 알려주는 함수로, string.h 라이브러리 안에 포함되어 있습니다.

ctype 라이브러리에 toupper() 이라는 함수는 사용자로부터 문자열을 입력받아 대문자로 바꿔주는 함수입니다.

문자열 관련된 라이브러리는 string.h고 문자 관련된 라이브러리는 ctype.h이니, 두 라이브러리 내 구현된 함수를 활용하도록 합시다.

8) 명령행 인자

make나 clang과 같은 프로그램을 실행할 때 컴파일하고자 하는 코드 외에도 컴파일 후 저장하고자 하는 파일명과 같이 추가적인 정보를 함께 줄 수도 있습니다. 이런 정보들을 명령행 인자 라고 부릅니다.

main() 안에 기계적으로 void 라고 입력하는 대신 아래 코드와 같이 argc, argv 를 정의해보겠습니다.

#include <cs50.h>
#include <stdio.h>

int main(int argc, string argv[])
{
    if (argc == 2)
    {
        printf("hello, %s\n", argv[1]);
    }
    else
    {
        printf("hello, world\n");
    }
}

여기서 첫번째 변수 argc는 main 함수가 받게 될 입력의 개수입니다.

그리고 argv[]는 그 입력이 포함되어 있는 배열입니다. 프로그램을 명령행에서 실행하므로, 입력은 문자열로 주어집니다.

따라서 argv[]는 string 배열이 됩니다.

argv[0]는 기본적으로 프로그램의 이름으로 저장됩니다.

만약 하나의 입력이 더 주어진다면 argv[1]에 저장될 것입니다.

예를 들어 위 프로그램을 “arg.c”라는 이름으로 저장하고 컴파일 한 후 “./argc”로 실행해보면 “hello, world”라는 값이 출력됩니다.

명령행 인자에 주어진 값이 프로그램 이름 하나밖에 없기 때문입니다.

하지만 “./argc David”로 실행해보면 “hello, David”라는 값이 출력됩니다.

명령행 인자에 David라는 값이 추가로 입력되었고, 따라서 argc 는 2, argv[1] 은 “David”가 되기 때문입니다.

4. 알고리즘

알고리즘의 성능, 시간 복잡도를 표현할 때, 최악의 경우(상한)을 나타내는 것 : Big-O 표기법, O()

주로 아래 목록과 같은 Big O 표기가 실행 시간을 나타내기 위해 많이 사용됩니다.

• O(n^2)
• O(n log n)
• O(n) - 선형 검색
• O(log n) - 이진 검색
• O(1)
•  

Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것입니다.

예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 됩니다.

역시 아래 목록과 같은 Big Ω 표기가 많이 사용됩니다.

• Ω(n^2)
• Ω(n log n)
• Ω(n) - 배열 안에 존재하는 값의 개수 세기
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬
• O(n log n) : 병합 정렬
• O(n): 선형 검색
• O(log n): 이진 검색
• O(1)

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬(n-1번 반복할 경우)
• Ω(n log n) : 병합 정렬
• Ω(n) : 버블 정렬(교환이 일어나지 않을 때까지 반복할 경우)
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

* 병합 정렬 추가 설명

병합 정렬 실행 시간의 상한은 O(n log n) 입니다.

숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문입니다.

실행 시간의 하한도 역시 Ω(n log n) 입니다. 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문입니다.

선택 정렬, 버블 정렬, 선형 검색, 이진 검색 4가지 알고리즘이 최선인 경우일 때의 실행시간이(하한) 빠른 순서대로 나열한 것은 무엇인가요? 

: 이진 검색 - 선형 검색 - 버블 정렬 - 선택 정렬

병합 정렬, 선택 정렬, 버블 정렬의 실행시간의 하한을 빠른 순서대로 정렬한 것은 무엇인가요?

: 버블 정렬 - 병합 정렬 - 선택 정렬

알고리즘의 실행 시간의 상한을 비교하기 위해 Big-O 표기법을 사용합니다. 다음 Big-O 표기법 중 빠른 순서대로 올바르게 정렬한 것은 무엇인가요?

: O(1) – O(log n) – O(n) – O(n^2)

Lv2가 맞나 싶은 난이도... 문제에 대한 감이 어느정도 있어야 이게 그리디로 푸는게 맞는지 아닌지 아는 것 같다.

문제

https://programmers.co.kr/learn/courses/30/lessons/42860

접근 방법

크게 상하 / 좌우로 움직일 때로 나뉜다. 

상하 이동 : 알파벳 바꿀 때 (어차피 A인 경우에는 0이므로 그냥 계산해주면 됨)
1) N(78) 이전 문자로 변경 시 위로 이동 -> 이동횟수 = 해당문자아스키값 - 65(A)
2) 이외에는 아래로 이동 -> 이동횟수 = 90(Z) - 해당문자아스키값 + 1 (+1은 A->Z 변경)
-> 더 작은 값으로 설정하기

* 여기에서 ord() 메서드를 사용해주면 해당 문자의 아스키값을 리턴해준다

좌우 이동 ** 풀이 참고 **
- 기본 최소 이동 횟수 : 길이 -1
- 연속되는 A가 있을 때, 그것의 왼쪽이나 오른쪽부터 시작하며 알파벳을 변경하는 것이 가장 효율적
(기존, 연속A의 왼쪽에서 시작, 연속A의 오른쪽에서 시작) 중 min값이 답
- 연속되는 A가 있는 곳에는 굳이 갈 필요 없음, 그 부분을 제외하고 수정하는 경우 계산
- 다만 연속되는 A가 여러 개인 경우, 가장 긴 부분을 안 가는 것이 효율적임

여기가 도저히 이해가 안되서 블로그를 많이 뒤져봤다 보니까 원래는 왼쪽만 계산해줘도 됬는데, 2022년 기준 테스트케이스가 추가되어 오른쪽을 계산하는(뒤에서 시작하는) 부분이 추가되어야 한다고 한다. 이해를 돕기 위해 이미지를 하나 첨부한다.

코드

# 2022-04-06
# 프로그래머스 고득점 kit 그리디 - 조이스틱 
# https://programmers.co.kr/learn/courses/30/lessons/42860

def solution(name):
    answer = 0

    min_move = len(name) - 1
    
    for i, char in enumerate(name):
        # 알파벳 변경 최솟값 추가
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)

        # 해당 알파벳 다음부터 연속된 A 문자열 찾기
        next = i+1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        # 기존, 연속된 A의 왼쪽 시작방식, 연속된 A의 오른쪽시작방식 비교 및 갱신
        min_move = min([min_move, 2*i+len(name)-next, i+2*(len(name) - next)])

    # 상하이동 횟수 + 좌우이동 횟수     
    answer += min_move
    return answer

인터럽트에 대해서 설명하세요

하드웨어가 시스템의 수행 흐름을 바꾸기 위해 발생하는 것. 트랩(예외, exception)의 경우 소프트웨어가 발생하는 인터럽트이다. 인터럽트가 발생되면 CPU는 현재 수행중인 작업을 멈추고 운영체제 내에 있는 특정 코드를 실행한다. 이 실행이 끝나면 다시 멈춘 작업을 재개한다. 

인터럽트는 1) 현재 작업을 멈추고, 현재 상태를 보관 2) 인터럽트의 종류 분석 3) 특정 인터럽트 수행 4) 보관된 상태를 원상복귀하고 멈춘 작업을 재개하는 과정을 통해 실행된다. 

DMA 존재 이유에 대해서 설명하세요.

I/O (입출력)에는 두 가지 형태가 있다.

- 동기식 입출력 (synchronous I/O) : 입출력이 시작되면 요청한 프로세서는 입출력이 완료될 때까지 기다린다.

- 비동기식 입출력 (asynchronous I/O) : 요청한 프로세서는 입출력이 완료될 때까지 기다리지 않고 계속 다른 작업을 수행한다.

속도가 느린 입출력 장치는 하나의 입력을 받은 후 다음 입력까지 CPU는 다른 유용한 작업을 할 수 있다. 그러나 반대로 입출력 장치의 속도가 빠르면 인터럽트가 너무 빈번하게 발생하여 CPU가 다른 유용한 작업을 할 시간이 적다. 이것을 해결하기 위해 사용하는 기법이 DMA(Direct Message Access)이다. DMA 방식에서 장치 제어기(디스크, 오디오 장치를 관리)는 데이터 블록을 CPU의 관여 없이 직접 주기억장치로 이동하며, 인터럽트는 바이트 단위가 아닌 블록 단위로 발생한다.

즉, DMA란 CPU의 개입 없이 입출력장치와 주기억장치의 데이터 전송이 이루어지는 방법으로, 입출력을 위한 인터럽트 발생 횟수를 최소화하여 컴퓨터 시스템의 효율을 높이기 위해 필요하다.

함수호출과 시스템 콜의 차이에 대해서 설명하세요.

함수 호출이란 자신이 직접 작성하거나 라이브러리에 저장된 함수를 호출하는 것이다. 

* 라이브버리 함수들에는 프로그래밍 언어에서 제공하는 기본 함수들과 컴파일러별로 추가적으로 제공하는 API들이 속한다. 따라서 프로그램 내부에서 메모리 할당/해제가 가능하다.

시스템 콜(시스템 호출)의 기본적인 정의는 프로세스와 운영체제 간 인터페이스를 제공해주는 것이다. 즉 운영체제의 커널이 제공하는 서비스에 접근하기 위한 수단이라고 이해할 수 있다. 시스템 콜의 경우 프로세스 제어, 파일 관리, 장치 관리, 정보 유지보수, 통신 등 다양한 기능을 수행하기 위해 운영체제에 미리 정의가 되어 있는 함수를 사용하는 것이다. 

인터럽트와 시스템 콜의 차이에 대해서 설명하세요.

인터럽트는 하드웨어가 시스템의 수행 흐름을 바꾸기 위해 사용하는 것이고, 트랩의 경우 소프트웨어가 발생하는 인터럽트이다. 소프트웨어는 시스템 콜이라는 연산을 통해 트랩을 발생시킨다.

시스템 콜의 경우 프로그램이 커널에서 서비스를 요청할 수 있도록 하는 방법이며, 인터럽트는 CPU에게 특정 일을 즉각적으로 수행하도록 고지하는 이벤트이다. (하드웨어 인터럽트, 소프트웨어 인터럽트라는 개념으로 접근해서 이해하면 조금 더 수월할 듯 하다)