파이썬 문법

1. 입력

  1. input의 기본인자는 string이고 number로 받을 때는 int함수 사용
    1
    2
    3
    4
    5
    num = int(input('num: '))
    print(num)

    num = float(input('num: '))
    print(num)
  2. map을 활용한 input
    1
    2
    3
    4
    5
    6
    a, b = map(int, input().split())
    print(a+b)
    print(a-b)
    print(a*b)
    print(int(a/b))
    print(a%b)

2. 출력

  1. f-string
    출처: https://www.daleseo.com/python-f-strings/

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    x = 1
    y = 2
    print(f"{x} + {y}는 {x+y}입니다.")
    word = 'Python'
    print(f"{word}는 {len(word)}글자입니다.")
    print(f"대문자로는 {word.upper()}이고, 소문자로는 {word.lower()}입니다.")
    print(f"{word}의 첫 두 글자는 {word[:2]}입니다.")
    print(f"{word}를 거꾸로 하면 {word[::-1]}입니다.")
    print(f"3회 반복: {','.join([word]*3)}")
    from datetime import date
    print(f"오늘은 {date.today()}입니다.") # 객체 치환은 str() 내장함수가 기본
    print(f"오늘은 {date.today()!r}입니다.") # 디버깅할때 원한다면 !r을 붙여서 repr() 내장함수를 확인하는 것도 가능
    num = 1
    print(f"num={num}")
    print(f"{num=}")
    print(f"{2*15:3}", end='') # 글자 수 세자리로 출력
    print(f"{2*15:3}", end='')
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    1 + 2는 3입니다.
    Python는 6글자입니다.
    대문자로는 PYTHON이고, 소문자로는 python입니다.
    Python의 첫 두 글자는 Py입니다.
    Python를 거꾸로 하면 nohtyP입니다.
    3회 반복: Python,Python,Python
    오늘은 2024-05-27입니다.
    오늘은 datetime.date(2024, 5, 27)입니다.
    num=1
    num=1
     30 30%

  2. f-string 정렬
    출처: https://ooyoung.tistory.com/87

  • 왼쪽 정렬 및 문자: {문자:10s}
  • 가운데 정렬 및 정수: {정수:^10d}
  • 오른쪽 정렬 및 실수: {실수:>10f}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    names = ['청우', '은식', '재혁']
    nums = [15, 20, 49]

    for name, age in zip(names, nums):
        print(f"{name:10s}의 나이는 {age:^10d}세 이다.")

    for x in range(1,10,2):
        print(f'{x:>10d} x 2 = {x*2}입니다.')

    float = [0.55555, 0.66666, 0.777777]
    for x in float:
        print(f"둘째자리까지 표현 {x:10.2f}")

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    청우        의 나이는     15    세 이다.
    은식        의 나이는     20    세 이다.
    재혁        의 나이는     49    세 이다.
             1 x 2 = 2입니다.
             3 x 2 = 6입니다.
             5 x 2 = 10입니다.
             7 x 2 = 14입니다.
             9 x 2 = 18입니다.
    둘째자리까지 표현       0.56
    둘째자리까지 표현       0.67
    둘째자리까지 표현       0.78
  1. print 함수 활용
    출처: https://www.daleseo.com/python-print/

  • print시 파이썬이 자동으로 내용물을 str() 감싸서 출력한다.

    1
    2
    3
    4
    a = 123
    b = ['a','b','c']
    c = range(5)
    print(a,b,c)
    1
    123 ['a', 'b', 'c'] range(0, 5)

  • 객체 출력시 해당 함수가 가진 __str__() 매직함수를 호출하도록 되어 있다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class NumberHolder:
        def __init__(self, number):
            self.number = number

    print(NumberHolder(1))

    class NumberHolder:
        def __init__(self, number):
            self.number = number

        def __str__(self):
            return f"NumberHolder({self.number})"

    print(NumberHolder(1))

    1
    2
    <__main__.NumberHolder object at 0x1045e5a90>
    NumberHolder(1)

  • 여러 줄 출력

    1
    print("안녕", 123, [1, 2.5], {"이름": None, "관리자": True}, sep="\n")
    1
    2
    3
    4
    안녕
    123
    [1, 2.5]
    {'이름': None, '관리자': True}

  • 한 줄 출력

    1
    2
    3
    4
    5
    6
    7
    8
    9
    print("어떤 언어를 사용하십니까?")
    print("파이썬")
    print("자바스크립트")
    print("자바")

    print("어떤 언어를 사용하십니까?", end=" ")
    print("파이썬", end=", ")
    print("자바스크립트", end=", ")
    print("자바", end=" 👍\n")
    1
    2
    3
    4
    5
    어떤 언어를 사용하십니까?
    파이썬
    자바스크립트
    자바
    어떤 언어를 사용하십니까? 파이썬, 자바스크립트, 자바 👍
  1. 2차원 배열 출력
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    print("matrix: ", matrix)
    print()
    for row in matrix:
        print("row: ", row)
    print()
    print("*matrix:", *matrix, sep="\n")
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    matrix:  [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

    row:  [1, 2, 3]
    row:  [4, 5, 6]
    row:  [7, 8, 9]

    *matrix:
    [1, 2, 3]
    [4, 5, 6]
    [7, 8, 9]

3. 문자열(str)

  1. 인덱싱
    1
    2
    3
    4
    5
    6
    a = [1,2,3]
    print(a[0])
    print(type(a))
    b = "남청우"
    print(b[0])
    print(type(b))
    1
    2
    3
    4
    1
    <class 'list'>
    남
    <class 'str'>
  2. 슬라이싱
    1
    2
    3
    word = 'Python'
    print(word[::2])
    print(word[::-1])
    1
    2
    Pto
    nohtyP
  3. in
    1
    2
    my_string = "hello"
    print('e' in my_string)  # 출력: True
  4. len
    1
    2
    my_string = "hello"
    print(len(my_string))  # 출력: 5
  5. count
    1
    2
    my_string = "hello"
    print(my_string.count('l'))  # 출력: 2
  6. index
    1
    2
    my_string = "hello"
    print(my_string.index('l'))  # 출력: 2
  7. split
    문자열.split()
    문자열.split('구분자')
    문자열.split('구분자', 분할횟수)
    문자열.split(sep='구분자', maxsplit=분할횟수)
  • 리스트로 반환함.
  • sep 파라미터의 기본값은 none이며, 기본 동작은 한 칸 띄어쓰기.
  • maxsplit 파라미터의 기본값은 -1 이며, 기본 동작은 제한없이 자를 수 있을 때 까지 문자열 전체를 자름.
    1
    2
    3
    4
    a = 'a..b..c..d..e'
    b = a.split('..')
    print(b)
    print(type(b))
    1
    2
    ['a', 'b', 'c', 'd', 'e']
    <class 'list'>
  1. join
  • join 메서드는 문자열을 결합할 때 사용
  • separator.join(iterable)
    • separator: 각 요소 사이에 삽입될 문자열입니다.
    • iterable: 문자열로 구성된 시퀀스(예: 리스트, 튜플 등).
      1
      2
      3
      4
      5
      6
      7
      word = 'Python'
      print(','.join([word]))
      print(','.join(word))

      list = ['a', 'b', 'c']
      print(type("\n".join(list)))
      print("\n".join(list))
      1
      2
      3
      4
      5
      6
      Python
      P,y,t,h,o,n
      <class 'str'>
      a
      b
      c
  1. 문자열은 immutable(불변) 자료형
    리스트는 요소 추가(append()), 요소 삭제(remove()), 정렬(sort()), 뒤집기(reverse())와 같은 다양한 메서드를 제공합니다.
    반면에, 문자열은 변경할 수 없으므로 이러한 메서드를 제공하지 않습니다.
    1
    2
    my_string = "hello"
    # my_string[0] = 'H'  # 오류 발생

4. 리스트(list)

  1. 리스트 언패킹
    Python에서 리스트 앞에 *를 붙이면 리스트를 언패킹(unpacking)합니다. 이는 리스트의 각 요소를 개별적인 인수로 전달하는 것과 같은 효과를 줍니다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    my_list = [1, 2, 3]
    print(*my_list)  # 1 2 3

    def my_function(a, b, c):
        print(a, b, c)

    my_list = [1, 2, 3]
    my_function(*my_list)  # 1 2 3

    li = [[1,2,3],[4,5,6]]

    a,b,c = li[0]
    print(a,b,c)
    1
    2
    3
    1 2 3
    1 2 3
    1 2 3

  2. 리스트 메서드
    https://codinglevelup.tistory.com/67

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    list = [1,2,3]
    # 리스트 관련 내장함수
    max(list) # 3
    min(list) # 1
    len(list) # 3

    # 리스트 관련 메소드
    # 추가
    list.append(4)
    list.insert(4, 5)
    print(list)

    # 삭제
    list.remove(1)
    print(list)

    list.pop()
    print(list)

    del list[1]
    print(list)

    # 변경
    list[0] = 1
    print(list)

    # 탐색
    print(list.index(4))
    1
    2
    3
    4
    5
    6
    [1, 2, 3, 4, 5]
    [2, 3, 4, 5]
    [2, 3, 4]
    [2, 4]
    [1, 4]
    1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # 정렬
    list = [3,2,1]
    list.sort()
    print(list)

    list = [1,2,3]
    list.sort(reverse=True)
    print(list)

    list = [1, 4, 2, 7]
    list.reverse()
    print(list)

    # 개수 세기
    list = [1,1,2,3]
    print(list.count(1))
    1
    2
    3
    [1, 2, 3]
    [3, 2, 1]
    [7, 2, 4, 1]

  3. map과 필터함수

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def square(x):
        return x * x
    numbers = [1, 2, 3, 4, 5]
    result = map(square, numbers)
    print(list(result))  # [1, 4, 9, 16, 25]

    numbers = [1, 2, 3, 4, 5]
    result = map(lambda x: x * x, numbers)
    print(list(result))  # [1, 4, 9, 16, 25]

  4. 리스트 컴프리헨션
    Python의 리스트 컴프리헨션과 자바의 스트림(Stream) API는 비슷한 개념으로 동작함.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 리스트의 각 요소에 대해 제곱한 값을 포함하는 새로운 리스트 생성하기:
    original_list = [1, 2, 3, 4, 5]
    squared_list = [x ** 2 for x in original_list]
    print(squared_list)
    # 문자열 리스트에서 각 문자열의 길이를 포함하는 새로운 리스트 생성하기:
    words = ['apple', 'banana', 'orange']
    word_lengths = [len(word) for word in words]
    print(word_lengths)
    # 조건을 만족하는 요소만을 포함하는 새로운 리스트 생성하기:
    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    even_numbers = [x for x in numbers if x % 2 == 0]
    print(even_numbers)

  5. 리스트 값 전체 삭제

    1
    2
    3
    4
    5
    # 리스트 값 전체삭제하는 법
    my_list = [1,2,3,4]
    my_list = []  # 모든 값을 삭제한 빈 리스트로 초기화
    my_list.clear()  # 리스트 내 모든 요소 삭제
    my_list[:] = []  # 리스트 전체를 슬라이싱하여 모든 요소 삭제

  6. 슬라이싱

    1
    2
    3
    4
    5
    6
    list = ['남청우', '이재혁', '김은식']
    list.append('박영민')
    list.append('박지아')
    print(list[0:])
    print(list[1:3])
    print(list[0:-2])
    1
    2
    3
    ['남청우', '이재혁', '김은식', '박영민', '박지아']
    ['이재혁', '김은식']
    ['남청우', '이재혁', '김은식']

5. 튜플(tuple)

모습은 리스트와 거의 비슷하지만, 튜플에서는 리스트와 다른 2가지 차이점을 찾아볼 수 있다.

  • t2 = (1,)처럼 단지 1개의 요소만을 가질 때는 요소 뒤에 쉼표(,)를 반드시 붙여야 한다는 것
  • t4 = 1, 2, 3처럼 소괄호(())를 생략해도 된다는 점

튜플과 리스트의 가장 큰 차이는 요솟값을 변화시킬 수 있는지의 여부이다. 즉, 리스트의 요솟값은 변화가 가능하고 튜플의 요솟값은 변화가 불가능하다.

1
2
3
4
5
t1 = ()
t2 = (1,)
t3 = (1, 2, 3)
t4 = 1, 2, 3
t5 = ('a', 'b', ('ab', 'cd'))

6. 집합(set)

순서가 없고 집합 안에서 유니크한 값을 가지고 mutable 객체이다.
list나 dict의 경우 대괄호나 중괄호로 선언할 수 있지만, set은 dict타입과 동일한 중괄호를 사용하므로, 중괄호만으로는 생성할 수 없다. 따라서 set 생성자를 이용합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
s = {}
print(type(s))
set_example = set([1,2,1,1,3])
print(type(set_example))
print(set_example)

# add
set_example.add(4)
print(set_example)

# update
set_example.update([3,4,5])
print(set_example)

# remove
set_example.remove(5) # 없으면 에러 발생
print(set_example)

# discard
set_example.discard(5) # 없어도 에러 발생 안함
print(set_example)
1
2
3
4
5
6
7
# 복사(얕은 복사임)
# 얕은 복사는 객체의 최상위 레벨 속성만 복사하고, 중첩된 객체나 리스트와 같은 하위 레벨의 참조는 원본 객체와 동일하게 유지됩니다. 즉, 얕은 복사는 원본 객체와 복사된 객체가 같은 하위 레벨 객체를 참조하게 됩니다.
s = {1,3,5}
t = s.copy() # 얕은 복사 
t2 = set(s) # 얕은 복사
print(t)
print(t2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# 연산
# |
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}
c = a | b
print(c) # {1, 2, 3, 4, 5, 6, 7}

# &
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}
c = a & b
print(c) # {3, 4, 5}

