dfs32 [Swift][이분 탐색][중간에서 만나기] 백준 1208번 (부분수열의 합 2) 요구능력 해시와 이분탐색 문제풀이 일반적인 부분수열의 합으로 풀기에는 시간복잡도가 2^40까지 나와서 시간초과가 나오게된다. 2^40이 나오는 이유는 이 문제는 더하기, 더하지않기라는 경우의 수밖에 없기때문이다. 그렇다면 어떻게 풀어야할까? 나는 여기서 중간에서 만나기라는 개념을 처음 접했는데, 대충 이런개념인것같다. 반을 쪼개서 해시로 dictionary에 값들을 저장해주고, 나머지 반에서 값들을 구하면서 (목표값 - 구한값)을 해시에 저장된 값에서 가져오면 중간에서 만나는(?) 개념이 성립되는것 같다. 그리고 문제에서는 크기가 양수인 부분수열이라고 했는데, 아래와 같이 재귀로 sum을 계속 들어가면 하나도 더하지않는 경우(공집합)가 생기므로 s가 0인경우에는 공집합이 생기는 경우를 제거해야한다. 후기.. 2022. 5. 10. [Swift][프로그래머스][해시] 메뉴 리뉴얼 요구능력 조합 + 해시 문제풀이 DFS를 활용해서 조합을 사용하였고, 문제에서도 조합이라고 했기 때문에 음식의 순서는 상관없다. 그래서 sorTemp변수를 사용해서 얻어오는 조합마다 정렬해서 받았다. 이 부분이 이 문제의 변별력인것 같다. ex) XY, YX는 같은 음식조합이다. 그리고 사실 "만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다." 이 부분을 안읽고 문제를 풀다가 가 예제 2번에 AB는 왜 안되지라는 생각을 계속했는데, 2가지 메뉴구성 중에서도 가장 많이 함께 주문된 메뉴구성을 골라야했다. 가장 많이 함께 주문된 메뉴구성을 안고르고 그냥 course의 개수에 맞고 2개이상인 메뉴구성을 계속 고르다보니 문제가 안풀렸던것이다. 후기 문제의 조건을.. 2022. 4. 27. [Swift][DFS] 백준 16964번 (DFS 스페셜 저지) 요구능력 DFS와 정렬 문제풀이 https://sapjilkingios.tistory.com/entry/SwiftBFS-%EB%B0%B1%EC%A4%80-16940%EB%B2%88-BFS-%EC%8A%A4%ED%8E%98%EC%85%9C-%EC%A0%80%EC%A7%80 [Swift][BFS] 백준 16940번 (BFS 스페셜 저지) 요구능력 BFS와 정렬 문제설명 일반적인 BFS문제에 주어진 방문순서대로 방문이 가능한지를 판별하는 문제이다. 간선정보가 주어진다면 인접리스트를 고려해봐야한다. 그래서 인접리스트를 구 sapjilkingios.tistory.com 위의 BFS스페셜저지와 동일한 문제입니다. 바뀌는점은 BFS -> DFS인것 밖에 없습니다. 어려운것없이 1번노드를 먼저방문하도록 dfs(1)로 .. 2022. 3. 26. [Swift][Graph] 백준 12946번 (육각보드) 요구능력 DFS 활용 문제풀이 이분의 블로그를 참고하였다. https://astrid-dm.tistory.com/380 백준 12946번 육각 보드 (C++) 문제 링크 : www.acmicpc.net/problem/12946 12946번: 육각 보드 크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다. 육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을.. astrid-dm.tistory.com 후기 여섯방향으로 탐색해야하고 최대 3개의 색상밖에 안나온다는 것까지는 파악하기 쉬웠는데, 몇가지 예외가 생기는거 같아서 탐색의 갈피를 못잡았다. 코드 import Foundation let n = Int(String(readLine()!))! var arr .. 2022. 3. 22. 이전 1 2 3 4 ··· 8 다음