Skip to content

Latest commit

 

History

History
219 lines (196 loc) · 12 KB

11_algorithm_problems.md

File metadata and controls

219 lines (196 loc) · 12 KB

11. 문제 풀이 연습: 정렬, 비밀번호, 소수, 볼링 점수

이미지: note_31 · note_32 · note_41 · note_42 · note_43 · note_44 · note_45 · note_46

1. 문제를 푸는 기본 흐름

  • 표현 / 용도, 의도를 생각하며 코드를 읽기
  • 키워드: 파이썬에서 사용한다고 정의한 글자 (if, for, while, True, False ...)
  • 흐름(과정) 정의: 처리과정 설계
    1. 필요한 변수를 정확히 적기: 무엇을 저장하고 사용할지
    2. 기능(작업): 데이터 가져오기 -> 연산 -> 저장 -> 원하는 값을 화면에 출력
  • 예: 숫자 3, 6의 합을 프린트
    • 변수: 숫자 2개, 결과값 1개
    • 작업: 숫자 가져오기, 숫자끼리 더하기, 결과값 저장, 원하는 값 출력
  • 코드 한 줄 한 줄을 "변수명 접근 -> 연산 -> 결과 저장(변수명, 대입연산자, 결과값) -> 화면출력(print 활용법)" 순으로 손으로 해석해 보기
  • 노트 문구: "변수명, 대입연산자, 리터럴 / 암기형 떠오르기"
a, b = 3, 6          # 변수: 숫자 2개
result = a + b       # 연산 후 결과값 저장
print(result)        # 9

2. 숫자 3개 정렬 -> N개로 일반화

문제

  • 사용자로부터 숫자 3개를 입력받아 1) 큰 순서대로 2) 작은 순서대로 나열
  • 입력 방식: 각각의 변수에 대입 vs 하나의 변수(list)에 대입
    • 변수 여러 개: 숫자가 많아지면 코드가 달라짐
    • list 하나: 숫자가 많아져도 코드가 크게 바뀌지 않음
  • 노트 강조: 문제를 보고 구체적으로 상황을 정해야 함(문제 정의). 현재는 숫자 3개이지만 10개여도 되는 범용 코드를 목표로 함

생각 순서

  1. list [item1, ...]를 숫자로 정의
  2. item 순서를 규칙에 따라 변경
  3. index 순서를 변경 (보완 필요)
  • 예: 인덱스 [4, 3]을 [3, 4]로 바꾸고 싶다 = index 0 자리에 1번 값, index 1 자리에 0번 값
    • 문제: A[0] = A[1]을 하는 순간 원래 A[0] 값이 사라짐 -> 임시 변수가 필요
    • 2개만 반복하는 경우의 틀: if A[0] < A[1]: n = A[0]; A[0] = A[1]; A[1] = n
  • 리스트가 길어지면: index i(결과 저장 자리), j(비교군 가져오기)를 쓰는 이중 반복
def sort_desc(A):
    """큰 순서대로 (노트 코드: A[i] < A[j]이면 교환)"""
    A = list(A)                       # 원본은 그대로 두려고 복사
    for i in range(len(A) - 1):       # 마지막 요소는 비교할 대상이 없음
        for j in range(i + 1, len(A)):
            if A[i] < A[j]:
                n = A[i]              # 임시 변수로 교환
                A[i] = A[j]
                A[j] = n
    return A

print(sort_desc([4, 3, 9]))                 # [9, 4, 3]
print(sort_desc([5, 1, 7, 3, 9, 2, 8]))     # 숫자가 늘어도 같은 코드
  • i 범위가 range(len(A) - 1)인 이유: i가 마지막 인덱스이면 j로 비교할 요소가 없기 때문
  • 노트 메모: for를 쓸 때 횟수 제한 등을 설정하는 것도 방법
  • 오름차순(작은 순서대로)은 <를 >로 바꾸면 됨 (노트의 < 옆에 "오름차순?" 메모, [판독 불확실])
  • 파이썬에서는 임시 변수 없이 A[i], A[j] = A[j], A[i]로 교환 가능 (노트: "비추천?" 느낌의 메모가 있으나 [판독 불확실])
def sort_asc(A):
    A = list(A)
    for i in range(len(A) - 1):
        for j in range(i + 1, len(A)):
            if A[i] > A[j]:
                A[i], A[j] = A[j], A[i]   # 튜플 언패킹 교환
    return A

print(sort_asc([4, 3, 9]))   # [3, 4, 9]
print(sorted([4, 3, 9]))     # 내장 함수 sorted()와 같은 결과

3. 비밀번호 검증

