본문 바로가기

Coding

 (195)
1912번 연속합 생각보다 오래 걸린 DP 문제. 점화식을 찾다가 생각해보니 그냥 다 더하면서 나아가면 된다는것을 깨닫고 그대로 실행. 10 -4 3 1 5 6 -35 12 21 -1 10 6 9 10 15 21 -14 12 33 32 -> 시간초과. 이틀 정도 다른 문제 풀다가 봤더니 굳이 dp를 0으로 만들어줄 필요가 없다는걸 깨달았다. 그래서 살짝 코드를 바꿔줬더니 통과했다. 전체 코드
1065번 한수 간단한 브루트 포스 문제. 100미만의 숫자는 다 한수이므로 입력받은 N값이 답이 된다. 그렇기 때문에 100이상의 숫자에서 한수를 찾으면 된다. (ex. 123, 135, 234, 258) 예시를 보면 백의 자리와 일의 자리를 더한 값을 2로 나누면 십의 자리 숫자가 된다. 모든 한수가 그렇다. 여기서 조심해야 할 점은 나머지 값은 없어야 한다는 것이다.
11057번 오르막 수 쉬운 DP문제인데 생각보다 오래걸렸다(쉬운거 맞나..?). 저장할 공간을 arr[길이 N][층수]라고 생각해보자. 1. arr[n][층수]를 구하려면 층수를 나누어야한다. arr[n][0층]을 구하려면 그 전 길이인 n-1에서 구해야하고 arr[n-1][0층]밖에 없다. 2. arr[n][1층]을 구하려면 그 전 길이인 n-1에서 구해야하고 arr[n-1][0층], arr[n-1][1층]밖에 없다. 3. 즉, arr[n][0] = arr[n-1][0] arr[n][1] = arr[n-1][1] + arr[n-1][0] arr[n][2] = arr[n-1][2] + arr[n-1][1] + arr[n-1][0] ....... ..... .. . arr[n][9] = arr[n-1][9] + arr[n-1]..
Insert Sort 삽입정렬이란? 앞에서부터 시작하여 범위를 늘려가며 자기 자신의 자리를 찾는 정렬 방식이다. ex) 3 2 1 -> 2 3 1 -> 1 2 3 1. 시간복잡도 최악의 경우(정렬되어있지않은 경우) 1번, 2번, 3번, ..... , N-1번까지 정렬이 일어날 수 있다. 즉, N*(N-1)/2 이므로 O(N^2) 2. stable 범위를 늘려가면서 순서대로 자기 위치를 찾기 때문에 같은 숫자의 순서를 유지한다. 3. 코드 ps. 삽입 정렬은 왼쪽 부분이 정렬되어있다고 가정하기 때문에 자기가 왼쪽에 있는것보다 크다면 거기서 멈추면 된다. 따라서 멈출 포인트를 알고 있기 때문에 선택, 버블 정렬보다 효율적이다.
Bubble Sort 거품정렬이란? 앞,뒤 인접한 숫자들을 비교하여 작은값을 앞으로, 큰 값을 뒤로 바꿔주는 정렬 방식이다(오름차순일 경우). 1. 시간복잡도 1부터 N까지 N번 -> 2부터 N까지 N-1번 -> 3부터 N까지 N-2번 -> ........... -> N-1에서 N까지 1번 즉, N*(N+1)/2 이므로 O(N^2) 2. stable 앞에서부터 비교하여 쭉 올라가기 때문에 같은 숫자의 순서를 유지한다. 3. 코드
Selection Sort 선택 정렬이란? 값들 중 가장 작은 값을 찾아서 맨 앞으로 보내는 정렬 방식이다. 1. 시간 복잡도 N-1만큼 돌고 -> N-2만큼 돌고 -> N-3만큼 돌고 -> ..... -> 1만큼 돌고 즉, N*(N-1)/2 이므로 시간 복잡도 O(N^2) 2. Unstable 최소값을 구해 Swap 해주는 형태로 진행되기 때문에 같은 숫자의 순서를 보장해주지 않는다. 3. 코드
9465번 스티커 간단한 DP문제. i\j 0 1 2 3 4 0 50 10 100 20 40 1 30 50 70 10 60 (dp[j][i]) 1. j가 0일때, dp[0][0] 또는 dp[0][1]에서 시작. 2. j가 1일때, dp[0][0]에서 갈 수 있는 곳은 dp[1][1], 즉 dp[1][1]=dp[1][1]+dp[0][0] dp[0][1]에서 갈 수 있는 곳은 dp[1][1], 즉 dp[1][0]=dp[1][0]+dp[0][1] 3. j가 2일때, dp[2][0]으로 올 수 있는 곳은 dp[1][1]과 dp[0][1]이다, 즉 dp[2][0]=max(dp[1][1]+dp[2][0],dp[0][1]+dp[2][0]) dp[2][1]로 올 수 있는 곳은 dp[1][0]과 dp[0][0]이다, 즉 dp[2][1]=..
xcode 코드 옆의 M과 A 의미 M -> 코드가 수정되었고 로컬 깃 저장소에 아직 커밋되지 않은 상태를 의미. A -> 새로운 파일이 생성되었고 아직 커밋되지 않은 상태를 의미.

티스토리툴바