dynamic programming 5

[BOJ/11053/Golang&Python] 백준 11053 - 가장 긴 증가하는 부분 수열

[BOJ/11053/Golang&Python] 백준 11053 - 가장 긴 증가하는 부분 수열 문제로 이동하기 https://www.acmicpc.net/problem/11053 접근 방식 가장 긴 증가하는 부분 수열은 Longest Increasing Subsequence 라고도 합니다. 줄여서 LIS라고 하는데요. 대표적인 다이나믹 문제입니다. 이 문제는 1차원 배열로도 풀 수 있습니다. 계단수 문제나 123 더하기 5번 문제처럼 2차원 배열을 사용하지 않아도 되는 이유는 이미 있는 수를 사용하기 때문입니다. 즉, 계단수 문제나 123 더하기 5 문제처럼 마지막에 누가 와야할지 알 수 없는 경우에는 마지막에 올 수를 기록하기 위해 이차원 배열을 사용했지만, LIS의 경우, 어떤 수가 오더라도 해당 수..

PS/BOJ 2021.06.23

[BOJ/11053/Golang&Python] 백준 11053 - 가장 긴 증가하는 부분 수열

[BOJ/11053/Golang&Python] 백준 11053 - 가장 긴 증가하는 부분 수열 문제로 이동하기 https://www.acmicpc.net/problem/11053 접근 방식 가장 긴 증가하는 부분 수열은 Longest Increasing Subsequence 라고도 합니다. 줄여서 LIS라고 하는데요. 대표적인 다이나믹 문제입니다. 이 문제는 1차원 배열로도 풀 수 있습니다. 계단수 문제나 123 더하기 5번 문제처럼 2차원 배열을 사용하지 않아도 되는 이유는 이미 있는 수를 사용하기 때문입니다. 즉, 계단수 문제나 123 더하기 5 문제처럼 마지막에 누가 와야할지 알 수 없는 경우에는 마지막에 올 수를 기록하기 위해 이차원 배열을 사용했지만, LIS의 경우, 어떤 수가 오더라도 해당 수..

PS/BOJ 2021.06.20

[BOJ/17070/Golang] 백준 17070 - 파이프 옮기기 1

문제로 이동하기 https://www.acmicpc.net/problem/17070 여담 오랜만에 DP를 풀어봤습니다. 솔직히 요즘 BFS만 공부하다보니 DP에 소홀해져서 많이 걱정했는데, 스스로 이 문제를 풀게 돼서 정말 기쁘고 행복(?)했습니다! ㅋㅋㅋ 아.. 진짜 예제 입력들 전부 넣어보고 마지막 답이 정확하게 일치하는 거 보고 현실로 탄성을 질렀습니다 ㅋㅋㅋ... 잡설이지만 정말 기뻤답니다 🙂 접근 방식 우선 점화식을 세워봐야 합니다. 다른 어려운 문제들에 비해선 점화식을 세우기 쉬운 편인 것 같았습니다. 처음에는 너무 단순하게 생각해서 D 배열을 이렇게 정의했습니다. D[i][j] = 파이프의 끝자락이 (i, j)에 위치하도록 이동시키는 방법의 수 이렇게 점화식을 세우고 문제를 접근해보니 일단 ..

PS/BOJ 2021.06.06

[BOJ/12969/Golang] 백준 12969 - ABC

접근 방식 앞선 포스트에서 소개한 14238번 문제인 '출근 기록' 문제와 유사한 문제입니다. 문제의 조건 하루에 한 명씩 출근한다. 문자열의 길이 = 출근 기록의 길이(N) A는 본인 스스로 짝을 이룰 수 없다. B는 A와 짝을 이룰 수 있다. C는 A, B 모두와 짝을 이룰 수 있다. 반드시 필요한 조건만 정리해보면, 문자열의 길이인 i가 필요합니다. 또한 A가 몇 개 있는지, B가 몇 개 있는지, C가 몇 개 있는지 알아야 합니다. 마지막으로 쌍의 개수를 계속 체크해주어야 하므로, 쌍의 개수도 나타나야 합니다. 그런데 여기에서 변수를 하나 줄일 수 있습니다. 바로 C인데요. C의 개수는 전체 문자열의 길이에서 A의 개수와 B의 개수를 빼준 크기입니다. 따라서, 실질적으로 사용하게 되는..

PS/BOJ 2021.05.24

[BOJ/14238/Golang] 백준 14238 - 출근 기록

접근 방식 이 문제는 앞으로 정리할 문제인 12969번의 ABC 문제와 유사한 문제입니다. 아무리 생각해도 점화식이 떠오르지 않아 강의를 듣고 이해한 내용을 정리해봅니다. 문제의 조건 하루에 한 명씩 출근한다. 문자열의 길이 = 출근 기록의 길이(N) A는 매일 출근이 가능하다. B는 출근한 다음 날에는 쉬어야 한다. C는 출근한 다음 날과 다다음 날은 쉬어야 한다. 반드시 필요한 조건만 정리해보면, A가 출근한 횟수, B가 출근한 횟수, C가 출근한 횟수가 필요합니다. 또한 B와 C처럼 전날과 전전날의 출근자를 알아야만 상황이 정의되는 사람을 표현하기 위해 전날 출근자(P1)와 전전날 출근자(P2)의 정보도 필요합니다. 참고로 12969번 ABC 문제는 전체 문자열의 길이를 알고 A와 B의 개수가 정해..

PS/BOJ 2021.05.23