백준177 [Swift][DP] 백준 11053번 (가장 긴 증가하는 부분수열) 요구능력 : DP의 응용 코드설명 : 이 문제는 앞에있는 숫자가 자기자신보다 작은 숫자의 갯수를 세는것이다. 1. 배열에서 현재 i가 위치한 배열의 앞부분에 현재 arr[i]의 수보다 작은게 있으면 그 자리의 dp는 dp[i]와 dp[j] + 1 중 큰 수를 dp[i]에 넣는다. 그 이유는 디버깅해보면 알겠지만, [10, 20, 10, 30]과 같은 경우에 10일 때는 dp[0] = 1 20일 때는 dp[1] = 2 10일 때는 dp[2] = 1 30일 때는 dp[3] = 3 이 된다. 후기 : 증가하는 부분수열의 점화식은 처음에 구했는데 왜 답이 안나왔었는지 멀리돌아서 왔다. let a = Int(readLine()!)! var arr = readLine()!.split(separator: " ").m.. 2021. 9. 22. [Swift][문자열] 백준 10973번 (이전순열) 요구능력 : 문자열의 이해 코드설명 : 이 문제는 딱 세가지만 알면 쉽다. 첫째, 큰수 > 작은수 둘째, 내림차순 셋째, 큰수 > 작은수에서 큰수보다 작으면서 맨 마지막에 있는 인덱스 처음에 문제를 풀때 다음순열과 비슷한 방식으로 접근했다. 그래서 수를 나열 해봤는데 아래와 같은 규칙이 나왔다. . . . 1 2 4 5 3 1 2 4 3 5 1 2 3 5 4 1 2 3 4 5 우선 쭉 보면서 어디가 바뀌는지 찾아보자. 1. 1 2 4 5 3 -> 1 2 4 3 5 2. 1 2 4 3 5 -> 1 2 3 5 4 1번은 5와 3의 자리가 바뀌었고 2번은 4와 3과 5의 자리가 바뀌었다. 직접 적으면서 해보면 알겠지만, 왼쪽부터 오른쪽으로 수를 돈다고 가정할 때, 큰수 > 작은수 가 되는 부분이 있다. 수를 .. 2021. 9. 16. [swift][구현] 백준 16935번 (배열 돌리기 3) 요구능력: DFS와 BFS 그리고 스택과 큐의 이해 코드설명 : 1. 1번 배열을 상,하 반전 이건 arr이 2차원 배열이기 때문에 reverse()하면 arr[i][j]일 때, arr[i]의 순서가 거꾸로 되므로 상하반전이 된다. 2. 2번 배열을 좌, 우 반전 좌, 우 반전은 arr[i][j]에서 j(열)을 반전시켜주면 된다. 3. 배열을 오른쪽으로 90도 회전 이 부분에서 조금 헤맸다. n과 m을 스왑안해줘서 원하는 결과가 계속 안나왔다. n과 m을 스왑해줄거면 resultArr도 새로 생성해줘야한다. 어차피 밑에서 arr에 다 넣어주기 때문에 저장은 되어있다. 그리고 배열문제를 잘 푸려면 인덱스 활용을 잘해야된다. resultArr이 0,0일 때 arr은 5,0을 내주어야 한다. 이런식으로 쭉 나.. 2021. 9. 10. [Swift][DFS/BFS] 백준 1260번 (DFS와 BFS) 요구능력: DFS와 BFS 그리고 스택과 큐의 이해 코드설명 : 1. 간선을 받기위함. 이렇게 받으면 a[0]이 시작노드 a[1]이 도착노드인데 서로 넣어준 이유는 간선이 양방향이기때문이다. 예를 들면 간선이 1 5 로 입력되었으면 a[0]가 1이고 a[1]이 5이다. 여기서 a[0]에만 5를 넣어주면 간선은 1->5는 갈수있는데 5->1은 못가는게 된다. 정렬해준 이유는 문제에 순서가 적혀있었기 때문이다. 마찬가지로 둘다 정렬해준 이유는 간선입력이 a[0] = 1, a[1] = 5가 있는데 간선으로 입력받는것중 5로시작하는게 없을경우 정렬이 안되기 때문이다. 2. 시작노드는 시작이기 때문에 당연히 방문처리를 한다. 그리고 방문한 노드를 바로 프린트 해주는 방식으로 했다. DFS는 깊이우선 탐색이기 때문.. 2021. 9. 9. 이전 1 ··· 27 28 29 30 31 32 33 ··· 45 다음