algorithm2.md

Algorithm +

배열

배열 : 2차원 배열

• 1차원 List를 묶어주는 List
• 2차원 이상의 다차원 List는 차원에 따라 Index를 선언
• 2차원 List의 선언 : 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함
• python 에서는 데이터 초기화를 통해 변수선언과 초기화가 가능함

2차원 배열의 접근

• 배열순회
  • nm 배열의 nm개의 모든 원소를 빠짐없이 조사하는 방법
  • ex) 행 우선 순회(열 우선 순회면 j와 i의 순서를 바꾸어 주면 된다.
  • 행과 열의 수가 다를 겨우 조심해야 한다.

for i in range(n):
	for j int range(m):
			array[i][j]

• 델타를 이용한 2차 배열 탐색

arr[0...N-1][0..N-1] N*N배열
di[] <- [0, 0, -1, 1]
dj[] <- [-1, 1, 0, 0]
for i : 0 -> N-1
    for j : 0 -> N-1:
        for k in range(4):
            ni <- i + di[k]
            nj <- j + dj[k]
            if 0 <= ni < N and 0 <= nj < N
            # 유효한 인덱스면
            test(arr[ni][nj])

ex) 예시

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, ni, nj)

결과값으로

0 0 0 1
0 0 1 0
0 1 0 2
0 1 1 1
0 1 0 0
0 2 1 2
0 2 0 1
1 0 1 1
1 0 2 0
1 0 0 0
1 1 1 2
1 1 2 1
1 1 1 0
1 1 0 1
1 2 2 2
1 2 1 1
1 2 0 2
2 0 2 1
2 0 1 0
2 1 2 2
2 1 2 0
2 1 1 1
2 2 2 1
2 2 1 2
# 이렇게 나올 것이다. (가능한 자리수, if문을 통해 불가능한 자리들을 제외할 수 있다. )

• 전치 행렬

i : 행의 좌표, len(arr)
j : 열의 좌표, len(arr[0])
arr = [[1,2,3],[4,5,6],[7,8,9]]
for i in range(3):
    for j in range(3):
        if i < j:
            arr[i][j], arr[i][j] = arr[j][i], arr[i][j]

부분집합의 합

• 완전 검색 기법으로 부분 집합의 합 문제를 풀기 위해서는 우선 집합의 모든 부분 집합을 생성한 후에 각 부분 집합의 합을 계산해야 한다.

• 부분 집합의 수

  • 집합의 원소 n개일 때 공 집합 포함하여 2**n개
  • A = [1, 2, 3, 4]
  • 고정으로 리스트의 원소가 적을 때 사용할 수 있다.
  • 흘러가는 흐름을 파악하자
  • 만약 원소가 많은 경우 재귀 혹은 다른 방법을 찾아보자

  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)

  [0, 0, 0, 0] 0
  [0, 0, 0, 1] 4 4
  [0, 0, 1, 0] 3 3
  [0, 0, 1, 1] 3 4 7
  [0, 1, 0, 0] 2 2
  [0, 1, 0, 1] 2 4 6
  [0, 1, 1, 0] 2 3 5
  [0, 1, 1, 1] 2 3 4 9
  [1, 0, 0, 0] 1 1
  [1, 0, 0, 1] 1 4 5
  [1, 0, 1, 0] 1 3 4
  [1, 0, 1, 1] 1 3 4 8
  [1, 1, 0, 0] 1 2 3
  [1, 1, 0, 1] 1 2 4 7
  [1, 1, 1, 0] 1 2 3 6
  [1, 1, 1, 1] 1 2 3 4 10

비트 연산자

& : 비트 단위로 AND 연산을 한다.

• ex) i & (1<<j) : i 의 j 번째 비트가 1인지 아닌지 검사한다.

'<<' : 피연산자의 비트 열을 왼쪽으로 이동시킨다.

• ex) 1<<n : 2**n → 원소가 n개일 경우의 모든 부분 집합의 수를 의미한다.

'>>' : 피연산자의 비트 열을 오른쪽으로 이동시킨다.

'>' : 비트 단위로 OR 연산을 한다.

bit = [0 for _ in range(N)]
for i in range(1, 1 << N):
    # i 가 0에서 2**n -1까지 반복하게 된다.
    subset_sum = 0
    for j in range(N):
        if i & (1 << j):
            subset_sum += arr[j]