알고리즘&자료구조 (16) 썸네일형 리스트형 정렬 알고리즘 활용 문제 풀이 BOJ 10989 수 정렬하기 3 Arrays.sort 로도 풀리지만 counting sort를 사용하는 방법도 있다. counting sort의 시간복잡도는 O(n + k)으로 매우 빠른 정렬 방식이지만 수의 범위만큼 메모리를 차지하기 때문에 범위가 제한되어 있고 1000만이하일 때 사용하는 것이 좋다 import java.io.* fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val n = readLine().toInt() val count = IntArray(10001) repeat(n) { count[readLine().toInt()]++ } val bw = BufferedWriter(OutputStreamWriter(Sy.. DP 문제 풀기 BOJ 1003. 피보나치 함수 1.테이블 정의하기 0과 1이 몇 번 출력되었는지 기록하기 위해 2차원 배열을 사용해서 정의한다 d[i][0] = fibonacci(i)를 실행했을 때 0이 출력된 횟수 d[i][1] = fibonacci(i)를 실행했을 때 1이 출력된 횟수 2. 점화식 구하기 피보나치를 응용해서 구하면 d[k][0] = d[k-1][0] + d[k-2][0] d[k][1] = d[k-1][1] + d[k-2][1] 3.초기값 설정 d[0][0] = 1 d[1][1] = 1 코드 import java.io.BufferedWriter import java.io.OutputStreamWriter fun main(args: Array) { var t = readLine()!!.toInt() v.. DP: Dynamic Programming 여러 개의 하위 문제를 풀고 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 예 ) 피보나치 -> 백트래킹 하기엔 n이 너무 클 경우 DP 푸는 과정 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 찾기 구현은 쉽지만 점화식을 끌어내는 과정이 쉽지 않음 -> 많은 문제 풀이 필요 BOJ 1463. 1로 만들기 (세 방향(연산 종류)으로 전개되는 bfs로도 풀 수 있음) 1.테이블 정의하기 d[i] = i 를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 (최소 횟수를 만들기 위한 규칙 찾기) 3으로 나누기 : d[k] = d[k/3] + 1(3으로 나눈 횟수 추가) 2로 나누기 : d[k] = d[k/2] + 1(2로 나눈 횟수 추가) 1 빼기 : d[k] = d[k-1] +.. kotlin 문자열 자르기 substring() 범위나 인덱스를 전달하여 문자열 자르기 가능하며 자른 문자열을 새로운 String에 담아 반환한다 String.substring(range) : 범위에 해당하는 부분을 잘라서 반환 String.substring(starIndex) : startIndex부터 끝까지 잘라서 반환 String.substring(startIndex, endIndex) : startIndex 부터 endIndex 전까지 잘라서 반환 split() delimiters(기준 문자열)에 따라 문자열을 자르고 List으로 반환한다 split(vararg delimiters: String, ignoreCase: Boolean = false, limit: Int = 0) 문자열 자르는 조건은 여러개 설정할 수 있다 c.. 시뮬레이션 구현하기 까다로운 구현 문제를 시뮬레이션이라고 한다 어려운 알고리즘을 쓰는 건 아니고 풀릴 것 같은데 막상 구현하려고 하면 꽤나 복잡해서 어떻게 해야 할지 모르겠는 문제들이다 푸는 것도 푸는 건데 문제가 길고 복잡해서 읽는 것도 힘들닿; 시간이 많지 않아서 문제 풀이 시간을 1~2시간으로 정해두고 그 안에 안 풀리면 답을 봤다 지금까지 풀어본 시뮬레이션 문제 유형 유형 1. 진짜 구현 (알고리즘 안쓰고 푸는 문제: 재귀, 반복문 등등) 유형 2. bfs+ 구현 유형 3. 백트래킹 + 구현 (풀이를 찾아보면 백트래킹 하는 부분을 dfs라고들 하는 것 같다) 유형 4. bfs + 백트래킹 + 구현 구현 - 배열 회전 시키기, 배열 한 방향으로 데이터 옮기기 등등 BOJ 15683 감시 몰라도 일단 풀어보라고.. 백트래킹 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 조건에 맞지 않는 후보는 제외하면서 탐색하여 불필요한 재귀 호출을 줄일 수 있다 BOJ 15649. N과 M (1) 순서가 있는 숫자 조합 출력하기 arr : 출력할 숫자를 담을 배열 isUsed : 현재 사용된 숫자를 구분하기 위한 배열 (isUsed[2] = 1 : 숫자 2는 이미 조합에 사용되었다) k: 현 인덱스, 몇번째 숫자까지 채웠는지 알 수 있다 구현 base condition : k == m 그동안 arr에 모은 숫자를 출력한다 backtracking isUsed[i] == 1 : 사용된 숫자라면 제외한다 isUsed[i] == 0 : 아직 사용하지 않은 숫자일 경우 arr에 추가 arr[k] = i, 사용했다는 표시 is.. 재귀 이번주 목표는 재귀 파트 넘기기 재귀 나에게 매우 어렵다 예전에도 알고리즘 공부하다가 재귀 파트에서 포기했던 기억이 난다 이젠 포기도 불가능 많이 풀어서 외워버릴테다 재귀란 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 함수를 명확하게 정의해야 함 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다 -> 반복문보다 메모리/시간에서 손해를 본다 자기 자신을 여러 번 호출하면 비효율적일 수 있다 -> 동일한 연산을 하는 함수 호출이 반복될 경우 재귀의 조건 1. 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함 : base condition 2. 모든 입력은 base condition으로 수렴해야 함 1,2중 한 조건이라도 무시된다면 무한으로 돌게 됨 절차지향적 사고를 탈피.. BFS 응용문제 풀기 2206. 벽 부수고 이동하기 최단거리 구하는 BFS 문제인데 벽을 하나 부술 수 있다는 조건이 추가되었다 최단 경로로 이동하기 위해 어떤 벽을 부숴야 하는지를 어떻게 구해야 할까 고민됐다 일단 모든 벽을 하나 하나 부쉈을 때 각 최단경로가 어떻게 되는지를 구하는 방법이 생각났는데 시간 초과가 나올 것 같았지만 생각나는 방법이 없어서 도전해봤더니 역시나 시간초과 변수에 벽을 부쉈는지 여부를 저장하고 이를 확인하여 벽을 부수지 않은 경우 벽을 만나면 부수는 방법도 생각해 봤으나, 0 1 (*) 0 1 (#) 1 0 1 0 0 이런 경우 # 위치의 벽을 부쉈기 때문에 이미 벽을 부쉈다는 체크가 되어있어 * 위치 벽을 부수지 못하고 탈출이 불가능하게 된다 다른 풀이를 봤더니 3차원 배열을 사용하고 있었다 (절.. 이전 1 2 다음