# -
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}
c = a - b
print(c) # {1, 2}

# ^
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}
c = a ^ b
print(c) # {1, 2, 6, 7}

# =과 동시에 연산가능
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}
a |= b
print(a) # {1, 2, 3, 4, 5, 6, 7}
print(b) # {3, 4, 5, 6, 7}

# union
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}
c = a.union(b)
print(c) # {1, 2, 3, 4, 5, 6, 7}

# intersection - 교집합
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}
c = a.intersection(b)
print(c) # {3, 4, 5}

# difference
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}
c = a.difference(b)
print(c) # {1, 2}

# symmetric_difference
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}
c = a.symmetric_difference(b)
print(c) # {1, 2, 6, 7}

7. 딕셔너리(dictionary)

Python 딕셔너리(Dictionary)는 키(key)와 값(value) 쌍을 저장하는 데이터 구조입니다. 딕셔너리는 변경 가능(mutable)하며, 키는 고유해야 하고 변경 불가능(immutable)한 타입이어야 합니다. 값은 변경 가능하며 중복될 수 있습니다.

  • 딕셔너리 생성
    딕셔너리를 생성하는 방법은 여러 가지가 있습니다:

    1. 중괄호 사용:

      1
      my_dict = {"name": "Alice", "age": 25, "city": "New York"}

    2. dict() 생성자 사용:

      1
      my_dict = dict(name="Alice", age=25, city="New York")

    3. 키-값 쌍의 리스트 사용:

      1
      my_dict = dict([("name", "Alice"), ("age", 25), ("city", "New York")])

  • 딕셔너리 접근
    딕셔너리의 값에 접근하려면 키를 사용합니다:

    1
    2
    print(my_dict["name"])  # Alice
    print(my_dict["age"])   # 25

  • 딕셔너리 값 변경
    키를 사용하여 딕셔너리의 값을 변경할 수 있습니다:

    1
    2
    my_dict["age"] = 26
    print(my_dict["age"])  # 26

  • 딕셔너리 항목 추가
    새로운 키-값 쌍을 추가할 수 있습니다:

    1
    2
    my_dict["email"] = "alice@example.com"
    print(my_dict)  # {'name': 'Alice', 'age': 26, 'city': 'New York', 'email': 'alice@example.com'}

  • 딕셔너리 항목 삭제
    딕셔너리에서 항목을 삭제하는 방법은 여러 가지가 있습니다:

    1. del 키워드 사용:

      1
      2
      del my_dict["city"]
      print(my_dict)  # {'name': 'Alice', 'age': 26, 'email': 'alice@example.com'}

    2. pop() 메서드 사용:

      1
      2
      3
      email = my_dict.pop("email")
      print(email)  # alice@example.com
      print(my_dict)  # {'name': 'Alice', 'age': 26}

    3. popitem() 메서드 사용: 마지막 항목을 삭제하고 반환합니다 (Python 3.7+):

      1
      2
      3
      item = my_dict.popitem()
      print(item)  # ('age', 26)
      print(my_dict)  # {'name': 'Alice'}

  • 딕셔너리 메서드
    딕셔너리는 다양한 메서드를 제공합니다:

    • keys(): 딕셔너리의 모든 키를 반환합니다.

      1
      print(my_dict.keys())  # dict_keys(['name'])

    • values(): 딕셔너리의 모든 값을 반환합니다.

      1
      print(my_dict.values())  # dict_values(['Alice'])

    • items(): 딕셔너리의 모든 키-값 쌍을 반환합니다.

      1
      print(my_dict.items())  # dict_items([('name', 'Alice')])

    • get(): 키를 사용하여 값을 반환하며, 키가 없으면 기본값을 반환합니다.

      1
      2
      print(my_dict.get("name"))  # Alice
      print(my_dict.get("age", "Not Found"))  # Not Found

    • update(): 다른 딕셔너리나 키-값 쌍으로 현재 딕셔너리를 업데이트합니다.

      1
      2
      my_dict.update({"age": 26, "city": "New York"})
      print(my_dict)  # {'name': 'Alice', 'age': 26, 'city': 'New York'}

  • 반복
    딕셔너리를 반복(iterate)하여 키와 값에 접근할 수 있습니다:

    1
    2
    3
    4
    5
    6
    for key in my_dict:
        print(key, my_dict[key])

    # 또는 items() 메서드를 사용하여 키와 값을 동시에 얻을 수 있습니다:
    for key, value in my_dict.items():
        print(key, value)

  • 딕셔너리 컴프리헨션
    딕셔너리 컴프리헨션을 사용하여 간단하게 딕셔너리를 생성할 수 있습니다:

    1
    2
    squared_numbers = {x: x**2 for x in range(5)}
    print(squared_numbers)  # {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

  • 딕셔너리 병합

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    d1 = {'a': 'apple', 'b': 'banana'}
    d2 = {'b' : 'boat', 'c': 'car'}

    new_dict = {**d1, **d2}

    print(new_dict) # {'a': 'apple', 'b': 'boat', 'c': 'car'}

    new_dict2 = d1 | d2

    print(new_dict2) # {'a': 'apple', 'b': 'boat', 'c': 'car'}

  • 딕셔너리의 특징

    1. 변경 가능(mutable): 딕셔너리는 생성 후에 항목을 추가, 수정, 삭제할 수 있습니다.
    2. 키는 고유해야 함: 딕셔너리의 키는 중복될 수 없습니다.
    3. 키는 변경 불가능해야 함: 문자열, 숫자, 튜플 등 변경 불가능한(immutable) 타입만 키로 사용할 수 있습니다.
    4. 빠른 검색 속도: 딕셔너리는 해시 테이블을 기반으로 하여 평균적으로 O(1)의 시간 복잡도로 항목에 접근할 수 있습니다.

