본문 바로가기

Study/Python

백준 14002 (Python 파이썬) 2022. 1. 13. 사실 이전 문제에서 글을 썼어야 했는데, 바로 뒤에 유사한 친구가 있는 것을 보고 그 친구로 써야겠다 생각하여 이 문제를 풀고 포스팅한다. 문제 이해하는 데에는 시간이 많이 걸리지는 않았다. 하지만, 이 친구를 DP를 어떻게 이용해서 풀어야 하지라는 고민 때문에 시간이 좀 걸렸다. 일단은 DP테이블을 비교해주기 전에 리스트를 돌면서 이전 인덱스보다 값이 큰지를 비교한다. 그러고 나서, 값이 크다면 지금 까지 쌓아왔던 DP테이블이 크기가 작은 인덱스가 더 크면 증가하는 범위에 숫자가 있는 것이기 때문에 크기가 작은 인덱스의 DP테이블을 크기가 큰 인덱스의 DP테이블로 옮겨준다. 그리고 일괄적으로 for문이 끝나면 해당 DP테이블을 +1을 해주면서 DP테이블을 설정해준다. 여기까지가 이전 문제, 조건이 추가..
백준 10844 (Python 파이썬) 2022. 1. 10. https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 실버 1 문제다. 사실 실버 1이랍시고, 그냥 이 전에 있던 dp 문제들과 별반 다를 바 없었다. 저번 문제랑 굉장히 유사해서인지 구선생님의 도움 없이 혼자서 문제를 해결할 수 있었다. 이 문제 역시 2 자릿수던지, 3 자릿수던지 모두 이전 자리에 영향을 미친다. 어떻게 미치는지는 표로 알아보도록 하자. 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 우선 각각의 숫자로 만들 수 있는 1자리 수의 계단 수를 표로 나타낸 것이다. 1,2,3,4,5,6,7,8,9 모두 계단 수 이기 때문에 ..
백준 15990 (Python 파이썬) 2022. 1. 10. https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 이번 문제 역시 DP문제이다. 이번 문제 관련하여 이거보다 조금 더 쉬운 1,2,3 더하기가 있었는데, 그 친구는 점화식만 간단하게 구하면 되는 문제여서 어려운 점이 없었다. 하지만, 이번 친구는 DP테이블을 구상하는 것부터 다른 문제들과 달랐기 때문에 어려움이 좀 있었다. 1시간 정도 고민하다가 해결할 수 없다 판단하여 구선생님의 도움을 조금 받았다. 이 문제는 이전 값의 결과가 다음 값에 영향을 미친다. 1을 만들어주려면 1 하나, 2를 만들어..
백준 2089 (Python 파이썬) 2022. 1. 5. 실버 4라 얕보고 들어갔다가 크게 혼났다. 문제 이해하는 데에는 오래 걸리지 않았다. 2진수인데 -2진수 인 것이다. 이거 저거 하면서 규칙을 찾아보려 하다가, 도저히 모르겠어서 질문 검색으로 가서 약간의 팁을 들었다. -2진 수라 너무 쫄지 말고 그냥 2진수 풀던 것처럼 풀면 된다는 것이었다. 대신에 -2로 숫자를 나누면 나머지가 0,1,-1 이 3개가 나올 수 있으니 -1의 나머지가 나오는 경우에는 몫에 1을 더해줘서 나머지를 1로 만들어 줘야 한다는 것이 포인트였다. 사실 진법에 대한 이해가 빠삭했다면 이 부분은 충분히 생각해 낼 수 있었을 것이다. 하지만, 진법에 대한 이해가 빠삭하지 못해 이 부분을 생각해내는데 좀 걸렸다.. import sys import math a = int(sys.stdi..
백준 1654 (Python 파이썬) 2022. 1. 1. 이번 문제는 이분 탐색이라는 새로운 개념이 나와 write up을 작성해 본다. 사실 알고 있었던 개념이라 새롭지는 않은데, 알고리즘 문제를 품에 있어서 이를 사용해본 적은 이번이 처음이다. 이 문제에 대해 어떻게 풀어야 할지 고민하다. brute force를 사용하여 풀기로 하였다. 코드를 작성하면서 마음속 한 구석에는 당연히 시간 초과 날 텐데.., 라는 생각을 가지고 있었지만, 혹시나 모르는 마음에 작성해 보았다. import sys a, b = map(int, sys.stdin.readline().split()) cnt = [] ranswer = [] for i in range(a): cnt.append(int(sys.stdin.readline())) for j in range(1, min(cnt..
Boj_17298 (Python 파이썬) 2021. 12. 28. 문제의 큰 특이점은 없지만, 처음으로 시간 복잡도에 대한 생각을 굉장히 깊게 하고 푼 문제여서 풀이를 작성해 보겠다. 문제는 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 여기로 가면 확인할 수 있다. 문제만 놓고 보면 어려울 게 없다. 그냥 요소마다 돌면서 그 옆에 있는 수들 중에 자신보다 크면서 가까운 수를 출력해주면 되는 것이다. 없으면 -1을 출력해줘야 한다. 하지만, 시간제한을 보니 1초였다. 딱 보고 이중 포문을 써야겠다는 생각이 들었지만 시..
Boj_1406 (Python 파이썬) 2021. 12. 23. 한동안 프로그래머스 문제 풀이를 올리지 않았다. 이유는 애초에 목표였던 프로그래머스 2단계를 다 풀고 백준으로 넘어갔기 때문이다. 백준에는 문제가 정말 많기 때문에 문제 푸는 순서도 중요하다고 들었다. 그래서 유명한 유튜버의 순서를 듣고 그대로 풀고 있다. 우선은 단계별로 풀어보기의 정렬까지는 풀어보라고 하셨다. 재귀는 나의 실력에 한탄하며 다음을 기약한 문제가 2개나 있다. 정렬까지 다 풀고나면 밑의 문제들은 알고리즘 문제들이기 때문에 강의로 넘어가서 강의에 나오는 백준 선생님께서 요약해놓은 문제들을 차례로 풀어보라고 하셨다. 현재 이 강의의 문제를 풀고있는 중이다. 여러개 문제를 풀다가 1406 이 문제에서 막힌것은 아니지만 깨달은 것이 너무 많아 포스팅하고자 한다. 문제는 https://www.ac..
programmers_level2_gamemap 2021. 12. 4. 4100명 정도가 풀어서 쉽진 않겠지만, 못 풀 정도는 아니겠구나 싶어 문제를 풀어보았다. https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 문제 예시가 길어서 따로 적지는 않겠다. 문제를 보고 내가 제일 자신 없어하는 최단경로임을 발견했다. 이 부분을 많이 풀어보지 못한 것도 있지만, 이론상으로도 공부가 되어 있는 상태가 아니었기 때문에 자신이 없을 수밖에..

티스토리툴바