본문 바로가기

CodingTest

 (238)
[ BOJ / 파이썬 ] 2193. 이친수 일단 문제 파악 위해 쭉 경우의 수를 써내려갔다. 1자리 1 2자리 10 3자리 100 101 4자리 1000 1001 1010 5자리 10000 10001 10010 10100 10101 일단 보통 초기값은 1개나 2개 잡는다고 가정하며 n항과 n-1항 사이 관계식 도출하려고 생각해보는데. 오 싹 스쳤다.. 사실상 5자리수는 4자리수를 안고 있어서는 안된다. 반면, 3자리수부터 2자리, 1자리수는 모두 안고있다. 왜냐하면 바로 다음자리수를 안는다면 11이 연달아서 나오니까!. 1자리, 2자리에서 점차 늘리는건 보통 조건에 부합한다는걸 보장하므로 신경안쓰고! 바로 이전자리수 뺀 모든 자리수들의 합 + 1 이 되는 셈이다. .. 엥 근데 왜 풀이를 이렇게 했지.. 직관적으로 풀기는 했는데 정리하려니 .....
[ BOJ / 파이썬 ] 11727. 2xN 타일링 2 보호되어 있는 글입니다.
[ BOJ / 파이썬 ] 1932. 정수삼각형 오.. 이제 DP는 어느정도 감 잡아가는 느낌이다 이예에 ~ 진짜 몇 달 전에 이 정도 문제도 감이 안 잡혔었는데... 정말 난독증이었던걸까.. 🙄😥 하여간 데이터 배열 자체에 메모제이션으로 해결할 수 있는 간단한 문제였다. 대신 핵심포인트는 해당 열의 첫 값과 끝 값을 예외처리해줘야 함. n = int(input()) triangle = [list(map(int, input().split())) for _ in range(n)] for i in range(1, n): row = triangle[i] triangle[i][0] += triangle[i-1][0] for j in range(1, len(row)-1): triangle[i][j] += max(triangle[i-1][j], triangle[..
[ BOJ / 파이썬 ] 12100 2048(Easy) 보호되어 있는 글입니다.
[ BOJ / 파이썬 ] 1182.부분수열의 합 백트래킹의 n과 m이나 n queen 문제와는 살짝 차이가 있는 풀이 유형을 익힐 수 있었다. 보통 visited[n] = 1 func(n) visited[n] = 0 이런 식으로 방문여부를 방문append() - 재귀 깊이 + 1 - 방문pop() 요런 느낌이었는데. 이 문제에서는 func( 이 단계에서 실행 X, depth+1) func( 이 단계에서 실행 O, depth+1) 이런 식으로 풀어나갔다. ... 그리고 해당 문제 풀이에서는 정말 기초적인 수학 이해가 필요했다. 크기가 양수인 부분수열일 때만이라는 조건을 그냥 넘기려 했는데 예제 입력처럼 합이 0인 경우 = 그러니까 크기가 0인 경우는 예외처리를 할 필요가 있었던 것이다. 놓치기 쉬운 부분이었다. 풀이. 정답 import sys input..
[ BOJ / 파이썬 ] 9663. N-QUEEN 백트래킹을 효율적으로 풀어내는 것과 배열의 대각선 형태의 접근에 대해서 정리할 수 있는 좋은 문제였다. - 배열 사용해서 방문값을 저장해두기 - - 대각선 - 왼쪽에서 오른쪽으로 내려오는 대각선 칸들은 같은 줄마다 x+y 값이 같다. 오른쪽에서 왼쪽으로 내려오는 대각선 칸들은 같은 줄마다 x-y+n-1 값이 같다. 대각선 개수는 2*n - 1개. 정답코드. 통과. import sys input = sys.stdin.readline def queen(k): global result if k == n: result += 1 return for i in range(n): if not col[i] and not diagLtoR[i+k] and not diagRtoL[k-i+n-1]: col[i] = 1 diag..
[ BOJ / 파이썬 ] 15649. N과 M(1) 음 .. ? 의외로 꽤 빨리 풀리고.. 이전 문제 풀이보다 실행시간도 줄었다..! 음 .. 실력이 늘긴 늘었나 진짜. 코드. 통과. import sys input = sys.stdin.readline n, m = map(int, input().split()) visited = [0] * (n+1) result = [] def recur(k): if k == m: print(*result) return for i in range(1, n+1): if not visited[i]: visited[i] = 1 result.append(i) recur(k+1) visited[i] = 0 result.pop() recur(0) 처음에는 현재 방문한 배열(visited) 하나만 두고 k가 일정 깊이 도달했을 때 그냥..
[ BOJ / 파이썬 ] 2447. 별 찍기 - 11 아 .. 요게 안 되네 진짜 ㅠㅜㅠ 싶어서 꽤 오래 걸렸다. 접근법은 알겠는데 묘하게 구현에서 뻑나서 결국 몇 개월 전 스스로 풀었던 풀이를 보고 완성했다. 이번에 못 해낸 이유는 재귀에서 조건에 만족했을 때 바로 프린팅을 찍으려고 한 점. 재귀 도는 순서상 프린트를 한 번에 하는게 안 된다. 그래서 미리 같은 사이즈의 결과 배열을 만들어두고, 재귀함수를 돌면서 가장 말단에 갔을 때 결과 배열을 업데이트하고 마지막에 완성된 결과물을 한 번에 프린팅해야한다. 해당 정답 코드. import sys input = sys.stdin.readline n = int(input()) template = [['*','*','*'],['*',' ','*'],['*','*','*']] def recursive(x, y, ..
[ BOJ / 파이썬 ] 쿼드트리 재귀 재귀 문제에서 지금 반복해 연습 중인 도형 자르기 문제. 6개월 전 풀었던 풀이를 바탕으로 시간복잡도 줄이기 위해 코드를 정리해나가봤다. 우선, 6개월 전 풀이. # 하.. 처음에 quadtree짤 때, return 받아서 print하게 한 걸, # 수정하면서 같이 안 고쳐줘서 엄한 데서 오류 찾고 있었다. 시간 많이 잡아먹었다:-( import sys input = sys.stdin.readline n = int(input()) board = [list(map(int, input().strip())) for _ in range(n)] def quadtree(x, y, n): if n == 1: print(board[x][y], end="") return canCompress = True for i..
[ BOJ / 파이썬 ] 11729. 하노이 탑 이동 순서 와.. 정말 초등 기초 교구느낌이었던 하노이 탑인데.. 생각해보면 나는 어렸을 때 풀어본 적이 없다. 하하 그래서일까 꽤 버거웠다. 핵심은 반복되는 재귀 구조의 일반항을 찾아내는 것. function(n) 에서 function(n-1)을 이용한 function(n)의 내용을 정리하는 게 핵심이었다. 사실 이게 재귀 문제의 핵심이라 어려운 부분인데.. 그래서 더 끈질기게 이 문제 잡고 늘어지면서 이해를 했던 것 같다. 어떤 문제를 만나도 잘 풀어낼 수 있도록 문제 자체에서 그 방식을 읽어내는 사고를 갖고자 했다. 정말 ! 정말 ! 도움이 많이 됐던 글.. ( 링크 ) 위의 글을 참고해서 풀어낸 코드. 정답. def move(k, start, to): global result result.append((st..

티스토리툴바