본문 바로가기

개발/알고리즘

 (64)
[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. 재귀함수를 이용한 풀이법. 이 문제는 각 경우에 마다 쭈우욱 가본 결과의 경우들을 모아서 그 중에 최대의 결과를 구하는 문제이다. 그랬을 경우, 백트래킹과 같은 방식을 사용하여 모든 경우를 파악해야했다. 그렇다면 문제를 풀 때 재귀함수..
[BOJ] 영역 구하기_2583 이 문제를 보았을 때, 15분 안에 정답 풀이법을 생각해 냈다. 하지만 제출해서 정답을 얻는데 까지는 40분 정도가 소요됐다. 풀이법을 코드로 풀어내는 데에 걸리는 시간이 20분 정도가 되었고, 오타 하나를 찾는데 걸리는 시간이 20분 정도가 되었다. 오타가 정말 문제다. 이건 아마 내가 변수명을 대충 지은 탓이 크다. 변수명을 어떻게 지어야 할까..? 나중에 코테를 볼 때도 변수명을 보긴 할거같은데,, 이런건 다른 사람에게 조언을 한번 구해보자.
[BOJ] 안전 영역_2468 이 문제는 푸는 생각을 하는데 까지 15분도 걸리지 않은 것 같다. 어떻게 풀어야 할지 머리로 먼저 생각하였고, 결과적으론 그 생각이 바로 맞았었다. 몇일 전까지만 해도 전혀 감이 안잡혔는데 생각보다 빨리 문제에 대한 감이 생기는 것 같다. 하지만 문제를 풀고 제출하는데 까지는 시간이 1시간도 넘게 걸렸다. 그 이유는 파이썬에 대한 몇가지 몰랐던 문법과 작은 실수들 때문이였다. 파이썬 문법 몰랐던 것 단순 객체복제 data = [1] data2 = data data2[0] = 2 이렇게 한다면 data2는 data변수를 단순히 복사한 것이기 때문에 둘다 가르키는 방향이 동일하다. 그러므로 data2의 값을 바꾸면 가르키는 객체의 내용이 바뀌는 것이기 때문에 둘다 값이 동일하게 바뀐다. 깊은 복사와 얕은 ..
[BOJ] 유기농 배추_1012 이 문제를 푸는데에는 30분이 걸리지 않았지만, 오류 때문에 오랜 시간이 걸렸다. if 0
[BOJ] 1697 숨바꼭질 문제는 수빈이가 동생을 +1, -1, *2 세 가지의 움직임을 통해 가장 빠르게 찾을 수 있는 횟수를 구하는 것이다. 처음에는 이것이 bfs랑 무슨 연관인거지? 생각하고 IF문을 마구잡이로 쓸 생각 밖에 나지 않았다. 문제 풀이를 보고나서, 풀이의 핵심은 visited배열을 MAX(100001)만큼 만든 것을 통해 해결하려고 한 것이다. 수빈이가 움직일 수 있는 범위를 최대 MAX로 둔 것에 착안하여 움직인 위치에 방문 횟수를 기록하는 방식이다. 현재 수빈이의 위치를 Queue에서 pop한 후, 세 가지 동작에 대하여 아직 방문하지 않았고, 범위를 초과하지 않았다면 이동한 visited배열에 이동하기 전 visited배열의 값 +1 을 넣는다. 아직도 헷갈리는 것은 visited가 왜 0이면 안되는걸까?..

티스토리툴바