파이썬 스터디 5주차(백준)

4주차 머신러닝 파트 분량이 너무너무 많다.

이해도 잘 안되는데 종류도 많고 양도 많아서 소화는 커녕 삼키는거라도 가능하면 다행...

루틴이나 순서가 깨지는 걸 좋아하진 않지만 이런 경우 어쩔 수 없다ㅠㅠ

 

---

브루트 포스 : 조합 가능한 모든 문자열을 하나씩 대입해 보는 방법으로 암호를 해독하는 방법.

 

https://www.acmicpc.net/problem/2798

2798번: 블랙잭

import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
cardlist = list(map(int, sys.stdin.readline().split()))
temp_num = 0
for cards in combinations(cardlist, 3):
  temp_sum = sum(cards)
  if temp_num < sum(cards) <= m:
    temp_num = temp_sum
print(temp_num)

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다. 첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력.

> combination의 수만큼 반복하면서 temp_sum에 임시 값(각 조합의 합)을 저장한 뒤 조건을 만족한다면 temp_num에도 그 값을 저장한다. 즉 조건이 맞다면 temp_num은 반복문을 돌면서 더 적합한 값으로 갱신되고, 반복문이 끝났을 때의 temp_num 값이 최종 값이다.

> 처음엔 n, n-1, n-2  이런식으로 풀었는데 도저히 예제 값이 안나오길래 뭔가 했다. 문제를 다시 보니 이웃한 값들끼리 더한다는 조건이 없었으므로 random의 sample을 사용해 2차 시도를 해보려 했으나, 이 경우 카드 합의 개수가 총 몇개여야하는지에 대한 계산이 필요했다. Combination 개념이 생각나 구글링 해 보았는데, 이 개념을 활용하는 게 맞았다.  Combination을 사용하면 random을 사용하지 않고도(더 간단하게) 계산할 수 있다!!

> from itertools import combinations \n combinations(a, b) 는 aCb의 경우의 수를 구해준다.

> list(map(int(input())))으로 여러 정수를 리스트 요소들로 받을 수 있다.

> 리스트명.remove('a')는 리스트 내에서 a를 지운다. a의 중복값이 있는 경우 인덱스값이 가장 적은 a를 삭제한다.

 

 

https://www.acmicpc.net/problem/2231

2231번: 분해합

import sys

n = int(sys.stdin.readline())
m = 0
for i in range(1, n+1):
  temp_list = list(map(int, str(i)))
  m = i + sum(temp_list)
  if m == n:
    print(i)
    break
  if i == n:
    print(0)

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램 작성. 생성자가 없는 경우에는 0을 출력.

> 저기서 i는 그대로의 값, sum(temp_list)는 각 자리수의 합을 말한다. 즉 i+sum(temp_list)는 i가 198이라 가정했을 때 198+sum([1, 9, 8])이므로 216이다. 진짜 이런 걸 어떻게 생각해내지? 진짜 너무 신기하고 대단하다...

> 문제 이해만 해도 10분은 걸린 것 같은데 어떻게 풀어야 할 지 갈피 잡는 것도 쉽지가 않았다.

> 사실 https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-2231%EB%B2%88-%EB%B6%84%ED%95%B4%ED%95%A9-%ED%8C%8C%EC%9D%B4%EC%8D%ACPython덕분에 풀 수 있었다... ^^ 코드를 보자마자 아!!! 헐!! 하면서 깨달음과 동시에 감탄했다. 진짜 대박.. 어떻게 이렇게 풀 수가 있지.

> `list(map(int, str(i)))`는 str(i)를 int로 변환해 list요소로 만든다는 뜻. 조만간 기초도 다시 공부해야 겠다..!

백준 2231번 분해합 파이썬(Python)

 

 

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

import sys
n, m = map(int, sys.stdin.readline().split())
board = []
for i in range(n):
  board.append(sys.stdin.readline().strip())
chess = []

for i in range(n-7):
  for j in range(m-7):
    w_cnt, b_cnt = 0, 0
    for k in range(i, i+8):
      for l in range(j, j+8):
        if (k+l) % 2 == 0: 
          if board[k][l] != 'W':
            w_cnt += 1
          if board[k][l] != 'B':
            b_cnt += 1
        else:
          if board[k][l] != 'B':
            w_cnt += 1
          if board[k][l] != 'W':
            b_cnt += 1
    chess.append(w_cnt)
    chess.append(b_cnt)
print(min(chess))

M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성.

> 만약 n과 m이 8초과라면 추가적인 경우의 수가 생기게 된다. 그에 대한 반복문인 i와 j는 range(n-7), range(m-7)로 (9*9의 경우 4개) 경우의 수를 계산한다. w_cnt와 b_cnt는 각각 흰색/검은색으로 시작한 경우에 칠해야 하는 개수이다. k와 l은 8*8인 체스판에 대한 반복문이다.

> k+l을 2로 나누었을 때 0이 나오는 최솟값은 0이다. (0,0)이라는 시작점이 W색이라면 (1,1) 또한 W여야 하고 (0,1)은 B여야 한다. (1,0)이 W인 경우 이는 B로 칠해져야 하기 때문에 b_cnt에 1을 더한다.

> n*m의 나무판을 가정하고 n//2, m//2로 나눠 열심히 풀다가 체스판이 8*8로 고정되어 있다는 조건을 뒤늦게 읽어 포기할'뻔' 했다. 이 또한 구글링의 도움을 많이 받았다.. 사람들은 정말 똑똑한 것 같다. 나도 이런 식으로 언젠가는 누군가한테 도움이 될 수 있겠지..?

https://jennnn.tistory.com/6

[백준] 1018. 체스판 다시 칠하기 / python 파이썬

---

뭔가 본격적인 알고리즘 문제풀이를 하는 듯한 느낌이다. 생각보다 너무 어렵고, 생각보다... 내 사고능력이 딸린다. 화이팅.. 열쩡 열쩡 열쩡!