본문 바로가기

CodingTest

 (238)
[ BOJ / 파이썬 ] 11726 2xn 타일링 사실 수학적 센스가 필요한 문제라 처음 만나면 풀어낼 자신은 없다. 대신 해설을 보고나면 구현 자체는 어렵지 않다. DP문제는 많이 풀어보는 것이 힘! 코딩테스트는 경험이 힘! 해당 문제는 일단 DP로 풀 수 있다는 것을 알아채기도 까다로운 것 같다. 그런데 점화식을 세우는게 진짜 아리송하다. 다만 우리에게 주어진 경우의 수가 사실은 몇 개 되지 않는다는 사실, 배치가 중복된다는 사실을 파악하면 되는 문제다. 2 x 1 1 x 2 를 놓는데, dp테이블을 dp[i] 가 2 x i 를 채우는 방법의 수라고 할 때, dp[1] = dp[n-1] 이다. 왜? 2 x n 바닥에서 2 x 1을 뺐으니 남은 건 2 x (n-1) 바닥이기 때문에. 2 x (n-1) 바닥을 채우는 수와 같기 때문. 1 x 2 의 경우..
[ BOJ / 파이썬 ] 1149 RGB거리 import sys input = sys.stdin.readline n = int(input()) R = [] G = [] B = [] for i in range(n): r, g, b = map(int, input().split()) R.append(r) G.append(g) B.append(b) d = [[0] * 3 for _ in range(n)] d[0][0] = R[0] d[0][1] = G[0] d[0][2] = B[0] for i in range(1, n): d[i][0] = min(d[i-1][1], d[i-1][2]) + R[i] d[i][1] = min(d[i-1][0], d[i-1][2]) + G[i] d[i][2] = min(d[i-1][0], d[i-1][1]) + B[i] pri..
[ BOJ / 파이썬] 2579 계단 오르기 정말 간만에 PS문제 푸니까 또 재밌고 할 만한 것 같다. 그리고 조금 원리를 이해해서 푸는 느낌이 나니 문제 풀이력이 느는 느낌이 확실히 든다. 역시 일이 진행되다가 너무 답도 없이 고여버리면 잠시 쉬고 오는 것도 ( 노는게 아니라 비슷한 다른 일 ..^^) 좋은 것 같다. 사담은 여기까지 하고, 우선 해당 문제가 DP라는 정보를 알고 부딪힐 수 있었다. 그래서 더 답에 빠르게 가까워진 것 같다. 1. DP테이블을 어떻게 구성할 지, 어떤 내용을 담을 지를 결정하고, 2. 점화식을 세우고 3. 초기값을 셋팅하는 식으로 풀어라 라고 배웠다. 되게 초보자 티 내는 듯이, DP테이블을 무조건 1차형으로 사용해야한다고 생각했다. 문제 풀이 경험의 부족 때문일 것이다. 이 값을 갖는 계단이 n개 있으므로 1줄의..
[ BOJ / 파이썬 ] 1463 1로 만들기 지금 피곤해서 그런지 솔직히 DP 개념이 잘 머리에 안 들어온다. 그래서 DP문제치고 굉장히 쉬운 편에 속하는 해당 개념도 인식이 잘 안 됐다. 30분 책상에 엎드려서 자고 왔다. import sys input = sys.stdin.readline x = int(input()) dp = [0]*(x+1) for i in range(2,x+1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i],dp[i//3] + 1) if i % 2 == 0: dp[i] = min(dp[i],dp[i//2] + 1) print(dp[x]) 다른 분의 코드를 보니 코드 자체는 이해 가는데, 이걸 내가 습득한 개념처럼 안 다가온다. 조금 쉬고 다시 보자. 1. 테이블 정의하기 :..
[ BOJ / 파이썬 ] 11652 카드 문제 리뷰 확실히 정렬 문제들을 오랜만에 푸는 것 같다. sort 사용 방법을 많이 잊어버려서 하나 하나 검색해서 푼 것 같다. 그래도 다행히 기억이 남아 있어서 검색창에 입력하는 동안 기억이 되살아나서 풀고 그랬던 것 같다. import sys input = sys.stdin.readline n = int(input()) cards = {} for i in range(n): num = int(input()) if num in cards: cards[num] += 1 else: cards[num] = 1 d = dict(sorted(cards.items(), key=lambda item: (item[1], -item[0]), reverse=True)) print(list(d)[0]) 다시 기억 되살릴 것..
[ BOJ / 파이썬 ] 1431 시리얼 번호 음 .. 이 문제는 뭐랄까..? 이 자체의 문제가 의미있게 다가오지는 않고, 여기서 활용되는 정렬 스킬들을 응용해서 더 고차원의 문제를 푸는 데 이용할 수 있을 것 같다는 생각이 들었다. import sys input = sys.stdin.readline n = int(input()) serial = [] for i in range(n): s = input().strip() sum = 0 for i in list(s): if 48
[ BOJ / 파이썬 ] 15688 수 정렬하기 5 1. counting sort 로 풀고 싶었습니다. import sys from collections import OrderedDict input = sys.stdin.readline arr = {} n = int(input()) for i in range(n): k = int(input()) if k in arr: arr[k] += 1 else: arr[k] = 1 arr = OrderedDict(sorted(arr.items(), key = lambda t:t[0])) for key, value in arr.items(): for i in range(value): print(key) : 백준 사이트에 파이썬으로 제출하면 시간 초과가 납니다. : 언어 설정을 PyPy3로 바꿔서 내야지 맞았습니다! 처리..
[ BOJ / 파이썬 ] 15686 치킨 배달 / 첫 제출 / import sys input = sys.stdin.readline n, m = map(int, input().split()) city = [list(map(int, input().split())) for _ in range(n)] chickens = [] homes = [] for x in range(n): for y in range(n): if city[x][y] == 2: chickens.append([x, y]) if city[x][y] == 1: homes.append([x, y]) chickenDist = [] for store in chickens: i = 0 dist = 0 for home in homes: dist += abs(store[0] - home[0]) + abs..
[ BOJ / 파이썬 ] 18808 스티커 붙이기 https://seongonion.tistory.com/113 [백준] 18808번 스티커 붙이기 - 파이썬(Python) 문제 (링크) https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종 seongonion.tistory.com : 행과 열의 크기가 다른 스티커는 90도 돌릴 때 r과 c의 값도 변경해야한다는 것을 몰랐다. 경험 차이. 비슷한 문제 나오면 헷갈리지 말 것! : 90도 돌리기 복습 r * c일 때, for i in range(r): for j in range(c): changed[i][j] = original[r-j-1][..
[BOJ / 파이썬] 15683 감시 https://soohyun6879.tistory.com/241 [백준/Python] 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는 soohyun6879.tistory.com : 아.. 그래도 꽤 접근했는데, 끝내 정답은 못 맞추네. : 그리고 제 생각에 이 문제는 정말 짜기 까다롭습니다. 대충 어떤 느낌이냐면 대충 구현 방향은 잡았고 천천히 구현을 하려고 하는데 짜다보니 꼬이고 코드 길이가 끝없이 길어지고, 기껏 완성한 후에 돌렸더니 결과가 이상해서 코드 중간중간에 끊임없이 출력문을 넣어서 잘못된 부분은 ..

티스토리툴바