8. 기타

  1. and, or 우선순위
  • and가 or보다 우선순위가 높다.
  • and 이외 조건은 괄호가 쳐져있다고 판단하면 됨.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    a = int(input())

    if a % 4 == 0 and a % 100 != 0 or a % 400 == 0:
        print(1)
    else:
        print(0)

    if a % 4 == 0 and (a % 100 != 0 or a % 400 == 0):
        print(1)
    else:
        print(0)

  1. python swap

    1
    2
    3
    4
    a, b = 1, 2
    a, b = b, a

    print(f"a = {a}, b = {b}")

  2. “=” 연쇄적으로 사용 가능

    1
    2
    3
    a, b, c = 1, 2, 3
    a = b = c
    print(f"a = {a}, b = {b}, c = {c}")

  3. 아스키 코드

  • ord() : 문자의 아스키 코드값을 리턴하는 함수이다.
  • chr() : 아스키 코드값 입력으로 받아 그 코드에 해당하는 문자를 출력하는 함수이다.
    1
    2
    3
    a = 'a'
    print(ord(a)) # 97
    print(chr(97))

  1. not 연산자

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    age = 10

    if not age >= 9:
        print("not 연산자 결과 : True")
    else:
        print("not 연산자 결과 : False")

    list = []
    list2 = [1]

    print(not list) # True
    print(not list2) # False

  2. “//“ 의미
    “//“ 연산자는 나누기 연산을 수행하고 소수점 이하를 버리는 연산을 의미합니다. 

    1
    2
    3
    num = 8
    print(num / 2)
    print(num // 2)

  3. 제곱근
    n ** 0.5는 주어진 숫자 n의 제곱근을 나타냅니다. 파이썬에서 ** 연산자는 거듭제곱을 계산하는 데 사용되며, 0.5를 거듭제곱하는 것은 제곱근을 계산하는 것과 같습니다.
    예를 들어, 4 ** 0.5는 4의 제곱근을 나타내며, 결과는 2가 됩니다.
    마찬가지로, 9 ** 0.5는 9의 제곱근을 나타내며, 결과는 3이 됩니다.

    1
    2
    3
    4
    5
    from math import sqrt
    print(4**0.5)
    print(9**0.5)
    print(sqrt(4))
    print(sqrt(9))

  4. 파이썬 유일한 삼항연산자

    1
    2
    3
    4
    5
    x = 2
    y = 3
    a = x if x > y else y
    print(a)

  5. type

    1
    2
    3
    4
    5
    6
    7
    8
    str = 'hi'
    i = 1
    f = 1.1
    print(type(str))
    print(type(i))
    print(type(f))
    print(type(range(0,9)))
    print(type(map(int, [0,1])))
    1
    2
    3
    4
    5
    <class 'str'>
    <class 'int'>
    <class 'float'>
    <class 'range'>
    <class 'map'>

  6. Immutable 객체랑 mutable 객체

  • Immutable 객체 int, float, str, tuple
  • Mutable 객체 list, dict, set
  • 값을 바꾸면 immutable은 새로운 객체로 메모리 자체를 바꿔서 생성하는 것인데, Mutable은 값을 바꿔도 기존 객체의 주소는 동일하다.
  • 왜 이 개념이 중요한가?
    • 성능: Immutable 객체는 해시 가능(hashable)하므로, 딕셔너리의 키로 사용할 수 있습니다. 반면, mutable 객체는 값이 바뀔 수 있으므로 해시 가능하지 않습니다.
    • 안정성: Immutable 객체는 여러 곳에서 공유될 때도 안전하게 사용할 수 있습니다. 반면, mutable 객체는 변경될 수 있으므로 공유된 상태에서의 예측 불가능한 동작을 피하기 위해 주의가 필요합니다.
    • 해시 가능: 객체의 값이 변경되지 않고, 항상 동일한 해시 값을 반환하는 객체. 예를 들어, 정수(int), 문자열(str), 튜플(tuple)은 그 값을 변경할 수 없으므로 해시 가능합니다. 따라서 딕셔너리의 키나 집합의 원소로 사용할 수 있습니다.
    • 해시 불가능: 객체의 값이 변경될 수 있어, 해시 값이 달라질 수 있는 객체. 예를 들어, 리스트(list)나 딕셔너리(dict)는 변경 가능(mutable)하기 때문에 해시할 수 없습니다. 이러한 객체들은 딕셔너리의 키나 집합의 원소로 사용할 수 없습니다.

  1. 모듈러 연산
    Python의 int는 메모리가 허용하는 한 무제한의 크기를 지원하는 BigInteger 타입으로, 이론적으로 매우 큰 정수를 다룰 수 있습니다. 그러나 연산 속도는 수의 자릿수에 따라 크게 달라집니다. 덧셈과 뺄셈의 경우, 연산 속도는 자릿수에 선형적으로 비례하지만, 곱셈과 나눗셈의 연산 속도는 자릿수의 증가에 따라 비선형적으로 증가하여 훨씬 더 느려집니다. 따라서, 매우 큰 정수를 다루는 알고리즘에서는 연산 속도 최적화를 고려해야 합니다. 특히, 나머지 연산을 포함하는 문제에서는 중간 계산 결과가 너무 커지지 않도록 모듈러 연산을 적절히 사용하여 시간 복잡도를 관리하는 것이 중요합니다.

  2. 시간복잡도 고려
    C++의 find(vector.begin(), vector.end(), x), Python의 x in list, list.count(x), list.index(x) 등은 평범한 배열에서 특정 원소를 찾을 때 전체를 탐색합니다. 라이브러리 함수도 전처리를 하지 않기 때문에 직접 반복문을 돌리는 것과 시간 복잡도에서 차이가 없습니다. Python의 문자열 검색(x in str)도 동일하게 느립니다. 이러한 작업은 모두 O(n) 시간 복잡도를 가집니다.

  3. not in

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    # not in 연산자는 특정 요소가 시퀀스(리스트, 튜플, 문자열 등) 안에 존재하지 않을 때 True를 반환합니다. 다음은 not in 연산자의 예제입니다:
    # 리스트에서 not in 사용하기
    my_list = [1, 2, 3, 4, 5]
    if 6 not in my_list:
        print("6은 리스트에 없습니다.")

    # 문자열에서 not in 사용하기
    my_string = "Hello, world!"
    if "x" not in my_string:
        print("문자열에 'x'가 없습니다.")

    # 튜플에서 not in 사용하기
    my_tuple = (1, 2, 3, 4, 5)
    if 6 not in my_tuple:
        print("6은 튜플에 없습니다.")

    # 사전에서 not in 사용하기 (키 검사)
    my_dict = {'a': 1, 'b': 2, 'c': 3}
    if 'd' not in my_dict:
        print("'d' 키가 사전에 없습니다.")

    # 딕셔너리의 값 중에 'John'이 포함되어 있는지 확인
    my_dict = {'name': 'John', 'age': 30, 'city': 'New York'}
    if 'John' not in my_dict.values():
        print('John is not in the dictionary values.')
    else:
        print('John is in the dictionary values.')

    # 문자열에서 not in 사용하기 (부분 문자열 검사)
    my_string = "Python programming"
    if "Java" not in my_string:
        print("Java 문자열이 Python 문자열 안에 없습니다.")

  4. list 연결

    1
    2
    3
    4
    5
    # [Do it! 실습 1-20] 1부터 12까지 8을 건너 뛰고 출력하기 2
    # 와 이렇게 리스트 연결이 가능하구나.
    for i in list(range(1, 8)) + list(range(9, 13)):
        print(i, end=' ')
    print()

  5. for else문
    for문과 else를 같이 쓰는 것이 가능하다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for i in range(10):
        print('hi')
        if i == 5:
            break
    else:
        print("for문 정상적으로 완료")

    for i in range(10):
        print('hi')
    else:
        print("for문 정상적으로 완료")

  6. if not문

    1
    2
    3
    4
    5
    6
    7
    8
    x = 0
    if not x:
        print("x is zero")  # 출력: x is zero

    y = []
    if not y:
        print("y is empty")  # 출력: y is empty

  7. __name__이 __main__인 경우
    if name == ‘main‘:은 파이썬 스크립트 파일이 직접 실행될 때 해당 블록 안의 코드를 실행하도록 하는 조건문입니다.
    이것은 모듈로서 다른 스크립트에 import되었을 때는 실행되지 않습니다. 따라서 이 부분에 코드를 작성하면 해당 스크립트 파일이 실행될 때만 동작하도록 할 수 있습니다.
    이러한 패턴을 사용하면 스크립트 파일을 모듈로서 import해도 코드 블록이 실행되지 않아서 의도치 않은 동작을 방지할 수 있습니다.

  8. 절대값

    1
    2
    3
    # |A[0] - A[1]|
    A = [-10, 8]
    print(abs(A[0] - A[1]))

  9. lambda

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    add = lambda x, y: x + y
    print(add(3, 5))  # 출력: 8

    numbers = [1, 2, 3, 4, 5]
    squared = list(map(lambda x: x**2, numbers))
    print(squared)  # 출력: [1, 4, 9, 16, 25]

    check_even = lambda x: x % 2 == 0
    print(check_even(4))  # 출력: True
    print(check_even(3))  # 출력: False

    points = [(1, 2), (3, 1), (5, 5), (0, 1)]
    sorted_points = sorted(points, key=lambda x: x[1])
    print(sorted_points)  # 출력: [(3, 1), (0, 1), (1, 2), (5, 5)]

  10. max의 key 사용

    1
    2
    3
    numbers = [-3, -7, 2, 9, -5]
    max_abs = max(numbers, key=abs)
    print(max_abs)  # 출력: -9

  11. global 예약어 사용

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # global 예약어 사용법
    x = 0

    def modify_global_variable():
        global x
        x = 10

    print(x)  # 출력: 0
    modify_global_variable()
    print(x)  # 출력: 10

  12. max, min 비교값 설정

    1
    2
    3
    4
    5
    6
    7
    # float('inf')는 무한대를 나타내는 특수한 부동소수점 수를 의미합니다. 이는 어떤 수와 비교해도 항상 크거나 같음을 의미합니다. 
    # float('-inf')는 음의 무한대를 나타내며, 어떤 수와 비교해도 항상 작거나 같음을 의미합니다.

    # 따라서 min_result에는 문제에서 주어진 조건을 만족하는 최소값을 찾기 위해 초기값으로 무한대를 설정하고, 
    # max_result에는 최대값을 찾기 위해 초기값으로 음의 무한대를 설정합니다.
    min_result = float('inf')
    max_result = float('-inf')

  13. sort

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # sort는 컬렉션 제일 앞의 요소 순으로 정렬해준다
    edgeList = []
    cnt = 0
    for i in range(10,0,-1):
        cnt += 1
        edgeList.append([i,cnt])

    print(edgeList)
    edgeList.sort() # edgeList.sort(key=lambda x: x[0])
    print(edgeList)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # sort 함수의 key 매개변수는 정렬 기준을 지정하는 역할을 합니다. 이 매개변수에는 정렬에 사용할 키를 생성하는 함수를 전달할 수 있습니다. 
    # key 함수는 각 요소를 정렬할 때 호출되며, 해당 요소를 대표하는 값(키)을 반환합니다. 정렬은 이 반환된 키 값을 기준으로 이루어집니다.

    # 예를 들어, 문자열의 길이에 따라 정렬하고 싶은 경우, key 매개변수에 len 함수를 전달할 수 있습니다. 이렇게 하면 각 문자열의 길이를 기준으로 정렬됩니다.

    my_list = ['apple', 'banana', 'cherry', 'date']
    my_list.sort(key=len)
    print(my_list)  # 출력: ['date', 'apple', 'banana', 'cherry']

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # 튜플의 첫 번째 요소를 오름차순으로 정렬하고, 두 번째 요소를 내림차순으로 정렬하려면 정렬 키를 지정할 때 각 요소에 대해 다음과 같이 조작할 수 있습니다.

    applicants.sort(key=lambda x: (x[0], -x[1])) # 리스트도 마찬가지이다.
    # 여기서 lambda x: (x[0], -x[1])는 튜플의 첫 번째 요소는 오름차순으로, 두 번째 요소는 내림차순으로 정렬하도록 정렬 키를 지정합니다. -x[1]는 두 번째 요소를 음수로 변환하여 내림차순으로 정렬하는데 사용됩니다.

    # 리스트도 마찬가지
    edgeList = []
    cnt = 0
    for i in range(0,10,1):
        cnt += 1
        edgeList.append([i,cnt])

    print(edgeList)
    edgeList.sort(key=lambda x: (-x[1], x[0]))
    print(edgeList)

  14. reversed

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # 리스트 생성
    original_list = [1, 2, 3, 4, 5]

    # reversed 함수를 사용하여 역순으로 변환한 리스트 생성
    reversed_list = list(reversed(original_list))

    # 결과 출력
    print("원본 리스트:", original_list)
    print("역순 리스트:", reversed_list)

  15. 삼항연산자

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # 조건 표현식
    # 조건이 참일 때와 거짓일 때의 값을 변수에 저장하는 예제
    x = 10
    result = "Even" if x % 2 == 0 else "Odd"
    print(result)  # 출력: Even

    # 조건이 참일 때와 거짓일 때의 값을 직접 출력하는 예제
    x = 10
    print("Even" if x % 2 == 0 else "Odd")  # 출력: Even

  16. 사용자 입력 eof로 막을 때

    1
    2
    3
    4
    5
    6
    while True:
    	try:
    		a,b = map(int, input().split())
    		print(a+b)
    	except:
    		break

  17. 2차원 배열 출력

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

    # 2차원 배열을 예쁘게 출력하는 방법에는 여러 가지가 있습니다. 여기에는 Python의 예시가 포함되어 있습니다:
    # 이중 루프를 사용하여 출력하기: 이 방법은 각 행을 순회하면서 각 행의 요소를 출력하는 방법입니다.

    arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

    for row in arr:
        for elem in row:
            print(elem, end=" ")
        print()  # 각 행이 끝날 때마다 줄바꿈
    # List Comprehension과 join() 함수 사용하기: 이 방법은 리스트 컴프리헨션과 join() 함수를 사용하여 각 행을 문자열로 변환한 후, 이를 줄바꿈하여 출력하는 방법입니다.
    arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

    for row in arr:
        print(" ".join(map(str, row)))

9. itertools

  • combinations 함수: 리스트의 요소들 중에서 지정된 길이의 조합을 반환합니다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    import itertools

    items = ['a', 'b', 'c']
    combos = itertools.combinations(items, 2)

    for combo in combos:
        print(combo)
        
    # 출력:
    # ('a', 'b')
    # ('a', 'c')
    # ('b', 'c')

  • permutations 함수: 리스트의 요소들을 모든 가능한 순열로 반환합니다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    import itertools

    items = ['a', 'b', 'c']
    perms = itertools.permutations(items)

    for perm in perms:
        print(perm)
    # 출력:
    # ('a', 'b', 'c')
    # ('a', 'c', 'b')
    # ('b', 'a', 'c')
    # ('b', 'c', 'a')
    # ('c', 'a', 'b')
    # ('c', 'b', 'a')

  • cycle 함수: 리스트의 요소들을 무한히 반복합니다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    import itertools

    items = ['a', 'b', 'c']
    cycles = itertools.cycle(items)

    for _ in range(5):
        print(next(cycles))
    # 출력:
    # 'a'
    # 'b'
    # 'c'
    # 'a'
    # 'b'

  • chain 함수: 여러 개의 iterable을 하나의 iterable로 결합합니다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    import itertools

    list1 = [1, 2, 3]
    list2 = ['a', 'b', 'c']
    chained = itertools.chain(list1, list2)

    for item in chained:
        print(item)
    # 출력:
    # 1
    # 2
    # 3
    # 'a'
    # 'b'
    # 'c'

  • repeat 함수: 지정된 요소를 지정된 횟수만큼 반복합니다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    import itertools

    repeated = itertools.repeat('hello', 3)

    for item in repeated:
        print(item)
    # 출력:
    # 'hello'
    # 'hello'
    # 'hello'

    ``

  • zip 함수

    1
    2
    3
    4
    5
    6
    7
    8
    import itertools
    # 리스트들을 묶어서 튜플로 반환
    list1 = [1, 2, 3]
    list2 = ['a', 'b', 'c']
    zipped = zip(list1, list2)

    for item in zipped:
        print(item)

  • any 함수

    1
    2
    3
    4
    5
    import itertools
    # 리스트의 요소 중 하나라도 True이면 True를 반환
    bool_list = [False, True, False]
    result = any(bool_list)
    print(result)  # 출력: True

  • all 함수

    1
    2
    3
    4
    5
    import itertools
    # 리스트의 모든 요소가 True이면 True를 반환
    bool_list = [True, True, True]
    result = all(bool_list)
    print(result)  # 출력: True

알고리즘

1. 등차수열

  • 수열 A: 5, 7, 9, 11, … ‘공차가 2이고, 초항이 5인 등차수열’
  • 수열 B: 6, 1, -4, -9, … ‘공차가 -5이고, 초항이 6인 등차수열’
  • 수열 C: 7, 7, 7, 7, … ‘공차가 0이고, 초항이 7인 등차수열’

2. 한수

정의
어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다.

문제
N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.

풀이
만약에 N이 130이 주어졌다면 1부터130까지의 수 각각에 대해 그 수를 구성하는 수가 등차수열을 만족하는지 보면 된다.

  • 1: 1하나 뿐이니까 등차수열
  • 2: 같은경우
  • 3: 같은경우
  • 10: 길이가 2고 각항이 1 0 인 수열. 공차가 -1인 등차수열임. 체크
  • 11: 길이가 2이고 각항이 1 1 인 수열. 공차가 0 인 등차수열임.체크
  • 100: 길이가 3이고 각항이 1 0 0 인 수열. 등차수열이 아님
  • 101:길이가 3이고 각항이 1 0 1 인 수열. 등차수열 아님
  • 123: 길이가 3이고 각항이 1 2 3 인 수열.공차가 1인 등차수열임. 체크

즉 한 자리수랑 두 자리수는 모두 한수에 해당함

  • 1, 2, …, 9: 모두 한수 (한 자리 수)
  • 10, 11, …, 99: 모두 한수 (두 자리 수)

3. 0의 팩토리얼이 1인 이유

4! = 4 * 3 * 2 * 1
4! = 4 * (4-1)!
4! = 4 * 3!

1! = 1 * (1-1)!
1! = 1 * 0! = 1
-> 0! = 1

4. 가우스의 덧셈

1
2
3
4
# 1~n까지 정수의 합
n = 10
sum = n*(n+1)//2
print(sum)

5. 순열과 조합 (permutation과 combination)

순열은 요소들의 순서에 의미가 있는 경우를 나타냅니다.
예를 들어, 주어진 요소들의 순서를 변경하여 만들어지는 모든 경우의 수를 순열이라고 합니다.
n개의 요소 중에서 r개를 선택하여 나열할 수 있는 경우의 수를 nPr로 표기합니다. 수식으로는 nPr = n! / (n - r)! 입니다.
예를 들어, A, B, C 세 개의 요소가 있을 때, 이를 나열하는 모든 경우의 수는 ABC, ACB, BAC, BCA, CAB, CBA로 총 6가지입니다. - 3*2*1 / 0!

조합은 요소들의 순서가 중요하지 않고, 요소들의 선택만으로 구성된 경우를 나타냅니다.
예를 들어, n개의 요소 중에서 r개를 선택하여 만들어지는 모든 경우의 수를 조합이라고 합니다.
n개의 요소 중에서 r개를 선택하는 경우의 수를 nCr로 표기합니다. 수식으로는 nCr = n! / (r! * (n - r)!) 입니다.
예를 들어, A, B, C 세 개의 요소가 있을 때, 이를 선택하여 만들어지는 모든 조합의 수는 AB, AC, BC로 총 3가지입니다. - 3*2*1 / 2*1*1

6. 트리의 간선 수

트리란 사이클이 없이 모든 정점이 연결되어있는 그래프
사이클이 없는 그래프이므로 간선의 개수는 e-1이다.

7. 최소 스패닝 트리 문제

n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리를 신장트리라 합니다.
다른 말로, 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프 입니다. 이 때, 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 합니다.
이런 특징들로부터 우리는 스패닝 트리가 유일하지 않고 여러개가 존재합니다.
가중치 그래프의 여러 개의 스패닝 트리 중 가중치의 합이 가장 작은 트리를 찾는 문제입니다.

8. 정점과 간선에서 순열과 조합 사용

  • 무방향 그래프:

    • 두 정점 간의 간선은 하나만 존재합니다.
    • 최대 간선 수는 조합을 사용해 계산되며, 공식은:
      $$
      \frac{n \times (n - 1)}{2}
      $$
    • 예: 4개의 정점에서 2개의 정점을 선택하면 간선의 수는 6개입니다.

  • 단방향 그래프:

    • 두 정점 간에 양방향으로 간선을 연결할 수 있습니다.
    • 최대 간선 수는 순열을 사용해 계산되며, 공식은:
      $$
      n \times (n - 1)
      $$
    • 예: 4개의 정점에서 2개의 정점을 선택하면 간선의 수는 12개입니다.

  • 순열 (단방향 그래프):
    4개의 정점에서 2개의 정점을 선택해 순서를 고려한 간선의 개수를 계산하는 공식:
    $$
    nPr = \frac{n!}{(n - r)!}
    $$

    • 예: $4! / (4-2)! = \frac{4 \times 3 \times 2 \times 1}{2 \times 1} = 12$

  • 조합 (무방향 그래프):
    4개의 정점에서 2개의 정점을 선택해 순서를 고려하지 않은 간선의 개수를 계산하는 공식:
    $$
    nCr = \frac{n!}{r! \times (n - r)!}
    $$

    • 예: $\frac{4!}{2! \times (4-2)!} = \frac{4 \times 3 \times 2 \times 1}{2 \times 1 \times 2 \times 1} = 6$

9. 순열 활용

n개의 숫자가 있고 n-1개의 연산자가 있다
예를 들어 n이 6이고 연산자는 2,1,1,1이면 (+,-,*,/)
1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6
숫자는 자리를 바꿀 수 없고 연산자만 자리를 바꾼다면
모든 경우의 수는 60가지이다.
계산 방법은 순열인데 5개 중에 3개의 순열을 맞추면 된다.
5개 중에 3개의 순열을 맞추면 나머지에 + 2개를 끼워넣기만 하면 된다.
그러므로 5! / 2! 이다

n이 3이고 연산자는 2,1이면 경우의 수는 3! / 2! 이다. 즉 3가지이다.
++x
+x+
x++

10. 최소 힙, 최대 힙

최대 힙(Max Heap) : 부모 노드는 자식 노드보다 작지만 않으면 된다. + 완전이진트리이다.
최소 힙(Min Heap) : 부모 노드는 자식 노드보다 크지만 않으면 된다. + 완전이진트리이다.
최대 힙에서의 삽입 : 트리의 새 노드에서 시작해서 루트쪽으로 올라가는 방법을 사용한다.
삽입되는 원소는 새 노드에 삽입이 되고나서, 최대 힙이 될 때까지 위로 올라가는 과정을 반복한다.
최대 힙에서의 삭제 : 최대 힙에서 원소를 삭제할 때는 힙(Heap)의 루트(Root)에서 삭제한다.
루트노드가 비워져 있는 상태이고, 가장 마지막 노드가 루트노드로 올라오게 된다.
새로 올라온 값이 제자리를 찾아갈 수 있도록 자식 노드랑 비교해 큰 값이랑 스위칭하면 된다. 이 과정을 반복하면서 내려가면 된다.

힙 자료구조를 직접 구현하는 방법을 Python과 Java로 설명드리겠습니다. 여기서는 **최대 힙(Max Heap)**을 예로 들어, 삽입과 삭제 연산을 구현해보겠습니다. 큐를 사용할 필요는 없으며, 배열을 이용해 직접 힙을 구현할 수 있습니다.

최소힙, 최대힙 둘다 추가하는 경우는 부모노드랑 자기자신과 비교해서 자기자신이 작거나 크면 switch해주면서 최상단 노드까지 가면 된다.
삭제하는 경우엔 좀 다른데, 최상단 노드를 popleft하고 제일 끝 리프노드를 최상단 노드에 appendLeft해준다. 그리고 자식 노드 두명 중에 더 작은 거랑 자기 자신을 스위칭하면 최소 힙이고 더 큰 걸로 자기 자신을 스위칭하면 최대 힙이다.

Python에서 최소 힙과 최대 힙

Python에서는 기본적으로 heapq 모듈이 제공되며, 이는 **최소 힙(Min Heap)**으로 동작합니다. 최대 힙(Max Heap)을 구현하기 위해서는 값에 음수를 곱하여 최소 힙으로 동작하도록 만들 수 있습니다.

최소 힙 예시 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import heapq

# 최소 힙 생성
min_heap = []

# 요소 삽입
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 20)
heapq.heappush(min_heap, 5)

