본문 바로가기

백준36

[백준/파이썬] 2579 : 계단오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 프로그래머스 도둑질문제에서 막혀서 비슷한 유형이라고 소개된 계단오르기를 풀었다. 예전에 풀었던 문제라 금방 풀었음 문제 요약 : 계단 시작점부터 꼭대기 도착점까지 오를 때에 가장 높은 점수로 오르는 경우의 점수를 출력하라. 단, 계단은 연속해서 3계단을 갈 수 없으며 한번에 한계단씩 혹은 두계단씩 오를 수 있다. 풀이 ) DP문제 dp 리스트에는 그 계단을 밟을 때에 가장 높은 점수를 저장해준다. 연속해서 세.. 2022. 10. 14.
[백준/파이썬] 2667 : 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 요약 : 같이 단지가 주어졌을 때, 같이 단지를 구분할 수 있다. 총 단지의 수와 각 단지에 속하는 집의 수를 오름차순으로 출력하라. 풀이 ) DFS, BFS 둘다 풀 수 있는 문제 나는 DFS 재귀로 풀었다. 입력으로 받아온 apart를 for문으로 돌려서 0보다 크면 DFS가 돌아가도록 한다. tmp값은 각 단지의 아파트 개수를 저장하기 위해 임의로 만든 값이고, 함수안에서도 계산될 수 있.. 2022. 10. 6.
[백준/파이썬] 4673 : 셀프 넘버 https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 문제 요약 : 양의 정수 n에 대해서 d(n)은 n과 n의 각 자리수를 더하는 함수이다. 이때 n은 d(n)의 생성자라고 한다. 이 생성자가 존재하지 않는 숫자를 셀프넘버라고 한다. 10000이하의 셀프넘버를 출력해라. 풀이 ) 1차원적이지만 10000까지 저장한 리스트를 만들고, i를 계속 1씩 증가시키면서 셀프넘버가 아닌 숫자를 빼주었다. 깊게.. 2022. 10. 6.
[백준/파이썬] 1541 : 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 요약 : 주어진 식을 괄호를 적절히 사용하여 최소 값을 구한다. solved.ac를 보니 너무 DP랑 graphs만 풀었나 싶어서 greedy도전,, 시도 1 ) 처음에 괄호를 여러개 쓸 수 있는 것을 간과해서 괄호를 어디서 끝내야하는지 고민하느라 시간을 너무 많이 써버렸다..ㅜ 괄호 개수의 제한이 없기 때문에 -값이 커질 수 있게 다 괄호로 만들었다. 3 - 5 + 7 - 9 + 15.. 2022. 10. 5.
[백준/파이썬] 1005 : ACM Craft 문제 : https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 요약 : 각 건물의 건설시간과 선후관계가 주어졌을 때, 특정 건물을 짓는 최단 시간을 구한다. 오랜만에 백준을 푸려니 개념이 가물가물했다..... 제대로 공부하지 않았다는거겠지 눈물을 뒤로 하고 이론부터 정리하고 간다,,, 다음엔 DP문제 시간 단축한다 즌쯔..... ※ 아직 공부하는 과정에 있어 틀린 말이 많을 수 있음... 1. 위상정렬(Topology Sort) 위상정렬은.. 2022. 10. 5.