self.winter.(09-1). brute force와 딕셔너리 활용, pair _ 백준[2798, 2231, 7568, 1436, 1018]

🧐 딕셔너리 (Dictionary). { key : value }

🤔 딕셔너리 개념

key-value를 하나의 쌍으로 갖는 자료구조로 다른 언어에의 map과 같은 기능을 한다.

이때, 딕셔너리는 키가 중복되는것을 허용하지 않는다!

이때, 딕셔너리는 키가 중복되는것을 허용하지 않는다!

 

 

🤔 딕셔너리의 생성과 삭제

dict_a['name'] = 'b'
dict_b[3] = 2

del dict_a['name']  # del a[key]

 

🤔 딕셔너리 key, value에 대한 접근-1

dict_a.keys() 	# key 객체들을 return
dict_a.values() # value 객체들을 return 
dict_a.items()	# key-value 쌍을 return

 

🤔 딕셔너리 key, value에 대한 접근-2. (key로 value얻기, value로 key얻기)

dict_a.get(key)  # key에 해당하는 "value값 출력"

for i in dict_a  			# 기본적으로 for문에서 i를 통해 key값을 사용할 수 있음
for i in dict_a.values()    # 기본적으로 for문에서 i를 통해 value값을 사용할 수 있음

for key, value in dict_a.items():  # key와 value를 한번에 사용
for key, value in dict_a: 		   # 위와 동일한 사용법

 

😶 활용 

for i in construct.keys():
    if construct[i] == n:  # key의 어떤 값이 n과 같다면
        ans.append(i)      # {construct[i] : i} key에 해당하는 value, i를 추가

 

 

 

🧐 백준 2798  (딕셔너리 활용)

🤫 해결의 실마리 1. brute force (완전탐색)

처음부터 끝까지 모두 탐색하는 방법의 brute force를 사용한다,.

🤫 해결의 실마리 2.  딕셔너리와 set 

cf. 딕셔너리 객체의 get()함수

dict.get(key, default = None) 
# 매개변수로 넘긴 값 (괄호 안의 값)이 키에 속하지 않으면? None 출력

get함수의 return값은 첫번째 인자의 키값이다.

🤔 Algorithm 과정 
1. 입력받은 숫자 리스트들에서 3개의 숫자를 골라 더한 값을 set에 집어넣는다.
2. 이 sum_set에 대해 입력된 M을 넘지 않는 것들에 대해 딕셔너리 형태로 세 숫자의 합과 m과의 차이를 저장한다.
3. 이때, 저장한 m과의 차이가 가장 작은 것이 m과 가장 가까운 것이므로 답임을 알 수 있다.
 

🤫  solution_2798

n, m = map(int, input().split())
num = list(map(int, input().split()))

sum_set = set()
sum_dict = {}

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            sum_set.add(num[i] + num[j] + num[k])

for i in sum_set:
    if m - i >= 0:
        sum_dict[i] = m - i
    else:
        pass

print(min(sum_dict, key = sum_dict.get))

 

 

🧐 백준 2231  (딕셔너리 활용)

🤫 해결의 실마리 1. 자연수의 자릿수에 해당하는 숫자 구하기.

