본문 바로가기

Algorithm283

[BOJ]5014번: 스타트링크 문제: https://www.acmicpc.net/problem/5014 BFS 문제입니다. 매 상태는 +U, -D로 두 가지로 분기됩니다. 낚일만한 요소는 F층이 최상단층이라는 것만 안 빼먹으시면 무난히 해결할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ5014.java 2020. 8. 13.
[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.

티스토리툴바