골드3 [Swift][브루트포스] 백준 2143번 (두 배열의 합) 요구능력 해시, 브루트포스 문제풀이 부분합 문제는 연속되서 브루트포스를 하게되면 n^2의 시간복잡도를 가지게되고, 연속되지않게 부분수열과 같은 문제가나오면 2^n의 시간복잡도를 가지게 된다. 이 문제는 연속되기 때문에 편하게 푸려면 브루트포스를 생각해봐야한다. n과 m이 1000이하이므로 n^2을 시도해봐도 괜찮을 것같다. 부분합을 구해주면서 dictionary에 해당 부분합이 나오는 개수를 저장을 해준다. 반으로 쪼개지는 않았지만, 이것도 중간에서 만나기 개념이 살짝 사용되는거같은데..?(아닌가) 그리고 나머지부분합을 구하면서 해시를 이용하여 목표값을 달성하는 개수를 result에 누적해준다. 후기 이전 문제랑 비슷하게 풀리는데.. 이건 연속된 배열이고, 이전 문제는 연속되지 않기때문에 2^n 코드 l.. 2022. 5. 10. [Swift][BFS] 백준 2234번 (성곽) 요구능력 : BFS 코드설명 : 1) 이 성에 있는 방의 개수 BFS를 도는 횟수가 방의 개수가 되겠다. BFS를 한번 돌게되면 벽에 막혀서 방문이 끝나게 된다. 방문하지 않은 곳의 배열을 모두 돌면서 방문처리를 해준다면 bfs를 도는 수 만큼이 방의 개수가 되겠다. 2) 가장 넓은 방의 넓이 큐에 append할 때 마다 방의 넓이는 count를 증가시켜줘야한다. 큐에 넣을때마다 증가시켜주지 않고 큐에 이동횟수를 붙여서 세게되면 모든 칸의 수를 다 세야하는데 아래와 같이 모든 경우의 수를 세지 못한다. 3) 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 마찬가지로 2진수를 이용하여 있는 벽만 하나씩 지워보면서 arr을 전부 돌아보면된다. 후기 : 생각도 못한 &연산.. 비트연산문제를 한번도 안.. 2022. 2. 3. [Swift][DP] 백준 11057번 (오르막 수) 요구능력 : DP에 대한 이해 코드설명 : 수의 길이에 따른 오르막 수의 개수를 세는 문제이다. 오르막수는 오름차순과 비슷한데 같은 수가나와도 오르막수가 된다. 예를들면 1 2 3, 1 2 2은 오르막 수 인데, 1 2 1, 1 2 0은 오르막수가 아니다. 이 문제에서 주의깊게 봐야할 점은 004 이런것도 다 세줘야하는것이다. 수는 0으로 시작할 수 있다는게 이런의미. 수를 관리하기위한 문제는 2차원 배열을 생각하는게 좋다. 수의 끝을 기준으로 DP구하기가 수월하기 때문이다. DP[1][0]은 1자리수에 끝자리 수가 0으로 끝나는것이다. DP[3][5]는 3자리수에 끝자리 수가 5로 끝나는 것이다. DP[1][0]부터 DP[1][9]까지는 1을 삽입해준다. DP[1][0]은 1자리에 끝이 0으로 끝나는.. 2021. 11. 5. 이전 1 다음