# 각 자릿수의 숫자의 합을 출력하는 함수
def digit(n):
    if n < 10:
        return n
    else:
        return digit(n // 10) + digit(n % 10)

🤫 해결의 실마리 2.  딕셔너리의 사용 

construct = {}
for i in range(n+1):
    construct[i] = i + digit(i)

ans = []

for i in construct:
    if construct[i] == n:
        ans.append(i)

🤔 Algorithm 과정 

216 => 198 + 1 + 9 + 8  ... 이런 방식은 거의 불가 (역추적 진행 시 생성자가 여러개임을 도출할 수 없음)

맵핑을 통해 1~N까지 똑같은 value들 중 최소 key를 찾는 방식으로 문제를 해결해 나갈 것이다.

{1:1}
{2:2}
...
{13:17}
{14:19}
{15:21}
...
{198:216}
...
{N:N'}

 

🤫  solution_2231

n = int(input())

# 각 자릿수의 숫자의 합을 출력하는 함수
def digit(n):
    if n < 10:
        return n
    else:
        return digit(n // 10) + digit(n % 10)

construct = {}
for i in range(n+1):
    construct[i] = i + digit(i)

ans = []

for i in construct:
    if construct[i] == n:
        ans.append(i)
print(0) if len(ans) == 0 else print(min(ans))

 

 

🧐 백준 7568 (C++의 pair와 같은 자료구조가 필요해!)  ★★★★★

🤫 해결의 실마리.  pair 처럼 입력받은 key와 value가 겹쳐도 되는 자료구조를 생성하자!.

for _ in range(int(input())):
    w, h = map(int, input().split())
    person.append((w, h))

# print(person)  => [(55, 185), (58, 183), (88, 186), (60, 175), (46, 155)]

🤔 Algorithm 과정 
1. 각각 받은 w, h에 대해 등수는 1부터 시작하므로 rank = 1로 초기화해준다.
2. 입력한 변수들을 저장한 person리스트에 대해
0번째 인덱스(몸무게)와 1번째 인덱스(키)가 모두 큰 경우에 rank를 1 증가시켜준다.

 

🤫  solution_7568

person = []

for _ in range(int(input())):
    w, h = map(int, input().split())
    person.append((w, h))

# print(person)  => [(55, 185), (58, 183), (88, 186), (60, 175), (46, 155)]


for i in person:
    rank = 1
    for j in person:
        if i[0] < j[0] and i[1] < j[1]:
            rank += 1
    print(rank, end = " ")

 

 

🧐 백준 1436

🤔 Algorithm 과정 
1. 처음 666인 수를 terminal변수에 저장
2. n이 0이 아닐 때 까지 반복하는데, 문자열 terminal을 update하는 방식으로 문제를 해결할 것이다.
3. terminal 문자열 안에 666이 들어있다면, n을 1만큼 감소시키고 
4. 만약 n이 0이라면 반복문을 탈출한다.
5. 이후 terminal의 값을 1만큼 증가시킨다.
 

🤫  solution_1436

n = int(input())

terminal = 666
while n != 0:
    if '666' in str(terminal):
        n -= 1
        if n == 0:
            break
    terminal += 1
print(terminal)

 

 

🧐 백준 1018 (CNN 알고리즘)

🤫해결의 실마리. CNN Algorithm (Convolution Neural Network)

CNN에서 filter를 이용해 합성곱 계층의 동작처럼 8X8의 정답 체스판을 만들고 
CNN알고리즘처럼 입력받은 체스판을 스캔하면서 틀린 경우를 카운팅해서 틀린경우의수가 최소를 출력한다.


🤔 CNN_Algorithm 과정 

https://wikidocs.net/164823

 

🤫  solution_1436

n, m = map(int, input().split())

chess = [list(input()) for _ in range(n)]
ans_chess_W , ans_chess_B = [], []
for i in range(4):
    ans_chess_W.append('WBWBWBWB')
    ans_chess_W.append('BWBWBWBW')
    ans_chess_B.append('BWBWBWBW')
    ans_chess_B.append('WBWBWBWB')


def wrongcount_W (x, y):
    cnt = 0
    for i in range(8):
        for j in range(8):
            if chess[x+i][y+j] != ans_chess_W[i][j]:
                cnt += 1
    return cnt

def wrongcount_B (x, y):
    cnt = 0
    for i in range(8):
        for j in range(8):
            if chess[x+i][y+j] != ans_chess_B[i][j]:
                cnt += 1
    return cnt

# CNN처럼 8x8 size로 체스판 자르기
cnt = []
for i in range(n-8 +1):
    for j in range(m-8 +1):
        cnt.append(wrongcount_W(i, j))
        cnt.append(wrongcount_B(i, j))
print(min(cnt))