📍 2차원 배열의 선언
- 1차원 List를 묶어놓은 List
- 2이상의 다차원 List는 차원에 따라 Index를 선언
- 2차원 List의 선언 : 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함
- python 에서는 데이터 초기화를 통해 변수선언과 초기화가 가능함
[참고]
3
1 2 3
4 5 6
7 8 9
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]N = int(input())
arr = [list(map(int, input())) for _ in range(N)]배열 순회
n X m 배열의 n * m 개의 모든 원소를 빠짐없이 조사하는 방법
행 우선 순회
열 우선 순회
- 아래도 가능
arr = [[0] * 3 for _ in range(4)]
for i in range(3):
for j in range(4):
arr[j][i] += 1지그재그 순회
- 행이 짝수일 때 홀수일 때 경우가 다르다
i가 짝수면 j는 0에서 열의 길이 - 1
홀수면 j는 열의 길이 - 1에서 0으로 - i를 2로 나눴을 때 0이면(짝수 행) (m-1-2*j)가 날아간다
2로 나눴을 때 1이면(홀수 행) m-1-j 점점 반대쪽으로
델타를 이용한 2차 배열 탐색
- 2차 배열의 한 좌표에서 4방향의 인접 배열 요소를 탐색하는 방법
- 방향을 먼저 결정하고 이동하는 방법
- 가까운애 먼저 이동하는 방법
i 행이고 j 열에 접근 한 것
가운데 i를 기준으로 상하좌우에 계산한 좌표를 놓는다
i - 1 j - 1 / j / j + 1
i
i + 1
주변 4개의 칸이 더 큰가? > 주변 칸에 접근할 수 있어야 한다
di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]
N = 3
for i in range(N):
for j in range(N):
for k in range(4):
ni, nj = i + di[k], j + dj[k]
if 0<=ni<N and 0<=nj<N:
print(i, j, di, dj)
상하좌우로 쭉 뻗어나가는 경우
di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]
N = 3
p = 3
for i in range(N):
for j in range(N):
for k in range(4):
for l in range(1, p + 1):
ni, nj = i + di[k] * l, j + dj[k] * l
if 0<=ni<N and 0<=nj<N:
print(i, j, di, dj)
대각선도 가능
전치 행렬
- 대각선을 기준으로 자리를 맞바꾸는 것
- i 와 j 가 같으면 대각선에 있는 원소들이다
위쪽은 j가 i보다 크고 아래쪽은 i가 j보다 크다
📍 부분집합 합 문제
- 유한개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 갓이 0이 되는 경우가 있는지를 알아내는 문제
- 예를 들어 [-7, -3, -2, 5, 8] 이라는 집합이 있을 때, [-3, -2, 5]는 이 집합의 부분집합이면서 (-3) + (-2) + 5 = 0 이므로 이 경우의 답은 참이 된다
- 완전검색 기법으로 부분집합 합 문제 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야 한다
*완전탐색으로 가능한 경우(문제 시간이 여유로운 경우)
부분집합의 수
- 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2의 n제곱 개이다
- 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다
포함되거나, 포함되지 않거나로 2가지 경우 * 원소의 개수
각 원소가 부분집합에 포함되었는지를 loop를 이용해 확인하고, 부분집합을 생성하는 방법
1이 부분집합에 포함되지 않으면 0, 포함되면 1이라고 표시
어떤 부분집합에 대해 각 원소의 포함여부를 나타낼 수 있는 배열을 만들어서 사용
A = [1, 2, 3, 4]
bit = [0] * 4
for i in range(2):
bit[0] = i
for j in range(2):
bit[1] = j
for k in range(2):
bit[2] = k
for l in range(2):
bit[3] = l
print(bit, end=' ')
s = 0
for p in range(4):
if bit[p]:
print(A[p], end=' ')
s += A[p]
print(s)📍 비트 연산자
- 비트는 두 가지 형태를 저장할 수 있는 최소 단위
- << 연산자
1 << n : 2**n 즉, 원소가 n개일 경우의 모든 부분집합의 수를 의미한다
1을 왼쪽으로 n번 옮겨라
옮겨가면 빈 자리는 0이 채워진다
0 0 0 1 -> 1 0 0 0
2의 3제곱 자리가 1인 값 > 2**3 = 8
2의 n개가 있을 때 비트 연산자를 이용해 구할 수 있다
- & 연산자
i & (1 << j): i의 j번째 비트가 1인지 아닌지를 검사
a라고 하는 변수에 0 0 1 1 저장되어있음
내가 한개의 비트만 검사하고 싶다면 검사하고 싶은 비트만 1인 값으로 &연산을 한다
관심사는 내가 검사하고자 하는 비트
내가 검사하고자 하는 비트 번호는 j,
j 번 비트가 1인 값을 만들어서 검사해봐 j 번 비트가 1인지 아닌지 검사
0이면 전체 결과가 0, 1이면 전체 연산 결과가 0이 아닌 결과가 나오게 된다
보다 간결하게 부분집합을 생성하는 방법
- n개의 원소가 있으면 n개의 비트로 표현 가능
- for i in range(1<<n)은 0에서부터 2의 n제곱 -1까지를 i가 갖는다
- i & (1<<j) j번 원소가 1이면 포함되어있는 부분집합이라고 하자
이전 방법은 이름만 bit고 배열을 만들어서 [0, 0, 0, 0]으로 만들었지만 이번엔 다르다
3개의 비트가 있으면 2의 3제곱개까지 만들 수 있다
