본문 바로가기

Algorithm272

[ 파이썬(python) ] 백준 9625 - BABBA 📌 백준 9625 - BABBA 백준 9625 - BABBA 💡 나의 풀이 전형적인 DP(Dynamic Programming)문제였으나, 처음에 문제 그대로 i가 증가하면 바뀌는 문자열을 새로운 배열에 넣고 마지막에 총 몇 개인지 count를 사용하여 풀다가 시간 초과 판정을 받았다. 그래서 어떤 규칙이 있는지 살펴보니까 전체 A, B 총 개수를 구할 필요는 없고 A, B의 개수를 따로따로 구하면 된다. a[i] = a[i-1] + a[i-2]인 전형적인 피보나치(Fibonacci) 수열 형태를 보였다. 나는 DP를 사용할 때 전체 k의 최대값를 선언했는데, 그럴 필요 없이 k+1만큼만 줘서 그때그때 계산해도 된다. 또, 새롭게 배운 점은 a[0] = 1, a[1] = 0 대신, 처음부터 a=[1,0]을.. 2021. 5. 21.
[ 파이썬(python) ] 백준 4396 - 지뢰 📍 백준 4396 - 지뢰 백준 4396 - 지뢰 ⚡️ 나의 풀이 상당히 고생한 문제다. 이 문제를 맞히기 위해 정답을 얼마나 제출했는지 모르겠다. 난이도가 실버 5 였기 때문에 쉽게 풀 줄 알았는데 큰 코 다쳤다. 처음 짰던 코드는 접근 자체를 잘 못했다. 이때까지 n*n 행렬을 초기화 시킬때 무조건 0으로 했는데, 꼭 그렇게 할 필요 없다는 생각이 이 문제를 풀면서 떠올랐다. 이 문제에 다른 모든 지점이 온점(.)으로 표시되어야하는 조건에서 result의 초기값을 .으로 해주면 됐었다. 또, 문제를 완벽하게 이해하지 못했는데, 지뢰가 있는 칸이 열렸다면 지뢰가 있으면서 열린 칸만 별표(*)로 표시하는것이 아니고, 지뢰가 있는 모든 칸이 별표(*)로 처리되어야한다. 도저히 모르겠어서 질문까지 남겼는데 .. 2021. 5. 20.
[ 파이썬(python) ] 백준 1110 - 더하기 사이클 📍 백준 1110 - 더하기 사이클 백준 1110 - 더하기 사이클 ⚡️ 나의 풀이 문제의 조건대로 구현하면 되는 문제인데, n번 사이클을 돌고 나서 원래의 수와 같아지는 조건식을 잘못 넣어서 조금 헤맸다. 결론적으로 처음 입력을 새로운 변수 check로 선언하고 제일 마지막에 나온 값과 비교해주면 됐다. 또, 처음 조건에 주어진 수가 10보다 작으면 앞에 0을 붙인다고 나와있는데, 사실 이 조건은 없어도 되는 조건이다. 예를 들어 처음 주어진 수가 5라고 할 때, 앞에 0을 붙여주고 각 자리의 숫자를 더하면 0+5가 되는데, 0은 있으나 없으나 같은 값이 되기 때문이다. 따라서 해당 조건은 건너뛰고 생각하면 된다. 여담이지만 각 자리의 숫자를 더하는 방법은 다음과 같다. 재귀함수를 이용해서 10으로 나.. 2021. 5. 18.
[ 파이썬(python) ] 백준 7568 - 덩치 📍 백준 7568 - 덩치 백준 7568 - 덩치 ⚡️ 나의 풀이 언젠가 단계별 풀이에서 한번 봤었는데, 어떻게 풀어야 할지 몰라 넘겼었는데 이번엔 풀었다. 이 문제의 가장 핵심 문장은 각 사람의 덩치 등수는 자신보다 더 큰 덩치의 사람의 수로 정해진다.이다. 이중 반복문의 범위는 A-B, A-C, A-D, A-E / B-A, B-C, B-D, B-E / C-A, C-B, C-D, C-E / E-A, E-B, E-C, E-D 처럼 모든 경우의 수를 비교할 수 있게 선언해야 한다. A-B나 B-A나 같은거아닌가?! 라고 생각할 수도 있지만, 각각의 케이스에서 덩치 등수를 셀 때 나를 제외한 모든 사람의 덩치를 비교해야 하기 때문에 같지 않다. 자신을 포함한 모든 경우의 수를 조사한다.(반복문의 범위 설정의.. 2021. 5. 18.
[ 파이썬(python) ] 백준 4673 - 셀프 넘버 📍 백준 4673 - 셀프 넘버 백준 4673 - 셀프 넘버 ⚡️ 나의 풀이 문제는 대충 이해됐지만, 막상 코드로 표현하려니까 막막했다. 시작 범위를 어디서부터 잡아야 하는지도 잘 몰랐는데, 많은 고민 끝에 다음과 같은 방법을 생각했다. 생성자가 없는 숫자를 셀프 넘버라고 칭하니까 생성자가 있는 숫자들을 구하고 새로운 리스트에 담아주자. 전체 1 ~ 10000까지의 리스트를 초기화하고, 생성자가 있는 숫자들을 모두 빼면 나머지 값은 모두 셀프넘버가 된다. 문제에 10000보다 작거나 같은 셀프넘버라고 나와있으니까. 종료 범위는 10000이고, 시작 범위는 문제에 양의 정수 n에 대해 계산한다고 나와있으므로 1부터 시작한다. 또, 이와같이 생각했음에도 답이 도출되지 않았는데 원인은 target.append.. 2021. 5. 18.

티스토리툴바