# 최소값 출력 및 삭제
print(heapq.heappop(min_heap))  # 출력: 5
print(heapq.heappop(min_heap))  # 출력: 10
print(heapq.heappop(min_heap))  # 출력: 20
  • heappush: 힙에 요소를 추가합니다.
  • heappop: 힙에서 최솟값을 제거하고 반환합니다.

최대 힙 예시 (Python)

최대 힙은 기본 제공되지 않지만, 음수 값을 활용하여 최소 힙을 최대 힙처럼 사용할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import heapq

# 최대 힙 생성 (음수를 사용하여 최소 힙으로 최대 힙 동작을 구현)
max_heap = []

# 요소 삽입 (음수로 변환하여 삽입)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)
heapq.heappush(max_heap, -5)

# 최대값 출력 및 삭제 (음수로 변환된 값을 다시 양수로 변환)
print(-heapq.heappop(max_heap))  # 출력: 20
print(-heapq.heappop(max_heap))  # 출력: 10
print(-heapq.heappop(max_heap))  # 출력: 5

Java에서 최소 힙과 최대 힙

Java에서는 PriorityQueue 클래스를 사용하여 힙을 구현할 수 있습니다. 기본적으로 PriorityQueue는 **최소 힙(Min Heap)**으로 동작합니다. 최대 힙(Max Heap)을 구현하려면 Comparator를 사용하여 역순으로 정렬되도록 해야 합니다.

