[Algorithm] Week 3. 구현

알고리즘 스터디 코드와 규칙 정리:

https://github.com/5jisoo/Algorithm-Study

GitHub - 5jisoo/Algorithm-Study: [2023 Winter ~ ] Algorithm Study ✏️ 알고리즘 스터디를 위한 저장소입니다.

 

교재: 이것이 취업을 위한 코딩 테스트다 with 파이썬

 

---

구현

피지컬로 승부하기

구현 = 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

• 생각해낸 풀이과정을 파이썬으로 정확히 구현해내야함.

 

• 유형
  • 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
  • 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

---

리스트 크기

int 자료형 데이터의 개수에 따른 메모리 사용량

데이터의 개수(리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
1,000,000	약 40MB

• 데이터 처리량이 많을 때, 메모리 제한을 고려하자
  • 하지만 애초에 대회 문제가 아니라면 복잡한 최적화를 요구하지는 않음.

 

---

채점 환경

자신의 코드가 1초에 2000만번의 연산을 수행한다고 가정하고 문제를 풀자!

• ex) 시간제한 = 1초, 데이터의 개수 = 100만개? O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 함.

 

시간 제한과 데이터의 개수를 먼저 확인 -> 시간 복잡도를 예측하기

 

---

구현 문제에 접근하기

	구현 난이도	프로그램 실행 시간
파이썬	쉬운 편	긴 편
PyPy	쉬운 편	다소 짧은 편

 

• Pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 실행 속도가 더 빠르다.
  • 반복문이 많을수록 파이썬과의 속도 차이가 더 심함.
• Pypy3를 코딩 테스트 환경이 지원한다면 이를 이용하자!

 

---

교재 예제 정리

문자열 압축

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

 

내가 생각해내지 못한점

• 알고리즘은 금방 구현했으나, 리스트 슬라이싱에서는 인덱스 범위를 벗어나도 괜찮다는 점을 놓침.
  • 인덱스 범위에 해당하는 부분만 잘라줌. 빈 리스트를 반환한다!

 

• ex) 리스트의 길이가 5일때

a = [1, 2, 3, 4, 5]
print(a[5])	# error!

 

• ex) 위와 같은 경우, 리스트 슬라이싱을 사용할 때:: 범위에 해당하는 원소들만 포함됨. 오류 없음.

a = [1, 2, 3, 4, 5]
print(a[3:8])

 

---

제출한 코드

위의 사실을 알았다면 현재 상태를 체크하는 문자열을 보다 쉽게 리스트 슬라이싱으로 작성할 수 있었다.

 

def solution(s):
    answer = len(s)
    for length in range(1, len(s) // 2 + 1):  # length
        result = ""
        prev = s[0:length]
        cnt = 1
        for j in range(length, len(s), length):
            if prev == s[j:j + length]:
                cnt += 1
            else:
                if cnt > 1:
                    result += str(cnt)
                result += prev
                prev = s[j:j + length]
                cnt = 1
        if cnt > 1:
            result += str(cnt)
        result += prev
        if len(result) < answer:
            answer = len(result)
    return answer

 

• 내가 놓쳤던 부분: 14번째 줄 

prev = s[j:j + length]

• 14번째 줄
  • 마지막 loop에서 prev가 나머지 문자열들을 저장함!!

 

---

자물쇠와 열쇠

 

문제 링크:

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

프로그래머스

 

내가 생각 해낸 것.

• 열쇠를 90도로 4번 회전
• 열쇠를 이동시키면서 자물쇠에 원소를 각각 더하여 1 이 아닌 부분이 있다면 False, 전부 1이라면 True

 

내가 생각해내지 못한 것

• 자물쇠 배열에서 열쇠를 용이하게 이동시키는 방법
  • 자물쇠 배열의 원래 길이보다 위, 아래로 3배씩 늘린 배열에서 열쇠를 이동시키면 편함

풀이과정 그림

 

풀이과정

• lock을 3배로 늘린 new_lock이라는 배열을 새로 만들어줌.
• key는 총 4번 90도 회전.
• key를 이 new_lock이라는 배열에서 이동시킴.
• 이동 후 각 key의 원소를 new_lock에 더함.
• 실제 lock의 위치를 확인하여 lock의 모든 원소가 1이면 True를 반환함.

 

 

제출한 코드

def rotate(a):  # key 회전 함수
    n = len(a)
    m = len(a[0])
    new_key = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            new_key[j][n - i - 1] = a[i][j]
    return new_key


def check(new_lock):  # new_lock배열에서 lock이 있는 위치 확인하기
    length = len(new_lock) // 3
    for i in range(length, length * 2):
        for j in range(length, length * 2):
            if new_lock[i][j] != 1:
                return False
    return True


def solution(key, lock):
    n = len(lock)
    m = len(key)
    new_lock = [[0] * (n * 3) for _ in range(n * 3)]

    for i in range(n):
        for j in range(n):
            new_lock[i + n][j + n] = lock[i][j]

    for _ in range(4):  # 총 4번 회전
        key = rotate(key)
        for x in range(n * 2):  # key 이동
            for y in range(n * 2):
                for i in range(m):  # key의 원소들을 new_lock에 더해주기
                    for j in range(m):
                        new_lock[x + i][y + j] += key[i][j]
                if check(new_lock):  # new_lock의 lock부분 원소 체크
                    return True
                for i in range(m):  # 더했던 key를 다시 빼줌
                    for j in range(m):
                        new_lock[x + i][y + j] -= key[i][j]
    return False


# test
print(solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]], [[1, 1, 1], [1, 1, 0], [1, 0, 1]]))

 

