분류 전체보기361 [BOJ]1039번: 교환 문제: https://www.acmicpc.net/problem/1039 BFS 문제입니다. 예외조건 때문에 많이 틀렸네요. 세 가지 주의점이 있습니다. 1. 바뀐 후의 숫자가 0으로 시작하면 안됩니다. 2. 10,20,30처럼 두 자리수이면서 0으로 끝나는 숫자는 Swap하면 안됩니다. (단, 100,1000,10000 같은 숫자들은 괜찮습니다. 0 끼리 바꾸면 되니까요) 3. 총 K번 Swap 회차만큼 Swap을 할텐데, 각 회차가 될 때 마다 방문배열을 초기화해줘야 합니다. 무슨 말이냐면 이전에 나왔던 숫자가 나중에 나와도 됩니다. 이를 위해서 저는 매 루프를 while (!q.empty()) 가 아니라 while (q.size()--) 만큼만 돌았습니다. 코드: https://github.com/.. 2020. 8. 13. [2020 카카오 기출] 가사 검색 문제: https://programmers.co.kr/learn/courses/30/lessons/60060 참고 링크: https://shjz.tistory.com/99 shjz님의 블로그 글을 참고해서 해결했습니다. 중요한 점은 3가지 입니다. 1. 트라이 사용 문제 2. 정방향 트라이와 역방향 트라이를 사용 3. 문자열 길이만큼 트라이배열을 만들어서 사용 1. 트라이 사용 문제 각 문자열에 대한 판단을 O(M) (M: 문자열의 길이)에 끝내기 위해 트라이를 사용합니다. 2. 정방향 트라이와 역방향 트라이를 사용 '?'(와일드 카드 식별자)가 중간에 나오지 않는다는 뜻은 '?'가 나온 시점에는 나머지 탐색에 대한 처리가 상수 시간에 끝나야 합니다. 그렇게 처리하지 않고 26(알파벳 크기)^(남은 문자.. 2020. 8. 12. [BOJ]4195번: 친구 네트워크 문제: https://www.acmicpc.net/problem/4195 단순 DFS로 탐색하면 시간초과로 터지는 문제입니다. Union & Find를 통해 해결했습니다. 풀이는 jason님 (https://jason9319.tistory.com/41) 링크를 참고했는데요. 일반 Union & Find 보다 한 단계 더 나아가 자식의 숫자를 저장하고 있어야 합니다. 그러므로 문제가 생기는 부분이 있습니다. 바로 friend1, friend2 로 들어오는 관계가 이미 부모 - 자식 관계인 경우 입니다. BEFORE의 경우 무조건 부모쪽에 더하도록 만들어주었고, AFTER는 부모 - 자식 관계인 경우 부모를 리턴, 부모 - 자식 관계가 아닌 경우 더하도록 만들었습니다. BEFORE 코드가 문제가 되는 이유는.. 2020. 8. 11. [2020 카카오 기출] 블록 이동하기 문제: https://programmers.co.kr/learn/courses/30/lessons/60063 시뮬레이션 문제입니다. 따져줄 게 참 많아보이는 문제입니다만 아래 두 가지에 대해서만 잘 정하고 풀면 됩니다. 1. 상태를 어떻게 저장할 지 2. 다음 좌표 탐색을 어떻게 할 지 우선 편의를 위해 블록의 2칸 중 한 칸을 HEAD, 다른 한 칸을 TAIL이라고 하겠습니다. 우리는 (HEAD_Y, HEAD_X, TAIl_Y, TAIL_X)로 4개의 정보가 필요하지만 이는 (HEAD_Y, HEAD_X, HEAD가 TAIL과 연결되어 있는 방향) 3개 정보로 똑같이 표현할 수 있습니다. 그래서 상태를 어떻게 저장하느냐에 대해서는 (HEAD_Y, HEAD_X, Direction)으로 표현하겠습니다. (b.. 2020. 8. 11. 이전 1 ··· 57 58 59 60 61 62 63 ··· 91 다음