최소 힙 예시 (Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        // 최소 힙 (기본 PriorityQueue)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 요소 삽입
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(5);

        // 최소값 출력 및 삭제
        System.out.println(minHeap.poll());  // 출력: 5
        System.out.println(minHeap.poll());  // 출력: 10
        System.out.println(minHeap.poll());  // 출력: 20
    }
}
  • add: 힙에 요소를 추가합니다.
  • poll: 힙에서 최솟값을 제거하고 반환합니다.

최대 힙 예시 (Java)

최대 힙을 구현하기 위해 Comparator를 사용하여 정렬 순서를 반대로 지정합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        // 최대 힙 (PriorityQueue with reverse order)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 요소 삽입
        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(5);

        // 최대값 출력 및 삭제
        System.out.println(maxHeap.poll());  // 출력: 20
        System.out.println(maxHeap.poll());  // 출력: 10
        System.out.println(maxHeap.poll());  // 출력: 5
    }
}
  • Collections.reverseOrder(): 기본 오름차순 정렬을 내림차순으로 바꿔서 최대 힙으로 동작하게 합니다.

11. DAG와 위상정렬

DAG와 위상정렬
Directed Acyclic Graphs(DAG)는 방향 그래프이면서 비순환 그래프이다.

위상 정렬은 사이클이 없는 방향 그래프 (DAG)에 대해서만 수행할 수 있다.
※ DAG (Direct Acyclic Graph) : 순환하지 않는(=사이클이 없는) 방향 그래프

