본문 바로가기

전체 글

 (131)
[python] 문자열 다루기 보호되어 있는 글입니다.
[BOJ] 쉬운 계단_10844 단계를 거듭할 수록 각각의 해당하는 숫자에 +1, -1을 한 값에 여태까지 나왔던 숫자들의 합을 더해주는 식이다.
[BOJ] 연속합_1912 이 문제는 쉽게 해결될 줄 알았는데 풀이를 보고도 어렵다고 느꼈다. 결론부터 보자면, dp.append(max(dp[i-1] + data[i], data[i])) 이 부분은 다시 봐도 정확히 이해가 되지 않는다. 저 한줄의 코드가 각 항 마다, 이전까지 더한 값이 더 크냐 or 현재 값이 더 크냐를 의미한다. 하지만 저것이 어떻게 모든 경우의 수를 고려해준 것일까?? dp[i] = max(dp[i-1]+data[i], data[i])에서 dp[i-1]은 이전까지 구한 값 중 최대의 값을 만들어낸 값이다. 그 전까지 더했을 때, 더 이득이 되는 것만 값을 더했기 때문이다. 그러한 값과 현재의 값을 더했을때와 더하지 않았을 떄의 값을 비교해서 최대값을 구하는 것이다.
[BOJ] 포도주 시식_2156 dp문제는 수능 수학에서 수열 문제와 비슷한 것 같다. 수능 수열 문제처럼 a1, a2..a4정도 까지 구해본 다음, 그 속에서 규칙을 찾아내 문제를 해결하는 것이다. 물론 그 규칙이 생기는 논리적인 이유를 통해 유추할 수 있지만, 처음 접근 방식을 수능 수열처럼 해보자. 그리고 배열에 값을 초기화할 때, 무조건 쓰던 방식만 생각하지 말고 그때그때 필요한 방식을 적용하자.
[BOJ] 계단 오르기_2579 DP문제를 풀 때 넘어야 할 산은 이게 모든 것을 고려해 준 것인가?를 판단하는 능력인 것 같다. 분명 어떤 식으로 풀어야 할지는 알겠으나, 풀이를 보고서도 이게 모든 것을 고려해준 것이 맞나?라는 생각이 든다. 해다아 코드는 문제 풀이이다. 이것을 보고 전체를 고려해 준 것이 맞나?라는 생각이 들었고,, 뭔가 맞는거 같기는 하다.. 근데 무언가 확신은 들지 않는다... 이 문제를 푸는데에 가장 중요했던 점이 무엇일까?? 바로 고려해 줘야 할 포인트인 것 같다. dp[i] = max(dp[i - 3] + data[i - 1] + data[i], dp[i - 2] + data[i])에서 dp[i - 3] + data[i - 1] + data[i] -> 이 부분은 모든 것을 고려해 준 것이 맞다. dp[i-..
[BOJ] RGB거리_1149 이 문제는 두개의 경우 씩 나눠서 고려해준 것이 전체를 고려해준다는 것을 파악하는게 중요한 문제이다. 이런 식으로 두 번째 배열에 모두 해당 배열이 택해졌을 때, 가지는 최소 값들을 구하는 식으로 내려간다면 최소 값을 고려해준 것이 된다. 배열 세 번째 에서는 이미 계산된 두 번째 배열을 선택해주면 된다. 그게 코드에서는 이런 식이다. 나는 세 번째 배열도 첫 번째 배열에 영향을 끼치는 줄 알고 몇 개씩 끊어서 생각해줘야 하나 고민을 많이 했었다. 그럴수록 문제는 점점 산으로 갔다. 이 문제의 핵심 포인트느느 다음 배열이 하나를 선택했을 때, 이전 배열의 나머지 원소 값 중 더 작은 것을 더해 나아가는 방법이다.
[BOJ] 촌수계산_2644 이 문제는 풀지 못하였다. 풀이법에 대해서도 생각하지 못하였다. 대충 트리를 활용해서 풀 수 있을 것이라 생각했다. 해당 그림의 트리는 자식에 대한 정보만 가지고 있고, 부모에 대한 정보는 없었다. 왜 이렇게 그린거지,,,? 저렇게 그린 후, 7을 가지고 있는 배열의 인덱스를 찾아서,,,어쩌구,,, 무튼 산으로 갔다. 풀이법을 본 후, 코드를 보며 그려본 것이다. 그냥 트리를 만드는 방식이 잘못됐겠거니~했지만 count를 큐에 넣어야 하는 방식은 생각하지 못했을 것 같다. 큐에 count를 넣는 이유는 해당 노드까지 몇 단계를 거쳤나 저장해 놓기 위해서이다. bfs로 모든 곳을 탐색하는 방식인데, 전부 다 count해버리면 안되니까,,, 그런 것 같다. 어떻게 이걸 생각하지?,,,
[BOJ] 알파벳_1987 이 문제는 풀지 못하였다. 해설을 보고 어떻게 푸는지를 보았고, 내가 모르는 부분들에 대해 정리해야겠다. 몰랐던 부분 1. 람다식을 통한 배열 만들기 graph = [list(map(lambda x: ord(x)-65, input())) for _ in range(n)] input()으로 입력 받은 값을 람다와 딕셔너리를 이용해서 숫자로 바꾼 리스트 값을 n 만큼 추가하였다. 지금 다시 봐도 생소한 느낌이다. 앞으로 파이썬 배열을 초기화할 때, 컴프리헨션으로 만들자. 2. 재귀함수를 이용한 풀이법. 이 문제는 각 경우에 마다 쭈우욱 가본 결과의 경우들을 모아서 그 중에 최대의 결과를 구하는 문제이다. 그랬을 경우, 백트래킹과 같은 방식을 사용하여 모든 경우를 파악해야했다. 그렇다면 문제를 풀 때 재귀함수..

티스토리툴바