---

치킨 배달

문제 링크:

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

15686번: 치킨 배달

 

내가 몰랐던 점

• 조합해서 나오는 경우를 모두 파악하기 위한 itertools 라이브러리 임포트하기
  • 구글링으로 라이브러리를 찾아서 풀었음. >> 라이브러리 사용법을 정리 필요

 

---

보완

itertools 라이브러리 사용법 정리:

https://5ji-record.tistory.com/159

[Python] itertools 라이브러리

 

---

외벽 점검

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스

 

내가 한번에 파악해내지 못한 점과 깨달은 점

• 구현에서 가장 중요한 것은 시간복잡도와 효율성을 따지는 알고리즘보단 어떻게 문제를 풀어나가야 하는지, 연산과정이 많아도 고려해야 하는 경우의 수를 전부 돌리더라도 말그대로 구현을 해내는 것이 우선임을 깨달아야 했던 문제였다.
• '제한 조건'에서 주어진 dist의 길이(친구 수)가 굉장히 짧았고(8), 이는 순열의 개수를 계산해봐도 8! = 40,320으로 2000만번의 한도 내에 충분히 계산 가능하다.
  • 이 점을 이용하여 완전탐색의 해법으로 갔어야 하는 것이다.
• 추가적인 문제는 원형이라는 점이다. (위에서의 자물쇠와 키 문제와 비슷하다.) 원형으로 나열된 데이터는 데이터의 길이를 2배로 널려서 선형적으로 만들어주면 유리하다는 점이다.
  • 각각의 weak[] 배열의 원소에 n을 더한 값을 뒤에 추가해줌. => 그럼 원형을 도는 것과 동일해짐.

 

 

아이디어

position = weak[start] + friends[count - 1] # 해당 친구가 점검할 수 있는 마지막 위치

• 나는 해당 친구가 점검할 수 있는 점검시작점에서부터의 거리를 나타내는 position이라는 변수를 생각해내지 못했다. 
• 항상 데이터 리스트를 비교, 확인할 때 새로운 변수를 갱신하면서 확인하는 점이 없을까에 대한 고민이 필요하다.

 

 

제출한 코드

from itertools import permutations


def solution(n, weak, dist):
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)

    answer = len(dist) + 1  # 초기화
    for start in range(length):  # 스타트 지점
        for friends in list(permutations(dist, len(dist))):  # 내보낼 친구의 순서 - 순열 사용
            count = 1  # 투입할 친구의 수
            position = weak[start] + friends[count - 1]  # 해당 친구가 점검할 수 있는 마지막 위치
            for index in range(start, start + length):  # 각각의 취약점
                if position < weak[index]:  # 점검할 수 있는 위치 벗어남
                    count += 1  # 새로운 친구 투입
                    if count > len(dist):  # 투입 불가 종료
                        break
                    position = weak[index] + friends[count - 1]
            answer = min(answer, count)
    if answer > len(dist):
        return -1
    return answer
    answer = 0


# test
print(solution(12, [1, 5, 6, 10], [1, 2, 3, 4]))
print(solution(12, [1, 3, 4, 9, 10], [3, 5, 7]))