전체 글 (62) 썸네일형 리스트형 13549번 - 숨바꼭질 3 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 13549번 - 숨바꼭질 3을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/13549 [문제 접근]저는 이 문제를 풀지 못했습니다. 정확히는 방향성을 잡지 못했습니다. 항상 유형별 문제만 풀다가, 유형을 모르는 문제를 풀려고 하니까 방향성을 잡기가 어렵네요.처음에는 그리디로도 생각했다가,, DP도 생각했는데, 정당성 그리고 점화식을 세울 수가 없더라구여.1시간을 고민 끝에 결국 문제 관련 자료를 찾아보았고, 그래프와 관련된 문제라는 것을 알 수 있었습니다.그래서 저는 BFS로 접근했고 풀어냈습니다!.근데 이 문제를 BFS로 풀어서 맞춘 것은 순전히 우연이었습니다. 이 문제는 우리가 알고 있는 BFS를 단순히 사용해.. [백준/C++] 알고리즘 2011번 - 암호 코드 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 2011번 - 암호 코드를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/2011 [문제 접근]읽어보면 이전상황을 이용해 현재 상황을 구한다는 느낌이 옵니다.즉 패턴을 발견할 수 있습니다. 동일한 구조의 작은 문제들의 해법을 이용해 동일한 구조의 큰 문제의 해법을 구할 수 있습니다.즉 다이나믹 프로그래밍 냄새를 술술 풍깁니다. [풀이 전략]다이나믹 프로그래밍의 첫번째 단계는 점화식 정의입니다.저는 dp[i]를 i번째까지 해석가짓수로 정의하였습니다.왜냐구여? 일단 가장 문안하게 정의내렸습니다.이렇게 했는데 점화식이 안구해지면 그에 맞춰서 dp[i] 정의를 다르게 하거나 dp[i][j] 정의로 변경하면 됩니다. i번째 .. [백준/C++] 알고리즘 9655번 - 돌 게임 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 9655번 - 돌 게임 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/9655 [문제 접근]여러가지 접근 방법이 있지만, 다이나믹 프로그래밍을 연습하는 목적으로, 다이나믹 프로그래밍 방법을 시도하였습니다.이 문제가 다이나믹 프로그래밍 냄새를 풍기는 부분이 있습니다. 바로 현재 상황 n을, n-1 이전 상황 혹은 n-3 이전 상황을 이용하여 구할 수 있기 때문입니다. 그래서 구체적으로 다음 스텝은 뭐냐구여?.점화식 정의를 해야합니다.저는 처음에 풀이를 했을 때 점화식 정의를 잘못하여 풀었는데 풀리는 이상한 상황이 발생하였습니다. 저는 dp[i]를 "i번째 돌이 남았을 때 이기는 사람"이라고 정의를 했습니다.n-1이전상.. 이전 1 2 3 4 ··· 21 다음