위상 정렬에서는 여러 가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재할 수 있다는 의미이다.

모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단할 수 있다. 왜냐하면 사이클에 포함된 원소 중에서 해당되는 어떠한 원소도 큐에 들어가지 못하게 되기 때문이다.

보통 큐로 구현하나, 스택을 이용한 DFS를 이용해 위상 정렬을 구현할 수도 있다.

시간 복잡도는 O(V+E)
위상 정렬을 수행할 때는 차례대로 모든 노드를 확인하면서 (O(V)), 해당 노드에서 출발하는 간선을 차례대로 제거(O(E))해야 한다. 따라서 노드와 간선을 모두 확인하는 것을 고려하여 O(V) + O(E) = O(V+E)의 시간이 소요된다

12. visited가 필요 없는 경우

사이클이 없다면 visited가 필요 없다.
방향 그래프이면 인접리스트를 중복으로 만들 필요 없다.
위상정렬은 DAG 조건에서 되므로 vistied가 필요 없다.
다익스트라도 최소비용으로 조건을 달아 방문한 노드를 방문 안하니 visitied가 필요 없다.

13. 시간복잡도

출처: https://invrtd-h.tistory.com/50

“컴퓨터는 1초에 1억-2억 번을 연산할 수 있다.”
대부분의 문제는 시간제한이 1초이고, 경험적으로 봤을 때 대부분의 골드급 문제는 0.1초~0.3초 안에 풀릴 수 있도록 설계되어 있습니다.
보통 2000만 번의 연산을 거치면 문제가 풀린다고 가정하는 것이 꽤나 합리적입니다.

