Algorithm/문제풀이_백준196 [Swift][구현] 백준 16931번 (겉넓이 구하기) 요구능력 구현, 수학 문제풀이 겉넓이만 구하면 되겠다고 생각하면 안된다. 울퉁불퉁(?)하기 때문에 옆에서 보는모습이 전부가 아니다. 이렇게 앞에서 봤을 때 빨간색으로 칠한부분이 옆에서는 안보인다. 이걸 어떻게 해결해야할까? 결론부터 말하자면, N*M의 겉을 0으로 둘러싸고 N*M을 4방향탐색해주면서 겉넓이를 구하면 된다. 이 배열이 저장되어있는 arr이라는 배열이 있다. 그럼, arr[1][1]부터 탐색을 시작하는거다. 빨간동그라미 부분의 4방향을 탐색해보자. 왼쪽 0, 위 0, 오른쪽 3, 아래 2이다. 인접한부분의 값이 자기자신보다 작으면 겉넓이를 더해준다. 직접 해보면 이해가 가겠지만 왼쪽 0이라서 1이더크니까 겉넓이가 1이 더해질것이다. 그럼 이 겉넓이는 왼쪽면에서 더해지는 겉넓이라고 생각하면 된.. 2022. 5. 13. [Swift][비트마스킹] 백준 1062번 (가르침) 요구능력 조합, 비트마스킹 문제풀이 나혼자 처음에 이해를 못한건가 싶기도한데.. anta tica를 기본으로 깔고 중간에 있는 단어들중에서 k개를 배운다는줄 알았다. 그게 아니고 anta tica포함 k개였다. C++언어로는 완탐조합만 돌려도 시간초과가 나오지 않을것이다. 하지만, 스위프트로 풀기위해서는 비트마스킹을 사용해야한다. 1) 문장을 입력받을 때 각 문장마다 단어를 비트마스킹으로 추가해줬다. for i in 0.. 2022. 5. 11. [Swift][브루트포스] 백준 2143번 (두 배열의 합) 요구능력 해시, 브루트포스 문제풀이 부분합 문제는 연속되서 브루트포스를 하게되면 n^2의 시간복잡도를 가지게되고, 연속되지않게 부분수열과 같은 문제가나오면 2^n의 시간복잡도를 가지게 된다. 이 문제는 연속되기 때문에 편하게 푸려면 브루트포스를 생각해봐야한다. n과 m이 1000이하이므로 n^2을 시도해봐도 괜찮을 것같다. 부분합을 구해주면서 dictionary에 해당 부분합이 나오는 개수를 저장을 해준다. 반으로 쪼개지는 않았지만, 이것도 중간에서 만나기 개념이 살짝 사용되는거같은데..?(아닌가) 그리고 나머지부분합을 구하면서 해시를 이용하여 목표값을 달성하는 개수를 result에 누적해준다. 후기 이전 문제랑 비슷하게 풀리는데.. 이건 연속된 배열이고, 이전 문제는 연속되지 않기때문에 2^n 코드 l.. 2022. 5. 10. [Swift][이분 탐색][중간에서 만나기] 백준 1208번 (부분수열의 합 2) 요구능력 해시와 이분탐색 문제풀이 일반적인 부분수열의 합으로 풀기에는 시간복잡도가 2^40까지 나와서 시간초과가 나오게된다. 2^40이 나오는 이유는 이 문제는 더하기, 더하지않기라는 경우의 수밖에 없기때문이다. 그렇다면 어떻게 풀어야할까? 나는 여기서 중간에서 만나기라는 개념을 처음 접했는데, 대충 이런개념인것같다. 반을 쪼개서 해시로 dictionary에 값들을 저장해주고, 나머지 반에서 값들을 구하면서 (목표값 - 구한값)을 해시에 저장된 값에서 가져오면 중간에서 만나는(?) 개념이 성립되는것 같다. 그리고 문제에서는 크기가 양수인 부분수열이라고 했는데, 아래와 같이 재귀로 sum을 계속 들어가면 하나도 더하지않는 경우(공집합)가 생기므로 s가 0인경우에는 공집합이 생기는 경우를 제거해야한다. 후기.. 2022. 5. 10. 이전 1 2 3 4 5 6 7 8 ··· 49 다음