조건 (Q2)

  1. 길이 8자 이상
  2. 숫자, 문자, 특수문자 조합 (!, #, @ 허용)
  3. 대문자 1개 이상 포함
  • 제대로 만들어진 비밀번호인지 확인. 위배되면 약속 위반(예: 8자 이상이 아니면 등)

설계

  • 변수: ① 입력받은 비밀번호(문자), ② O/X 판단용 변수 (일단 안 된다는 조건으로 설정해 둠)
  • 작업: ① 데이터 가져오기 ② 조건 확인
    • item 개수가 8자 이상인가? 숫자가 있나(0~9)? 문자가 있나? 특수문자(!, #, @)가 있나? 대문자가 1개 있나?
    • 만족하면(=정상 비번) 사용(OK), 아니면 새로 만들기(규칙 위배)
  • 처음 구조(중첩 if): 8자 이상 -> 숫자/문자/특수문자 모두 있나 -> 대문자 1개 이상 -> 비밀번호 생성, 각 else에서 사유 안내
  • 노트 메모: 중간에 조건을 만족 못 하면 else로 검증되지 않은 것이 있을 수 있음. 2-2, 2-3, 2-4를 "숫자, 문자, 특수문자" 분류로 나눠서 확인

각 자리 가져오기

  • for i in 비밀번호 (문자를 하나씩) 또는 for i in range(len(비밀번호)) (몇 자리인지 알 수 있음)
  • 분류: 숫자 / 문자 / 특수문자 / 그 외(재입력)
  • 확인 순서: ① 각 항목 개수 > 0 ② 총 항목 >= 8 ③ 문자 항목에서 대문자 확인 ④ 모두 만족하면 OK, 아니면 X
  • 처음에는 변수 숫자모음 [], 문자모음 [], 특수문자모음 []을 만들었으나 "모음으로 묶는데 굳이 필요가 없어진다 -> 개수만 필요하네?"라고 정리
  • if k in ["!", "#", "@"]: k가 목록 안에 있는지 True/False로 알려줌
  • 노트 문제: 조건을 주어주고 비밀번호를 만들 수 있을까? (숙제 "해와~")
def check_password(pw):
    digits = letters = specials = upper = 0
    for k in pw:
        if k.isdigit():
            digits += 1
        elif k.isalpha():
            letters += 1
            if k.isupper():
                upper += 1
        elif k in ["!", "#", "@"]:
            specials += 1
        else:
            return False, "허용하지 않는 문자가 있습니다"   # 그 외 -> 재입력
    if len(pw) < 8:
        return False, "8자 이상이 아닙니다"
    if digits == 0 or letters == 0 or specials == 0:
        return False, "숫자, 문자, 특수문자를 모두 포함해야 합니다"
    if upper == 0:
        return False, "대문자가 없습니다"
    return True, "사용 가능한 비밀번호입니다"

for pw in ["abc", "abcdefg1!", "Abcdefg1!", "Abcdefg1$"]:
    print(pw, check_password(pw))
  • 보충: 노트처럼 문자/숫자 목록 대신 str.isdigit(), isalpha(), isupper()를 쓰면 k in [...] 비교를 줄일 수 있음. 특수문자는 허용 목록(!, #, @)만 확인
  • 사용 라이브러리: 없음 (내장 문자열 메서드)

4. 소수 판별

  • 소수: 1과 자기 자신으로만 나누어지는 수. 입력은 자연수(음수, 0 제외)이고 판단 결과는 True/False
  • 변수 2개: 입력된 수 num(노트에서 n), 결과를 알려줄 변수. 기능: 소수 판별(나머지 % 연산으로 0이 아닌지 판단)
  • 순서
    1. n >= 2 판단
    2. 1을 만족하면 2 ~ (n-1)까지 정수를 만들어 변수 i에 하나씩 가져옴
    3. n % i == 0인지 확인 -> 나눠지면 소수가 아님
    4. 나머지는 코드 종료, 2-2 ~ 2-4를 n-1까지 반복(for문)
    5. 끝까지 나눠지지 않으면 소수
  • if 안에 for, for 안에 if가 들어가는 구조 (나머지가 0인지 판단이 필요하므로)
  • if만 쓰면 / if-elif: "별도 처리하고 싶다", if-elif-...-else: "모든 데이터를 처리하고 싶다"
  • for 변수 in 반복할 수 있는 객체: 명령문. 반복할 대상이 뭔지 고민 후 for ... in 선택. 변수 설정: 도움 받을 수 있는 게 있으면 변수로 설정, 횟수를 count할지 enumerate/range로 접근
  • 노트 변수 예: 반환 = None -> 소수이면 True, 아니면 False로 바꾸는 flag 방식
def is_prime(n):
    if n >= 2:
        for i in range(2, n):        # 2 ~ n-1
            if n % i == 0:
                return False         # 나눠지면 소수가 아님
        return True                  # 끝까지 안 나눠지면 소수
    else:
        return False                 # 2 미만은 소수가 아님

print([n for n in range(1, 30) if is_prime(n)])
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
  • 노트의 range(2, N-1, 1)은 "n-1까지"라는 뜻으로 적었지만 range의 끝은 포함하지 않으므로 range(2, n)이 2 ~ n-1
  • 보충: range(2, int(n ** 0.5) + 1)까지만 확인해도 결과는 같고 훨씬 빠름
  • [판독 불확실]: 노트 하단의 반환 == None 비교 부분은 flag 변수 방식으로 이해했고, 위 코드는 return을 쓴 같은 동작의 버전

5. 볼링 점수 계산기

순서

  1. 문제 파악 (점수 계산 방법)
  2. 처리과정 작성
  3. 함수 정의 (매개변수, 반환값, 함수 기능). 가능하다면 class 작성
  4. 구현
  5. Flet: 볼링 점수 구현, 테스트 검증용으로 구분하기 (설계 -> 실제 반영)
  • 내일(4/23)까지 볼링 게임 완성 / Flet으로 만들고 GitHub에 반영까지
  • 추가로 CV에서 배운 것(흑백 전환 버튼, 이미지 사이즈 변환, 버튼 -> 컬러 변환 등) 만들어 보기

규칙 정리

  • 1 게임 = 10 프레임. 한 프레임에 A, B 두 번 투구 (파울 0, 거터 0, 미스 0)
  • 스트라이크(X, 첫 투구 10점): 10점 + 다음 2번의 투구 점수 (노트 예: 10 + 10 + 9 = 29)
  • 스페어(/, A+B = 10): 10점 + 다음 1번의 투구 점수
  • 스페어/스트라이크가 없으면 A + B (A + B < 10)
  • 마지막(10) 프레임: 스트라이크나 스페어이면 기회 3번, 아니면 2번
  • 스트라이크이면 B = 0으로 고정하고 다음 프레임으로 이동
  • 필요 변수: ① 직전 프레임 점수 ② 현재 프레임 점수 A, B ③ 다음 프레임 점수 C ④ 현재 프레임 최종 점수
    • 경우 1: 스페어X, 스트라이크X -> 직전 + (A + B)
    • 경우 2: 스페어 -> 직전 + (A + B + C)
    • 경우 3: 스트라이크 -> 연속 스트라이크이면 그다음 프레임 A와 총점까지 필요
  • 자료구조 아이디어: key: frame, value: A, B, C
  • 노트의 기존 표(사용자별 9/, 5/ 칸에 15, 25 누적)처럼 "계산 완료 / 진행 중"을 구분해서 표시

구현 (노트 규칙을 투구 목록으로 계산)

def frame_scores(rolls):
    """투구 목록 -> 프레임별 누적 점수 (보너스 투구가 아직 없으면 계산하지 않음)"""
    scores = []
    total = 0
    i = 0
    for _ in range(10):
        if i >= len(rolls):
            break
        if rolls[i] == 10:                        # 스트라이크
            if i + 2 >= len(rolls):
                break
            total += 10 + rolls[i + 1] + rolls[i + 2]
            i += 1
        else:
            if i + 1 >= len(rolls):
                break
            if rolls[i] + rolls[i + 1] == 10:     # 스페어
                if i + 2 >= len(rolls):
                    break
                total += 10 + rolls[i + 2]
            else:                                 # 일반
                total += rolls[i] + rolls[i + 1]
            i += 2
        scores.append(total)
    return scores

# key: frame, value: 투구 점수 (노트의 구조)
frames = {1: [10], 2: [10], 3: [9, 1], 4: [8]}
rolls = [x for v in frames.values() for x in v]
print(frame_scores(rolls))                 # [29, 49, 67]  (노트 예: 29, 49, ...)

assert frame_scores([10] * 12)[-1] == 300           # 퍼펙트 게임
assert frame_scores([9, 0] * 10)[-1] == 90          # 모두 9-0
assert frame_scores([5] * 21)[-1] == 150            # 모두 스페어(5/5)
print("OK")
  • 보충: 스트라이크 프레임은 투구가 1번이라 value의 길이가 다름. 위처럼 투구를 한 줄로 펴서(rolls) 계산하면 A, B, C 구분 없이 처리할 수 있음
  • 사용 라이브러리: 없음 (Flet 화면은 아직 노트에 설계만 있음)