n 범위 시간복잡도 대표 알고리즘
n <= 10 O(n!) Brute forcing
n <= 20 O(2^n), O(n^2 × 2^n) 비트마스크 DP
n <= 50 O(√2^n) MITM
n <= 500 O(n^3) 행렬 체인 곱셈
n <= 5,000 O(n^2)
n <= 100,000 O(n√n), O(n log^2 n) 모의 알고리즘
n <= 1,000,000 O(n log n) 정렬, LIS, 등…
n <= 10,000,000 O(n) 피보나치 (DP), DFS, 트리 탐색
그 이상 O(log n), O(1) 이진 탐색, 지수 함수, 해싱

13. 정리 필요

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# -------------------------------------------
# 1904번 01타일
# 00과 1로만 순열을 맞춰야 함

# 1904번 01타일
# 00과 1로만 순열을 맞춰야 함

# 1개의 타일을 만들어야 하면 
# 1

# 2개의 타일을 만들어야 하면 
# 00 0개일 경우 3!/3! 
# 00 1개일 경우 2!/1  
# 2

# 3개의 타일을 만들어야 하면 
# 00 0개일 경우 3!/3! 
# 00 1개일 경우 2!/1  
# 1+2 = 3 

# 4개의 타일을 만들어야 하면 
# 00 0개일 경우 4!/4! - 반장선거 4명 나왔는데, 4명 다 똑같은 지위라서 투표 수 순서 상관없음 그래서 4!로 나눔
# 00 1개일 경우 3!/2! - 반장선거 3명 나왔는데, 1 이름 2명이 똑같은 지위라서 투표 수 순서 상관없음 그래서 2!로 나눔
# 00 2개일 경우 2!/2! - 반정선거 2명 나왔는데, 00 이름 2명이 똑같은 지위라서 투표 수 순서 상관없음 그래서 2!로 나눔
# 1+3+1 = 5 

