728x90 백준플래/Tree3 백준 9202, Boggle 개요 문제 링크 플래 5, Tree, Trie 가로 세로 대각선 방향의 이동만을 통해 문자가 구성가능한지 확인하기 접근 Trie로 풀었는데 다른 풀이가 있는지 다른 사람들과 시간차이가 많이 났다. 일단 잘 맞췄음에 의의를 둬보자. 처음에는 찾으려는 문자열의 trie를 만드는 줄 알았다. 어떤 문자열 S를 구성 가능하다는 것은 S를 포함하는 문자열에서 S만큼을 건너뛰어도 된다는 것이라 그때마다 찾아주려했는데, 매 위치마다 길이가 1부터 7인 꼬리문자열에 대해 trie를 찾아줘야 하니까 여간 번거로운게 아니었다. 그래서 그냥 맵 전체의 경우의 수를 trie에 저장하기로 했다. 그리고 문자열마다 trie를 돌려주면 끝. 핵심을 알면 나머지 로직은 단순하다. 팁이라면 score계산을 할 때 아래처럼 해주면 한 .. 2023. 3. 7. 백준 4315, 나무 위의 구슬 개요 문제 링크 플래 5, Tree, DFS 모든 정점의 값이 1이 되도록, 수를 1씩 이동하는 최소 횟수 접근 Tree와 DP, 개꿀잼코스 두개가 묶였다. 사실 DP라기보다는 그리디에 가까운 문제인듯 하다. 문제가 얼핏 어려워보이는데, 그냥 음수 값을 인정해버리면? 문제가 단순해진다. 이때의 핵심은 리프노드를 1로 만들기가 된다. 리프노드가 1이 되면 고려할 필요가 없고 잘라버리면 되기 때문이다. 이게 왜 될까? 아래 예시를 보자. // [left, root, right] 0 0 3 -> 0 2 1 -> 1 1 1 2+1번, 총 3번의 시행이 필요하다. 이때 부모노드가 자신이 갖지 않은 값을 왼쪽 자식에게 빌려준다고 생각하자. 0 0 3 -> 1 -1 3 -> 1 1 1 왼쪽 리프노드를 먼저 1로 만들.. 2023. 3. 6. 백준 19585, 전설 개요 문제 링크 플래 3, Trie Q개의 문자열이 C,N개의 문자열의 합으로 구성가능한지 확인하기 접근 56트 끝에 AC받은 비운의 문제. 공부가 더 필요해 보인다. 풀이 방법은 여러가지가 있겠지만 대표적인 방법은 정배열 / 역배열로 끝점체크해주고 두 끝점의 좌표차이가 1이 나면 Yes인 방법이 있다. 내가 주로 사용한 방법은 정배열 / map을 이용하는 것인데 훨씬 간단하고 이해가 쉽다. 색상의 끝점에서 이름이 유효한지 확인하는 것이다. 트리는 메모리 초과를 잡을 방법을 모르겠어서 포기하고 그냥 배열을 이용했다. 색상의 400만개 노드에 대해 26개 다음점을 저장하고, 끝점 여부를 저장한 뒤 끝점에 도달하면 map에 저장된 닉네임이 있는지 확인해주면 된다. Pseudo code rc = root_of.. 2023. 2. 22. 다음 728x90