[코딩테스트 이론] 배열

※ 코딩테스트 합격자 되기 - 파이썬 편 (골든 래빗) 교재 참조

배열

: 인덱스와 값을 일대일 대응해 관리하는 자료구조

• 배열 선언
  1. 일반적인 방법
     arr = [0, 0, 0], arr = [0]*6
  2. 리스트 생성자 사용방법
     `arr = list(range(6)) # [0,1,2,3,4,5]
  3. 리스트 컴프리헨션 활용
     arr = [0 for _ in range(6)]
• 차원
  • 1차원 배열 : 가장 간단한 리스트 배열 방법
    `arr = [1,2,3,4]
  • 2차원 배열 : 1차원 배열 확장
    arr = [[1,2],[3,4]]
  • 1,2차원 이상의 여러가지 차원도 있음

배열 기법

: 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근 할 수 있음
시간 복잡도 O(1)

• 자주 활용하는 리스트 기법
  1. 데이터 추가
     • 리스트.append(값)
     • 리스트.insert(원하는 인덱스 위치, 값)
  2. 데이터 삭제
     • 리스트.pop(원하는 인덱스 위치) : 삭제한 데이터의 값을 반환
     • 리스트.remove(삭제 값) : 특정 데이터 자체를 삭제
• 참고

1. len() : 리스트 전체 데이터 개수 반환
2. index() : 특정 데이터가 처음 등장한 인덱스를 반환 , 없으면 -1반환
3. sort() : 사용자가 정한 기준에 따라 리스트 데이터를 정렬, 원본 자체 데이터를 바꿈
4. count() : 특정 데이터 개수 반환

---

문제1 

[행렬 곱셈]

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

프로그래머스

 

** 나의 풀이법 (시간복잡도 O(N^3))

1) 길이 지정 후, answer 이라는 0 배열 만들기

2) arr1와 arr2 곱하기 위한 반복문 수행

def solution(arr1, arr2):
    a1 = len(arr1)
    a2 = len(arr1[0])
    b2 = len(arr2[0])
    answer = [[0]*b2 for _ in range(a1)]
    
    for i in range(a1):
        for j in range(b2):
            sm = 0
            for k in range(a2):
                sm += arr1[i][k]*arr2[k][j]
            answer[i][j] = sm
    
    return answer

 

문제2

[행렬 곱셈]

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

프로그래머스

 

**나의 풀이법

1) 좌표 시작 위치 재 선정 -> 0,0에서 5, 5로 가정하고 아래, 오른쪽에 0인 배열으로 패딩했다고 가정

2) 중복되는 방향을 제거 해야함으로 set을 통해 add

   - 이때, 방향 (이전 위치, 이후 위치) 모두 넣어야함!

3) 갯수세기/2

def solution(dirs):
    ans = set()
    dr = {'U': (-1, 0), 'D': (1, 0), 'R': (0, 1), 'L': (0, -1)}
    i, j = 5, 5
    
    for d in dirs:
        ni, nj = i + dr[d][0], j + dr[d][1]
        if 0 <= ni < 11 and 0 <= nj < 11:
            ans.add((i,j, ni,nj))
            ans.add((ni, nj, i, j))
            i, j = ni, nj
    return len(set(ans))/2