본문 바로가기

백준177

[Swift][BruteForce] 백준 14889번(스타트와 링크) 요구능력 : 백트래킹에 대한 이해 코드설명 : 이 문제는 팀을 n명중에서 n/2명을 뽑아야된다는게 핵심이다. 그래서 나는 n과 m을 떠올려서 백트래킹 방법으로 팀부터 뽑았다. 다음으로, 내가 스타트팀원들을 뽑았으니까 링크팀원들은 자동적으로 스타트팀원들을 뺀 사람들이 되겠다. 스타트팀원들을 n/2명을 뽑으면 맨 아래 for문에서 방문처리가 되게된다. 그럼 방문처리가 안된 사람들이 링크팀원들인 것이다. n/2명을 뽑았을 때 team1과 team2를 0으로 초기화해준다.(이전에 뽑았던 값을 재사용하게 되는 경우가 없게하기 위함) 그리고 for문으로 arr배열의 전체 인덱스를 돌아주면서 방문하지 않은것은 링크팀(team2)원들이기 때문에 방문하지 않은경우에 team2에 더해주고 방문했다면, 맨 아래에서 뽑은 스.. 2021. 11. 4.
[Swift][BruteForce] 백준 6603번 (로또) 요구능력 : N과M에 대한 이해 코드설명 : 문제를 보면 N과M시리즈와 매우 유사하다. 1. N개의 수 중에서 6개를 뽑는다. 2. 비내림차순 1. 문제의 조건을 맞춰주는 부분 문제에서는 0이 입력되기전까지 계속해서 받으라고 했으므로 while문으로 처리를 해준다. 그리고 배열에서 맨 앞의수는 필요없으니 버려준다.(어차피 N개의 수에서 6개만 뽑아서 오름차순해줄것이기 때문이다.) while true{ input = readLine()!.split(separator: " ").map{Int(String($0))!} if input[0] == 0 { break }else { input.removeFirst() dfs(0, 0) print("") } } 2. 백트래킹을 이용해서 N개의 수중 6개를 뽑아준다. .. 2021. 11. 2.
[Swift][DP] 백준 15988번 (1, 2, 3더하기 3) 요구능력 : DP에 대한 이해 코드설명 : 문제를 설명해주면 1과 2와 3중 한개 이상을 더해서 주어진 수를 만드는 문제이다. 처음 접해보시는 분들은 어렵게 느껴질 수도 있는데, 이 문제만 정확히 이해하면 다른 더하기 DP문제들은 꽤 쉽게 풀릴것이다. 그림을 보면 파란색글씨로 + 1, + 2, +3 을 해놓은것을 볼 수 있다. 1, 2, 3더하기니까 이렇게 1, 2, 3을 기준으로 앞에 들어와야 할 수를 구해준다. 이게 가능한건 DP이기 때문에 가능하다. +1, +2, +3앞에 오는 수가 무엇이든간에 이미 1과 2와 3의 조합으로만 더해놨기 때문이다. 위의 그림에 5를 보면 이전에 4를 1과 2와 3의 조합으로 해놨기 때문에, 4에 조합된 개수를 그대로 가져오는걸 볼 수 있다. 이해가 안간다면 여러번보고.. 2021. 11. 2.
[Swift][DP] 백준 2225번 (합분해) 요구능력 : DP에 대한 이해 코드설명 : 이해가 정말 잘되게 해주신 블로그 우선 구해야되는 배열의 개수가 얼마안되서 그냥 처음부터 끝까지 다 구해버리고 거기서 해당되는 배열[k][n]을 뽑아냈다. 위에 태그해놓은 블로그를 먼저 보고오면 어떤식으로 풀어야할지 감이 잡힌다. 2차원배열인걸 처음에 어떻게 알고 풀지라고 생각했는데,, DP는 입력이 2개가 반드시 들어와서 찾는거라면 2차원이 아닐까.. 라는 생각을 조심스럽게 해본다. 여튼 이제 2차원으로 푸는건 위에 블로그에서 설명해주신대로 표그려서 풀어야겠다.. 후기 : 어려운거 같은데,, 알고나면 이렇게 푸는방법도 있구나 싶은 문제였다. 많은 정보중에서 내가 이 문제를 다시 봤을 때 논리적으로 풀 수 있겠다 싶은 방법으로 풀었다. let nk = readL.. 2021. 11. 1.

티스토리툴바