[0, 0, 0, 0, 0, 0]5. 배열
코딩 테스트 합격자 되기 - 파이썬 편 책 정리 내용입니다.
05-1 배열 개념
배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조
데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있다. =임의접근(random access)
배열 선언
일반적인 방법
리스트 생성자를 사용하는 방법
리스트 컴프리헨션을 활용하는 방법
엄밀히 말하면 배열과 리스트는 다른 개념이다. 다만 파이썬은 배열을 지원하는 문법은 없고 대신 리스트라는 문법을 지원.
파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현되어 있다.
다른 언어의 배열 기능을 그대로 사용할 수 있으면서 배열 크기도 가변적이므로 코딩 테스트에서 고려할 사항을 조금 더 줄여준다.
슬라이싱, 삽입, 삭제, 연결 등의 연산을 제공하므로 더 편리
배열과 차원
배열은 2차원 배열, 3차원 배열과 같이 다차원 배열을 사용할 때도 많다. 하지만 컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장한다.
다시 말해 배열은 차원과는 무관하게 메모리에 연속 할당된다.
1차원 배열
1차원 배열의 모습은 메모리에 할당된 실제 배열의 모습과 같다.
배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연이어 할당된다.
2차원 배열
1차원 배열의 확장
다음과 같이 선언할 수 있다.
# 2차원 배열을 리스트로 표현
arr = [[1,2,3,4], [5,6,7,8], [9,10,11,12]]
# arr[2][3]에 저장된 값을 출력
print(arr[2][3])12- 리스트 컴프리헨션의 활용
[[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]- 2차원 배열 데이터에 접근하는 방법은 1차원 배열과 비슷. 행과 열을 명시해 []연산자를 2개 연이어 사용한다는 점만 다르다.
2차원 배열도 실제로는 1차원 공간에 저장이 된다.
1 2 3 4 5 6 가 아닌
1 2 3 4 5 6
05-2 배열의 효율성
배열 연산의 시간 복잡도
배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한번에 접근할 수 있다.
따라서 시간 복잡도는 O(1)
맨 뒤에 삽입할 경우
맨 뒤에 삽입할 때는 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않는다.
따라서 시간 복잡도는 O(1)
맨 앞에 삽입할 경우
맨 앞에 삽입할 경우 기존 데이터들을 뒤로 한 칸씩 밀어야 한다.
따라서 데이터 개수를 N개로 일반화하면 시간 복잡도는 O(N)
중간에 삽입할 경우
중간에 삽입할 경우 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 해야한다.
미는 데이터 개수가 N개라면 시간 복잡도는 O(N)
- 알 수 있는 점
- 배열은 특정한 경우에 데이터 추가나 삭제에 드는 비용이 많다.
배열을 선택할 때 고려할 점
데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있다.
But, 메모리 공간을 충분히 확보해야 하는 단점
즉 빈번하게 접근하는 경우 효율적이지만 메모리 낭비가 발생할 수 있다. 이에 따라 다음 2가지 사항을 고려
할당할 수 있는 메모리 크기를 확인해야 한다.
- 보통 정수형 1차원 배열은 1000만 개, 2차원 배열은 3000*3000 크기를 최대로 생각한다.
중간에 데이터 삽입이 많은지 확인해야 한다.
- 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있다.
※ 파이썬의 리스트는 동적으로 크기가 조절된다. 즉 구현 시 배열 크기에 대한 고민은 하지 않는다. 공부하는 정도로만 기억!
05-3 자주 활용하는 리스트 기법
- 파이썬에서 배열 자료구조가 필요한 때는 앞서 언급했듯 리스트를 활용
리스트에 데이터 추가
append() 메서드로 데이터 추가
- 맨 끝에 데이터를 추가
+ 연산자로 데이터 추가
- 리스트의 맨 끝에 다른 리스트의 데이터를 추가
insert() 메서드로 데이터 삽입
특정 위치에 데이터를 삽입
첫 번째 인수에 데이터를 삽입할 위치를 받고, 두 번째 인수에 삽입할 데이터를 받는다.
lst.insert(index, data)지정한 위치에 데이터를 삽입하고 뒤쪽 데이터를 하나씩 뒤로 이동
리스트에서 데이터 삭제
pop() 메서드로 특정 위치의 데이터 팝
- pop 할 데이터의 인덱스를 인수로 받아 삭제하고 삭제한 데이터의 값을 반환
remove() 메서드로 특정 데이터 삭제
pop() 메서드와 다르게 특정 위치가 아닌 특정 데이터 자체를 삭제하는 함수.
인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제
- 첫 번째 2만 삭제되고 그 다음 2는 남아있는 모습
리스트 컴프리헨션으로 데이터에 특정 연산 적용
리스트에 제곱 연산 적용 예
주목해야 하는 점은 numbers 리스트의 값 변화 유무이다. numbers값 자체는 [1, 2, 3, 4, 5]로 이전과 비교해서 바뀌지 않았다.
이처럼 리스트 컴프리헨션은 연산이 끝난 리스트를 반환할 뿐이지 연산 대상 리스트를 바꾸지 않는다.
리스트 연관 메서드
- 리스트의 전체 데이터 개수를 반환하는
len()함수
- 특정 데이터가 처음 등장한 인덱스를 반환하는
index()메서드, 없으면 -1 반환
- 사용자가 정한 기준에 따라 리스트를 정렬하는
sort()메서드
['apple', 'banana', 'cherry', 'apple', 'orange', 'banana', 'kiwi']['apple', 'apple', 'banana', 'banana', 'cherry', 'kiwi', 'orange']['orange', 'kiwi', 'cherry', 'banana', 'banana', 'apple', 'apple']- 특정 데이터 개수를 반환하는
count()메서드
05-4 몸풀기 문제
문제 01. 배열 정렬하기
- 정수 배열을 정렬해서 반환하는 solution() 함수를 완성하세요.
권장 시간 복잡도 O(NlogN) ← 이건 시험에서는 안알려준다.
제약 조건
정수 배열의 길이는 2이상 \(10^5\) 이하
정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하
- 문제 분석
제약 조건을 주의 깊게 봐야한다.
제약 조건의 데이터 개수는 최대 \(10^5\) 이므로 제한 시간이 3초라면 \(O(N^2)\) 알고리즘은 사용할 수 없다.
만약 정수 배열의 최대 길이가 10이라면 사용해도 된다. 이렇게 제약 조건에 따라 같은 문제도 난이도가 달라질 수 있다.
sort()의 시간복잡도는 O(NlogN), 여기서 N은 arr의 길이이므로 최종 시간 복잡도는 O(NlogN)
문제 02. 배열 제어하기
- 정수 배열을 하나 받아 배열의 중복값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 solution() 함수를 구현
권장 시간 복잡도 O(NlogN) ← 이건 시험에서는 안알려준다.
제약 조건
배열 길이는 2이상 1,000 이하
각 배열의 데이터 값은 -100,000 이상 100,000 이하이다.
집합은 중복값을 허용하지 않으므로 문제에서 요구하는 중복 문제를 한 번에 해결할 수 있다. (해쉬 알고리즘 사용, 시간복잡도 O(N))
일일이 데이터를 확인해 중복값을 제거하는 알고리즘은 시간복잡도가 \(O(N^2)\) 으로 성능이 좋지 않다.
파이썬에는 코딩 테스트에 유용한 함수가 많다. 굳이 직접 작성하려 하지 마라
lst의 중복 원소를 제거하는 데 걸리는 시간복잡도는 O(N), 정렬 시간복잡도는 O(NlogN), 여기서 N은 lst의 길이이므로 최종 시간 복잡도는 O(NlogN)
05-5 합격자가 되는 모의 테스트
문제 03. 두 개 뽑아서 더하기
- 정수 배열 numbers가 주어졌을 때 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 solution() 함수를 완성하세요.
제약 조건:
numbers의 길이는 2 이상 100 이하
numbers의 모든 수는 0 이상 100 이하
입출력의 예
- input: [2, 1, 3, 4, 1] → output: [2, 3, 4, 5, 6, 7]
- 문제 분석하고 풀기
놓치기 쉬운 점: 중복값은 허용하지 않는다.
입출력 값에 대해서는 일부러라도 분석하는 시간을 반드시 갖기.
numbers의 최대 데이터 개수는 100이므로 시간 복잡도는 고려하지 않아도 된다.
내가 푼 풀이과정: 어짜피 i + i를 제외한 다른 원소의 합 들의 리스트를 구해야하므로 i + 맨 뒤 숫자부터 더하도록 구성하였다. (아래에 비해 코드가 직관적이지 않다.)
- for i in range(start, end) 에서 start를 이용하면 편하게 할 수 있었는데 놓쳤다.
- 시간 복잡도 분석
2중 반복문을 통해 모든 원소들에 대해 두 수의 합을 구하는 연산의 시간복잡도 \(O(N^2)\)
이를 set으로 만들 때 시간복잡도 \(O(N^2)\) (원래 set의 시간복잡도는 O(N)인데 데이터 갯수가 \(N^2\) 이므로)
\(N^2\) 개의 데이터를 정렬하는데 \(O(N^2\text{log}N^2)\)
- 최종적으로 시간 복잡도는 \(O(N^2\text{log}N^2)\)
문제 04. 모의고사
- 수포자는 수학을 포기한 사람을 줄인 표현입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.
1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, \(\quad\) 1, 2, 3, 4, 5, …
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, \(\quad\) 2, 1, 2, 3, 2, 4, 2, 5, …
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, \(\quad\) 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, …
1번 문제부터 마지막 문제까지의 정답이 순서대로 저장된 배열 answers가 주어졌을 때 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 반환하도록 solution() 함수를 작성
제약 조건
시험은 최대 10,000 문제로 구성
문제의 정답은 1, 2, 3, 4, 5 중 하나
가장 높은 점수를 받은 사람이 여럿이라면 반환하는 값을 오름차순으로 정렬
입출력의 예
input: [1,2,3,4,5] output: [1]
input: [1,3,2,4,2] output: [1,2,3]
# 내가 푼 풀이
import math
def solution(answer):
one = [1, 2, 3, 4, 5] # 5
two = [2, 1, 2, 3, 2, 4, 2, 5] # 8
three = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] # 10
one_freq = 0
two_freq = 0
three_freq = 0
for i in range(len(answer)):
one_index = i % len(one) # 0 1 2 3 4 0 1 2 3 4 ...
if answer[i] == one[one_index]:
one_freq += 1
two_index = i % len(two)
if answer[i] == two[two_index]:
two_freq += 1
three_index = i % len(three)
if answer[i] == three[three_index]:
three_freq += 1
scores = []
max_score = max(one_freq, two_freq, three_freq)
if max_score == one_freq:
scores.append(1)
if max_score == two_freq:
scores.append(2)
if max_score == three_freq:
scores.append(3)
return scores내가 푼 풀이과정: 각각의 패턴을 반복하며 하나씩 answer과 비교, 값이 동일하면 +1씩 계속 해준다. 이후 max값을 가진 학생을 찾아 scores 리스트에 넣는다.
# 정답 풀이
def solution(answers):
# 1. 수포자들의 패턴
patterns = [
[1,2,3,4,5],
[2,1,2,3,2,4,2,5],
[3,3,1,1,2,2,4,4,5,5]
]
# 2. 수포자들의 점수를 저장할 리스트
scores = [0]*3
# 3. 각 수포자의 패턴과 정답이 얼마나 일치하는지 확인
for i, answer in enumerate(answers):
for j, pattern in enumerate(patterns):
if answer == pattern[i % len(pattern)]:
scores[j] += 1
# 4. 가장 높은 점수 저장
max_scores = max(scores)
# 5. 가장 높은 점수를 가진 수포자들의 번호를 찾아서 리스트에 담음
highest_scores = []
for i, score in enumerate(scores):
if score == max_scores:
highest_scores.append(i+1)
return highest_scores- enumerate 적극적으로 사용해보자
- 시간 복잡도 분석
N은 answers의 길이
수포자들의 패턴과 정답을 비교하는 부분은 O(N)
scores를 순회하면서 가장 높은 점수를 받은 수포자를 추가하는 연산은 O(1)
따라서 최종 시간 복잡도는 O(N)
문제 05. 행렬의 곱셈
- 2차원 행렬 arr1과 arr2를 입력받아 arr1에 arr2를 곱한 결과를 반환하는 solution() 함수를 완성하세요.
제약 조건
행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하이다.
행렬 arr1, arr2의 데이터는 -10 이상 20 이하인 자연수이다.
곱할 수 있는 배열만 주어진다.
입출력의 예
arr1: [[1,4], [3,2], [4,1]], arr2: [[3,3], [3,3]]
return: [[15,15], [15,15], [15,15]]
arr1: [[2,3,2], [4,2,4], [3,1,4]], arr2: [[5,4,3], [2,4,1], [3,1,1]]
return: [[22,22,11], [36,28,18], [29,20,14]]
[[22, 22, 11], [36, 28, 18], [29, 20, 14]]# 정답 풀이
def solution(arr1, arr2):
# 1. 행렬 arr1과 arr2의 행과 열의 수
r1, c1 = len(arr1), len(arr1[0])
r2, c2 = len(arr2), len(arr2[0])
# 2. 결과를 저장할 2차원 리스트 초기화
ret = [[0]*c2 for _ in range(r1)]
# 3. 첫 번째 행렬 arr1의 각 행과 두 번째 행렬 arr2의 각 열에 대해
for i in range(r1):
for j in range(c2):
# 4. 두 행렬의 데이터를 곱해 결과 리스트에 더해줌
for k in range(c1):
ret[i][j] += arr1[i][k] * arr2[k][j]
return ret[[22, 22, 11], [36, 28, 18], [29, 20, 14]]- 시간 복잡도 분석
N은 행 혹은 열의 길이. arr1의 행과 열의 수를 r1, c1라 하고 arr2의 행과 열의 수를 r2, c2라 했을 때 r1*c1*c2 만큼 연산한다.
각 값을 N으로 봤을 때 최종 시간 복잡도는 \(O(N^3)\) 이다.
문제 06. 실패율
- 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌습니다. 그녀가 만든 오천성이 대성공을 거뒀지만 최근 신규 사용자 수가 급감했기 때문입니다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였습니다. 이 문제를 어떻게 할까 고민한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했습니다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만 실패율을 구하는 부분에서 위기에 빠지고 말았습니다. 오렐리를 위해 실패율을 구하는 코드를 완성하세요.
- 실패율 정의: 스테이지에 도달했으나 아직 클리어하지 못한 플레이어 수 / 스테이지에 도달한 플레이어 수
전체 스테이지 개수가 N, 게임을 이용하는 사용자가 현재 멈춰 있는 스테이지의 번호가 담긴 배열 stages가 주어질 때 실패율이 높은 스테이지부터 내림차순으로 스테이지 번호가 담겨 있는 배열을 반환하도록 solution() 함수를 완성하세요.
제약 조건
스테이지 개수 N은 1이상 500 이하의 자연수이다.
stages의 길이는 1이상 200,000 이하이다.
stages에는 1 이상 N+1 이하의 자연수가 있다.
각 자연수는 사용자가 현재 도전 중인 스테이지 번호를 나타낸다.
단, N+1은 마지막 스테이지, 즉 N까지 클리어한 사용자를 나타낸다.
만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오면 된다.
스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다.
입출력의 예
N = 5, stages = [2, 1, 2, 6, 2, 4, 3, 3]
result = [3, 4, 2, 1, 5]
첫 번째 입출력 예를 보면 1번 스테이지에는 총 8명의 사용자가 도전했으며 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.
- 1번 스테이지 실패율: 1/8
2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.
- 2번 스테이지 실패율: 3/7
마찬가지로 나머지 스테이지의 실패율은 다음과 같다.
3번 스테이지 실패율: 2/4
4번 스테이지 실패율: 1/2
5번 스테이지 실패율: 0/1
각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.
- [3, 4, 2, 1, 5]
N = 4, stages = [4, 4, 4, 4, 4]
result = [4, 1, 2, 3]
두 번째 입출력 예를 보면 모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.
- [4, 1, 2, 3]
# 내 풀이 과정
# 1. 실패율은 (현재 스테이지 사용자 / 현재 스테이지와 같거나 큰 사용자)
# 2. 딕셔너리 2개 이용하자. {스테이지: 현재 도전자 수} / {스테이지: 지나간 도전자 수} // 나중에 (현재 도전자 / 현재도전자 + 지나간 도전자) 하면 될듯
# 3. 사용자는 20만(M), 스테이지는 500개(N)
# 실패율 측정 순열 탐색 20만 * 스테이지 갯수 500 << 으로 하려했으나 생각해보니 한번 갈 때 모든 스테이지 처리하면 될듯. 20만(O(M))
# 마지막에 sort 스테이지 갯수 O(NlogN)
# 최종 시간 복잡도: (M+NlogN)
def solution(N, stages):
cur = {i+1:0 for i in range(N+1)} # 최종 스테이지를 꺤 사람은 N+1 스테이지에 위치
next = {i+1:0 for i in range(N+1)}
for i in range(len(stages)): # 1부터 시작해야하므로 i+1 주의
for j in range(stages[i]): # 해당 사용자의 현재 스테이지
next[j+1] += 1 # 이미 넘어간 사람들 더해주고
cur[stages[i]] += 1 # 현재 스테이지인 사람 더해준다.
fail = {i+1:0 for i in range(N)} # 실패율
for i in range(N):
fail[i+1] = cur[i+1]/next[i+1] # {1:1/8, 2:3/7, ...}
return list(dict(sorted(fail.items(), key= (lambda item: item[1]), reverse=True)).keys())
# 딕셔너리의 value 기준으로 내림차순 sort 한 뒤 다시 딕셔너리로 만들고 key값만 뽑아서 다시 리스트화# 정답 풀이
def solution(N, stages):
# 1. 스테이지별 도전자 수를 구함
challenger = [0] * (N+2) # 0 인덱스를 하나 버린 셈 치고 + 최종스테이지를 깬 사람을 표시하기 위한 1개를 추가해서 N+2
for stage in stages:
challenger[stage] += 1
# 2. 스테이지별 실패한 사용자 수 계산
fails = {}
total = len(stages)
# 3. 각 스테이지를 순회하며, 실패율 계산
for i in range(1, N+1):
if challenger[i] == 0: # 4. 도전한 사람이 없는 경우, 실패율은 0
fails[i] = 0
else:
fails[i] = challenger[i] / total # 5. 실패율 구함
total -= challenger[i] # 6. 다음 스테이지 실패율을 구하기 위해 현재 스테이지의 인원을 뺌
# 7. 실패율이 높은 스테이지부터 내림차순으로 정렬
result = sorted(fails, key=lambda x: fails[x], reverse=True)
return result- 마지막 딕셔너리 값을 이용한 정렬 코드나 total에서 빼나가는 과정 아이디어 등 잘 봐두자.
- 시간 복잡도 분석하기
N은 스테이지의 개수이고, M은 stages의 길이이다. challenger 배열을 초기화하고, 각 스테이지 도전자 수를 계산할 때 시간 복잡도는 O(N+M)이다.
이후 스테이지 별로 실패율을 계산하는 데 필요한 시간 복잡도는 O(N)이고, 실패율을 기준으로 스테이지를 정렬할 때의 시간 복잡도는 O(NlogN)이다.
이 연산들을 모두 고려하면 시간 복잡도는 O(2*N + M + NlogN)이므로 최종 시간 복잡도는 O(M+NlogN)이다.
문제 07. 방문 길이
- 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다.
U: 위쪽으로 한 칸 가기
D: 아래쪽으로 한 칸 가기
R: 오른쪽으로 한 칸 가기
L: 왼쪽으로 한 칸 가기
캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 구성합니다.
우리는 게임 캐릭터가 지나간 길 중 캐리거가 처음 걸어본 길의 길이를 구하려고 합니다. 즉, 이미 거쳐간 길을 지나는 경우를 제외합니다.
그리고 좌표평면의 경계를 넘어가는 명령어는 무시합니다. 예를 들어 LULLLLLLU로 명령하면 1~6 명령어대로 움직이고 7~8 명령어는 무시합니다. 그리고 다시 9 명령어대로 움직입니다.
명령어가 매개변수 dirs로 주어질 때 게임 캐릭터가 처음 걸어본 길의 길이를 구해 반환하는 solution() 함수를 완성하세요.
제약 조건
dirs는 string형으로 주어지며 ‘U’, ‘D’, ‘R’, ‘L’ 이외의 문자는 주어지지 않는다.
dirs의 길이는 500 이하의 자연수이다.
입출력의 예
dirs: ULURRDLLU
answer: 7
dirs: LULLLLLLU
answer: 7
# 내가 푼 풀이 (실패)
def solution(dirs):
(x, y) = (0, 0)
arr = [[0]*11 for _ in range(11)] # index 0~10 / 0~10. 따라서 아래 좌표에 +5씩 해주어야함!
freq = 0
for i in range(len(dirs)):
if (dirs[i] == 'U') & (y < 5):
y += 1
if (dirs[i] == 'D') & (y > -5):
y -= 1
if (dirs[i] == 'R') & (x < 5):
x += 1
if (dirs[i] == 'L') & (x > -5):
x -= 1
if arr[y+5][x+5] == 1: # 이미 지나간 길이면 -1
arr[y+5][x+5] = -1 # 이미 -1로 된 곳을 지난다고 한번 더 빼지거나 하진 않음
freq -= 1
if arr[y+5][x+5] == 0: # 처음가는 길이면 1
arr[y+5][x+5] = 1
freq += 1
print(f"이동합니다. {dirs[i]}, 현 위치는 {(x,y)}, freq={freq}")
return(freq)실수한 점: 좌표 도달을 기준으로 삼았는데 어디서 왔는지도 중요했다..
이동합니다. U, 현 위치는 (0, 1), freq=1
이동합니다. L, 현 위치는 (-1, 1), freq=2
이동합니다. U, 현 위치는 (-1, 2), freq=3
이동합니다. R, 현 위치는 (0, 2), freq=4
이동합니다. R, 현 위치는 (1, 2), freq=5
이동합니다. D, 현 위치는 (1, 1), freq=6
이동합니다. L, 현 위치는 (0, 1), freq=5
이동합니다. L, 현 위치는 (-1, 1), freq=4
이동합니다. U, 현 위치는 (-1, 2), freq=33이동합니다. L, 현 위치는 (-1, 0), freq=1
이동합니다. U, 현 위치는 (-1, 1), freq=2
이동합니다. L, 현 위치는 (-2, 1), freq=3
이동합니다. L, 현 위치는 (-3, 1), freq=4
이동합니다. L, 현 위치는 (-4, 1), freq=5
이동합니다. L, 현 위치는 (-5, 1), freq=6
이동합니다. L, 현 위치는 (-5, 1), freq=5
이동합니다. L, 현 위치는 (-5, 1), freq=5
이동합니다. U, 현 위치는 (-5, 2), freq=66- 문제 분석하고 풀기
중복 경로는 최종 길이에 포함하지 않는다는 조건
- 중복을 포함하지 않는다는 문장이 나오면 set() 함수를 생각해보면 좋다.
음수 좌표를 포함한다는 점
- 원점을 (0, 0)에서 (5, 5)로 바꿔 음수 좌표 문제를 해결
구현 문제는 답안 코드의 길이가 긴 경우가 많으므로 기능별로 함수를 구현하는 게 좋다. 처음부터 기능별 구현이 잘 될 수는 없다. 그럴 때는 일단 하나의 함수로 전체 동작을 구현해보고 이후 함수로 나누는 연습을 하자
# 정답 풀이
def is_valid_move(nx, ny): # 1. 좌표평면을 벗어나는지 체크하는 함수. 좌표 문제에 단골로 등장!
return 0 <= nx < 11 and 0 <= ny < 11
def update_location(x, y, dir): # 2. 명령어를 통해 다음 좌표 결정.
if dir == 'U':
nx, ny = x, y+1
elif dir == 'D':
nx, ny = x, y-1
elif dir == 'L':
nx, ny = x-1, y
elif dir == 'R':
nx, ny = x+1, y
return nx, ny
def solution(dirs):
x, y = 5, 5
ans = set() # 3. 겹치는 좌표는 1개로 처리하기 위함
for dir in dirs: # 4. 주어진 명령어로 움직이면서 좌표 저장
nx, ny = update_location(x, y, dir)
if not is_valid_move(nx, ny): # 5. 벗어난 좌표는 인정하지 않음
continue
# 6. A에서 B로 간 경우 B에서 A도 추가해야 함(총 경로의 개수는 방향성이 없음)
# (x, y)에서 (nx, ny)까지의 경로를 방문했다고 기록하는 것을 의미한다.
ans.add((x, y, nx, ny))
ans.add((nx, ny, x, y))
x, y = nx, ny # 7. 좌표를 이동했으므로 업데이트
return int(len(ans)/2)- 시간 복잡도 분석하기
- N은 dirs의 길이이다. dirs의 길이만큼 순회하므로 시간 복잡도는 O(N)이다.
Summary
- 리마인드
파이썬에서는 리스트를 배열처럼 사용할 수 있다.
배열은 임의접근(random access)으로 배열의 모든 위치에 바로 접근할 수 있다.
중간에 데이터를 삽입할 일이 많다면 배열은 비효율적이다. 다른 방법을 생각해야 한다.
- 추천문제
문제 01: 배열의 평균값
문제 02: 배열 뒤집기
문제 03: \(n^2\) 배열 자르기
문제 04: 나누어 떨어지는 숫자 배열
추가 질문
기본 배열 질문
파이썬에서 리스트의 장점 및 단점에 대해 말해주세요. 단점이 있다면 이를 해결할 수 있는 방법은 무엇이 있을까요?
장점: 동적으로 크기가 조절된다, 슬라이싱, 삽입, 삭제, 연결 등의 연산을 제공한다.
단점: 삽입, 삭제, 인덱싱 등의 작업에서 최악의 경우 O(n)까지 시간이 걸릴 수 있다.
- 해결방안: 첫부분에 삭제나 삽입을 많이하는 작업의 경우 deque 같은 것을 고려할 수 있다.
일반적인 배열과 파이썬 리스트의 차이점은 무엇인가요?
- 일반적인 배열은 고정된 자료형 및 크기를 가진다. 파이썬의 리스트는 다양한 자료형을 혼합할 수 있고 동적이다.
정렬된 두 개의 리스트를 하나의 정렬된 리스트로 만드는 방법이 있을까요? 있다면 로직을 설명하시고 시간복잡도 측면에서도 설명해주세요.
- 둘 다 이미 정렬되있다는 점을 이용해 한 원소씩 비교하며 더 작은 값을 새로운 리스트에 추가하는 방식으로 하면 된다. 그럴 경우 A의 리스트길이가 N, B의 리스트 길이가 M이라 한다면 시간 복잡도는 O(N+M)이 된다.
정렬된 리스트와 정렬되지 않은 리스트에서 특정 원소를 탐색하는 방법에 대해 설명하고, 각 경우의 시간 복잡도에 대해 논해주세요.
정렬된 리스트의 경우 선형 탐색 / 이진 탐색 2가지 방법이 가능하다. 여기선 이진 탐색이 유리하다.
이진 탐색: 리스트의 중간 요소를 선택하여 찾고자 하는 요소와 비교
작으면 왼쪽의 중간, 크면 오른쪽의 중간에서 탐색을 계속한다.
이 과정을 반복한다.
시간 복잡도는 탐색 범위를 계속 절반으로 줄이기 때문에 O(logN) 이다.
정렬되지 않은 리스트의 경우 처음부터 탐색하는 선형 탐색 방법을 사용한다. 이 경우 시간 복잡도는 O(n)이다.
파이썬에서 문자열을 순회하면서, ‘abcde’에서 ’bcdea’, ’cdeab’처럼 앞뒤가 연결된 형태로 출력하려고 합니다. 리스트의 인덱스를 넘어설 때마다 이러한 순회를 효율적으로 구현하려면, 인덱스 계산을 어떻게 해야 할까요?
인덱스 번호를 i라고 하고, 문자열의 길이가 n이라고 하면 인덱스를 i % n 으로 설정하면 된다.
‘abcde’ 문자열이 있을 때, 0-1-2-3-4 가 지나고 5일 때 %5 를 해서 다시 0으로 돌아가는 방식이다.
코딩 문제
리스트의 합 문제
문제 설명: 주어진 정수 리스트에서 두 수의 합이 특정 목표 값이 되는 모든 쌍을 찾아라.
입력: 정수 리스트와 목표 정수
출력: 목표 값이 되는 모든 수 쌍 (중복 없이)
예시 (Python)
연속된 1의 최대 길이
문제 설명: 0과 1로 이루어진 리스트에서 가장 긴 연속된 1의 길이를 찾아라.
입력: 0과 1로만 이루어진 리스트
출력: 가장 긴 연속된 1의 길이
예시 (Python)
중복 요소 찾기
문제 설명: 정수 리스트에서 중복된 숫자를 모두 찾아라.
입력: 정수 리스트
출력: 중복된 숫자의 리스트
예시 (Python)
회전된 리스트의 회전 횟수 찾기
문제 설명: 주어진 리스트가 몇 번 회전되어 오름차순으로 정렬될 수 있는지 찾는 문제입니다. 원래 리스트는 오름차순으로 정렬된 상태에서 오른쪽으로 회전된 상태입니다.
입력: 정렬된 리스트가 오른쪽으로 회전된 상태의 리스트
출력: 리스트가 오름차순으로 정렬되기 위해 필요한 회전 횟수
예시 (Python)
- 문제분석
하나씩 뒤로 옮기는 작업은 시간이 많이 들 것.
여기서는 값이 커지다가 ‘작아지는’ 시점만 파악하면 될 것 같다.
회전은 오른쪽으로 되므로 (전체갯수 - 가장 큰 시점까지의 갯수)
2D 리스트의 나선형 출력
문제 설명: N x N 크기의 2D 리스트를 나선형(spiral) 순서로 출력하라.
입력: N x N 2D 리스트
출력: 나선형 순서로 배열된 요소들의 리스트
예시 (Python)
# 나중에 다시 풀자.
import math
N = int(math.sqrt(len(matrix)))
res = []
visit = [[0]*3 for _ in range(N)]
#[0 0 0]
#[0 0 0]
#[0 0 0]
global x
global y
(x, y) = (0, 0)
res.append(matrix[0][0])
visit[0][0] = 1
# 시작시 0,0 은 넣어주고 시작하자.
def move_right():
while x < N:
if visit[y][x+1] == 1:
break
else:
x += 1
visit[y][x] = 1
res.append(matrix[y][x])
def move_down():
while y < N:
if visit[y+1][x] == 1:
break
else:
y += 1
visit[y][x] = 1
res.append(matrix[y][x])
def move_left():
while N < 0:
if visit[y][x-1] == 1:
break
else:
x -= 1
visit[y][x] = 1
res.append(matrix[y][x])
def move_up():
while 0 < y:
if visit[y-1][x] == 1:
break
else:
y -= 1
visit[y][x] = 1
res.append(matrix[y][x])
while True:
move_right()
move_down()
move_left()
move_up()UnboundLocalError: local variable 'x' referenced before assignment리스트에서 모듈러 연산 문제
문제 설명: 주어진 리스트에서 각 요소를 k로 나눈 나머지를 계산하여 나머지가 같은 요소들이 몇 개 있는지 세어라.
입력: 정수 리스트와 나눌 수 k
출력: 나머지가 같은 요소들의 개수
예시 (Python)
슬라이딩 윈도우 최대합 문제
문제 설명: 길이가 N인 정수 리스트에서 연속된 K개의 요소로 이루어진 부분 리스트의 최대 합을 찾아라.
입력: 정수 리스트와 정수 K
출력: 연속된 K개의 요소의 최대 합
예시 (Python)
특정 좌표의 8방향 값 출력 문제
문제 설명: 주어진 2D 리스트에서 특정 좌표 (x, y)의 주변 8방향 값을 출력하라. 만약 범위를 벗어나는 경우, “벗어났다”라는 메시지를 출력해야 한다.
입력: N x M 2D 리스트, 좌표 (x, y)
출력: 특정 좌표의 8방향 값 또는 범위를 벗어난 경우 “벗어났다” 메시지 출력
예시 (Python)
N = len(matrix)
def is_valid(matrix, x, y):
if (x < 0) or (x > N):
return '벗어났다'
elif (y < 0) or (y > N):
return '벗어났다'
else:
return matrix[y][x]
def solution(matrix, x, y):
print(is_valid(matrix, x-1, y-1), end=' ');
print(is_valid(matrix, x, y-1), end=' ');
print(is_valid(matrix, x+1, y-1), end=' ');
print(is_valid(matrix, x-1, y), end=' ');
print(is_valid(matrix, x, y), end=' ');
print(is_valid(matrix, x+1, y), end=' ');
print(is_valid(matrix, x-1, y+1), end=' ');
print(is_valid(matrix, x, y+1), end=' ');
print(is_valid(matrix, x+1, y+1), end=' ');
solution(matrix, 1, 1)1 2 3 4 5 6 7 8 9 지뢰 찾기 의사코드 작성 문제
문제 설명: 지뢰 찾기 게임에서 지뢰의 위치가 주어졌을 때, 각 빈 칸이 주변에 몇 개의 지뢰가 있는지 계산하는 로직을 의사코드로 작성하라.
입력: N x M 크기의 2D 리스트, 지뢰의 위치가 표시된 리스트
출력: 각 빈 칸의 지뢰 개수를 계산한 결과 리스트
예시 (Pseudo-Code)
Input:
matrix = [
['M', '.', '.', 'M'],
['.', '.', '.', '.'],
['.', 'M', '.', '.']
]
Output:
[
['M', 1, 1, 'M'],
[2, 2, 2, 1],
[1, 'M', 1, 0]
]res = [[0]*col for _ in range(row)] # result를 저장할 매트릭스
def check_bomb(i, j): # i, j 주변에 지뢰가 몇 개 있는지, 해당 위치가 지뢰인지 판단하는 함수
for i in range(row):
for j in range(col):
res[i][j] = check_bomb(i, j)
print(res)# 틀림. 추후 수정..
matrix = [
['M', '.', '.', 'M'],
['.', '.', '.', '.'],
['.', 'M', '.', '.']
]
row = len(matrix) # 3
col = len(matrix[0]) # 4
res = [[0]*col for _ in range(row)] # result를 저장할 매트릭스
def is_valid(x, y):
if (x<0) or (x>col-1):
return 0
elif (y<0) or (y>row-1):
return 0
else:
return matrix[y][x] == 'M' # 이 값이 지뢰면 +1
def check_bomb(x, y): # i, j 주변에 지뢰가 몇 개 있는지, 해당 위치가 지뢰인지 판단하는 함수
if is_valid(x, y) == 1: # 중앙값이 지뢰면 'M' 반환
return 'M'
else:
check = is_valid(x-1, y-1) + is_valid(x, y-1) + is_valid(x+1, y-1);
+ is_valid(x-1, y) + is_valid(x+1, y);
+ is_valid(x-1, y+1) + is_valid(x, y+1) + is_valid(x+1, y+1);
return check
for y in range(row):
for x in range(col):
res[y][x] = check_bomb(x, y)
print(res)[['M', 0, 0, 'M'], [1, 1, 1, 1], [0, 'M', 0, 0]]