# 5개의 타일을 만들어야 하면
# 00 0개일 경우 5!/5! - 반장선거 5명 나왔는데, 5명 다 똑같은 지위라서 투표 수 순서 상관없음 그래서 5!로 나눔
# 00 1개일 경우 4!/3! - 반장선거 4명 나왔는데, 1 이름 3명이 똑같은 지위라서 투표 수 순서 상관없음 그래서 3!로 나눔
# 00 2개일 경우 3!/2! - 반정선거 3명 나왔는데, 00 이름 2명이 똑같은 지위라서 투표 수 순서 상관없음 그래서 2!로 나눔
# 1+4+3 = 8

# 6개의 타일을 만들어야 하면
# 00 0개일 경우 6!/6! - 반장선거 6명 나왔는데, 6명 다 똑같은 지위라서 투표 수 순서 상관없음 그래서 6!로 나눔
# 00 1개일 경우 5!/4! - 반장선거 5명 나왔는데, 1 이름 4명이 똑같은 지위라서 투표 수 순서 상관없음 그래서 4!로 나눔
# 00 2개일 경우 4!/2!2! - 반정선거 4명 나왔는데, 00 이름 2명이 똑같은 지위, 1 이름 2명이 똑같은 지위라서 투표 수 순서 상관없음 그래서 2!와 2!로 나눔
# 00 3개일 경우 3!/3! - 반정선거 3명 나왔는데, 00 이름 3명이 똑같은 지위라서 투표 수 순서 상관없음 그래서 3!로 나눔
# 1+5+6+1 = 13

# 7개의 타일을 만들어야 하면
# 00 0개일 경우 7!/7!
# 00 1개일 경우 6!/5!
# 00 2개일 경우 5!/2!3!
# 00 3개일 경우 4!/3!
# 1+6+10+4 = 21