[알고리즘] 스트링, 2차원 리스트, 비트연산자

장현수·2023년 5월 15일
0

알고리즘

목록 보기
6/9

스트링 알고리즘, 2차원 리스트 ~ 순열조합 백트래킹

  • brute force
    : 무지성으로 다 돌려보는 것

2차원 리스트

이중 for문

matrix = [[3, 7, 9],
          [4, 2, 6],
          [8, 1, 5]]

for i in range(3):
    for j in range(3):
        print(matrix[i][j], end=" ")
    print()
3 7 9 
4 2 6 
8 1 5 
  • 반복문 중첩
  • 2차원 리스트에서 사용

순회&전치

[행 우선순회]

matrix = [[3, 7, 9],
		      [4, 2, 6],
	    	  [8, 1, 5]]

trails = []

for r in range(3):
    for c in range(3):
        trails.append(matrix[r][c])

print(trails)

[열 우선순회]

matrix = [[3, 7, 9],
		      [4, 2, 6],
	    	  [8, 1, 5]]

trails = []

for r in range(3):
    for c in range(3):
        trails.append(matrix[c][r])  # 여기가 바뀝니다.

print(trails)

[지그재그 순회]

[전치]

전치 : 화살표가 반대로 되는 것과 같음

전치는 n*n행렬에서만 가능

matrix = [[3, 7, 9],
		      [4, 2, 6],
	    	  [8, 1, 5]]

for r in range(3):
    for c in range(3):
        if r > c: # r < c로 해도 됩니다.
            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]

for i in range(3):
    print(matrix[i])

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

언패킹 연산자
list(zip(*a))

델타 탐색

중점에서 상/하/좌/우 방향으로 옮기기
r = row, 행
c = column, 열

상 nr = r - 1 / nc = c + 0
하 nr = r + 1 / nc = c + 0
좌 nr = r + 0 / nc = c - 1
우 nr = r + 0 / nc = c + 1

비트연산

set자료구조에는 합집합 교집합

&(and) 연산

  1. set 자료구조에서는 교집합
  2. 10진수 -> 2진수 변환해서 각 자리수의 숫자가 둘 다 1이면 1, 하나라도 0이면 0 출력. 각 자리수에 출력된 값을 10진수로 변환한 값을 출력
    둘 다 1이어야지만 1이다.***
십진수 3을 2진수로 변환 : 011
십진수 6을 2진수로 변환 : 110

0 1 1
1 1 0
------
0 1 0

결과값 010을 10진수로 변환 : 2

따라서 3 & 6 = 2 이다.

|(or) 연산

  1. set 자료구조에서는 합집합
  2. 10진수 -> 둘 다 0이어야지만 0.
십진수 3을 2진수로 변환 : 011
십진수 6을 2진수로 변환 : 110

0 1 1
1 1 0
------
1 1 1

결과값 111을 10진수로 변환 : 7

따라서 3 | 6 = 7 이다.

<< (왼쪽 shift)

  • 비트를 왼쪽으로 n칸 이동시킴
  • 새로 생긴 부분은 0으로 계산
  • 2배씩 늘어남
7 << 1  #2진수 7을 왼쪽으로 한 칸 이동

#2진수 7
1 1 1
=> 2제곱 + 2의 1제곱 + 2의 0제곱

#왼쪽으로 한 칸 이동
1 1 1 0 
=> 2의 3제곱 + 2의 2제곱 + 2의 1제곱 + 0
=> 14

두배가 됨.

>> (오른쪽 shift)

  • 비트를 오른쪽으로 n칸 이동시킴
  • 오른쪽으로 밀려 없어진 부분은 삭제됨
  • 2로 나눈 나머지가 없어짐 : 2의 n승으로 나눈 몫
7 >> 1  #2진수 7을 오른쪽으로 한 칸 이동

#2진수 7
1 1 1

#오른쪽으로 한 칸 이동
1 1
=> 2의 1제곱 + 2의 0제곱
=> 3 (7을 2^1로 나눈 몫)

27 >> 2  #2진수 27을 오른쪽으로 두 칸 이동

#2진수 27
1 1 0 1 1

#오른쪽으로 두 칸 이동
1 1 0
=> 2^2*1 + 2^1*1 + 2^0*0
=> 6 (27을 2^2로 나눈 몫)

^ (xor)

  • 비교하는 값이 서로 달라야지만 1이다. 청개구리

  • 정수를 비트처리 하면 o, x 할 수 있게 됨 -> 부분집합

letters = ['a', 'b', 'c']

for i in range(1 << len(letters)):  # 총 2³, 8개의 경우의 수 체크 모든 경우의 수를 보겠다
    selected = []
    for j in range(len(letters)): # 각각 비트를 한칸씩 옮기며 대조 
        if i & (1 << j):  # 1칸씩 왼쪽으로 옮겨가며 총 3칸을 대조해본다. 각 자리를 확인하겠다
            selected.append(letters[j]) # 대조 결과가 성공이라면 selected에 append!

    print(selected)

<연습 문제>

nums = [1, 1, 3, 2, 2]
answer = 0
for num in nums:
    answer ^= num
print(answer)

1)
answer = answer ^ 1
0 ^ 1 = 1
answer = 1

2)
1 ^ 1 = 0
answer = 0

3)
0 ^ 3 => 0 0 0 ^ 0 1 1
= 011 = 3
answer = 3

4)
3 ^ 2 => 0 1 1 ^ 0 1 0
= 1
answer = 1

5)
1 ^ 2 => 0 0 1 ^ 0 1 0
= 011 = 3
answer = 3


각 블록별로 독립적으로 계산

어차피 자기자신은 xor연산을 하면 0이 됨.
0과 xor연산을 하면 자기자신이 된다.
값이 0인 answer와 ^연산을 했을 때
두 개 들어있는 값은 자기자신을 자기자신과 ^연산을 하게 되고
자기 자신과 xor연산을 하면 0이 된다.
따라서 결과적으로 리스트에 한 개만 있는 값이 출력되게 된다.

profile
개같이 발전하자 개발

0개의 댓글