본문 바로가기

전체 글130

[알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍(동적 계획법)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 알고리즘 설계 기법: 문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식을 뜻한다.설계 기법은 알고리즘을 개발하고 구현하는 데 사용되는 전략과 원칙을 뜻한다. DP와 재귀 호출의 차이점DP와 재귀 호출의 차이점을 알기 전에 하향식 접근법과 상향식 접근법이 무엇인지 알아야 한다.1. 하향식(top-down) 접근법과 상향식(bottom-top) 접근법하향식 접근 방식은 큰 문제를 작은 하위 문제로 쪼개서 해결하는 방법이다. 주로 재귀 호출을 할 때 사용된다.상향식 접근 방식은 작은 문제들부터 시작해 작은 문제들의 결과를 이용해 점점 큰 문제의 결과를 구하는 방법. 2. 메모이제이션(Memo.. 2024. 6. 12.
[Android, 내일배움캠프] 공부일지(2024-06-11) 오늘 공부한 내용 정리(2024년 6월 11일)  1. 코드카타 문제풀이A. 행사장 대여(Small)(백준, S5, 14732번)문제 내용 문제 풀이 방법직사각형의 개수(N)와 직사각형의 시작점과 끝점이 주어질 때, 직사각형의 넓이를 출력.가장 큰 직사각형의 넓이를 구하는 문제가 아닌, 모든 직사각형의 합집합 넓이를 구하는 것이다.위와 같은 경우로 주어질 경우, 큰 직사각형  옆에 튀어나와 있는 점 E, H의 넓이도 같이 계산해야 한다는 뜻이다.넓이는 24 + 2 = 28이다. 해결 코드(스포 주의)더보기import java.util.Scannerfun main() = with(Scanner(System.`in`)) { val squareCnt = nextInt() val coordinate .. 2024. 6. 11.
[Android, 내일배움캠프] 공부일지(2024-06-10) 오늘 공부한 내용 정리(2024년 6월 10일)  1. 코드카타 문제풀이A. 균형 잡힌 세상(백준, S4, 4949번)문제 내용 문제 풀이 방법균형 잡힌 문자열이면 yes, 아니면 no 출력.균형 잡힌 문자열이 되기 위해서는소괄호는 소괄호끼리, 대괄호는 대괄호끼리 짝을 이룬다.모든 오른쪽 괄호는 짝을 이루는 왼쪽 괄호가 있어야 한다.괄호는 1:1 매칭만 가능하다.Help( I[m being held prisoner in a fortune cookie factory)]. 다음과 같은 문자열이 주어지면 이 문자열은 균형 잡힌 문자열이 아니다.괄호 순서가 (, [, ), ]이기 때문에 매칭될 수 없다. 해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.I.. 2024. 6. 10.
[Android, 내일배움캠프] 공부일지(2024-06-07) 오늘 공부한 내용 정리(2024년 6월 7일)  1. 코드카타 문제풀이A. 트럭(백준, S1, 13335번)문제 내용 문제 풀이 방법다리의 길이, 다리의 최대하중이 주어지고 트럭의 무게를 나타낸 숫자들이 입력으로 주어질 때, 모든 트럭들이 다리를 건너는 최단시간을 출력.다리의 길이는 단위길이라고 적혀 있는데, 그냥 다리의 길이가 w라는 뜻이므로 단위길이 때문에 헷갈리는 일이 없도록 하자.최단시간을 출력하려면 다리의 최대 하중에 가장 가깝게 트럭들을 여러 대 보내야 한다(하중이 10이라면 무게가 4인트럭 1대를 보내는 것보다 무게가 4, 5인 트럭 각각 1대씩 보내는 것이 시간 절약에 도움이 된다).트럭 1대가 다리를 모두 건너는 시간은 w초가 걸린다(다리의 길이만큼).트럭은 다리로 진입하는 데 1초, 다.. 2024. 6. 7.
[Android] 공부일지(2024-06-06) 오늘 공부한 내용 정리(2024년 6월 6일)  1. 알고리즘 문제풀이A. 듣보잡(백준, S4, 1764번)문제 내용 문제 풀이 방법첫째 줄에 듣도 못한 사람의 수가 주어지고, 보도 못한 사람의 수가 주어질 때, 둘째 줄부터 듣도 못함 사람 이름부터 보도 못한 사람 이름 순서대로 입력된다.(듣도 못한 사람이 3이고, 보도 못한 사람이 4일 때 2번째 줄부터 7줄에 걸쳐서 입력이 주어짐)입력받은 사람들 중 듣보잡의 수를 출력(듣도 못한 사람과 보도 못한 사람에 모두 포함되는 사람) 해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.BufferedWriterimport java.io.InputStreamReaderimport java.io.OutputS.. 2024. 6. 7.
[Android, 내일배움캠프] 공부일지(2024-06-05) 오늘 공부한 내용 정리(2024년 6월 5일)  1. 코드카타 문제풀이A. CCW(백준, 11758번)문제 내용 문제 풀이 방법문제 이름에 힌트가 나와있다. ccw 알고리즘을 이용해 문제를 해결한다.ccw 알고리즘은 3개의 점의 방향을 알 수 있는 알고리즘이다. 해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderfun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val pointList = mutableListOf>() for (i in 0 until 3) { val point = readLine().split(" ").map .. 2024. 6. 6.
[Android, 내일배움캠프] 공부일지(2024-06-04) 오늘 공부한 내용 정리(2024년 6월 4일)  1. 코드카타 문제풀이A. 잃어버린 괄호(백준, 1541번)문제 내용 문제 풀이 방법수식이 문자로 주어질 때, 수식의 값이 최소가 되는 경우를 출력.string을 - 기호를 기준으로 split을 해 분할한 후, + 기호로 연결된 모든 수를 더해서 리스트에 저장 후 리스트의 값을 첫 번째 리스트 값만 더하고 나머지는 모두 빼서 결과를 도출할 수 있다.초기 수식: 55 - 50 + 40- 기호를 기준으로 분할: 55, 50 + 40+ 기호의 값을 모두 더함: 55, 90결과의 첫 번째 데이터에 나머지 데이터를 모두 뺀 값: -35 해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamRea.. 2024. 6. 4.
[Android, 내일배움캠프] 공부일지(2024-06-03) 오늘 공부한 내용 정리(2024년 6월 3일)  1. 코드카타 문제풀이A. Hashing(백준, 15829번)문제 내용 문제 풀이 방법입력받은 문자열을 사용해 해시 값을 출력.해시 값을 구하는 방법은 a가 1이고 z가 26일 때, a의 int 값 * 31의 n제곱 % 1234567891과 같은 형식으로 구할 수 있다. n의 값은 a가 문자열에서 몇 번째 값인지 구해서 대입한다. 해결 코드(스포 주의)더보기import java.util.Scannerimport kotlin.math.powfun main() = with(Scanner(System.`in`)) { nextInt() val string = next() val mod = 1234567891 var result: Long = .. 2024. 6. 3.
[Android, 내일배움캠프] 공부일지(2024-05-31) 오늘 공부한 내용 정리(2024년 5월 31일)  1. 코드카타 문제풀이A. 과일 장수문제 내용 문제 풀이 방법사과를 m 개씩 담아서 포장할 때, 포장한 사과의 최저 점수와 담긴 사과의 개수(m)를 곱한 합을 return.과일을 높은 점수의 과일끼리 포장해야 이익이 크기 때문에 score를 정렬해서 과일을 포장하면 최대의 이익을 도출할 수 있다. 해결 코드(스포 주의)더보기fun solution(k: Int, m: Int, score: IntArray): Int { var answer: Int = 0 val fruitList = score.sortedArray() var fruitScore = k var addCnt = 0 // fruitList(정렬됨)에서 m번씩 돌면서 fr.. 2024. 5. 31.
[Android, 내일배움캠프] 공부일지(2024-05-30) 오늘 공부한 내용 정리(2024년 5월 30일)  1. 코드카타 문제풀이A. 둘만의 암호문제 내용 문제 풀이 방법s의 각 문자들을 index만큼 뒤로 옮기기(a -> b -> c...)옮기는 문자들 중에 skip에 문자가 포함되어 있으면 그 문자를 제외(건너뜀)문자가 z를 넘어가면 a로 다시 돌아가서 옮기기 시작. 해결 코드(스포 주의)더보기// s의 각 문자를 index만큼 뒤로 옮기기// 옮기는 문자가 skip에 포함되어 있는 경우, 제외하고 넘어가기// 문자가 z를 넘어가면 a로 돌아가서 다시 시작.fun solution(s: String, skip: String, index: Int): String { var answer: String = "" var move = 0 val rol.. 2024. 5. 30.
[Android, 내일배움캠프] 공부일지(2024-05-29) 오늘 공부한 내용 정리(2024년 5월 29일)  1. 코드카타 문제풀이A. 체육복문제 내용 문제 풀이 방법학생 n명 중 체육복을 잃어버린 lost 데이터가 있을 때, 빌려올 수 있는 학생인 reserve를 통해 가장 많이 체육복을 얻을 수 있는 경우를 구하기.제한 사항 중 마지막 제한사항을 유의해서 코드를 작성하기. 해결 코드(스포 주의)더보기// 학생 n명 중 체육복을 잃어버린 lost 데이터가 있을 때, 빌려줄 수 있는 학생인 reverse를 통해 가장 많이 체육복을 입을 수 있는 경우를 구해 return.fun solution(n: Int, lost: IntArray, reserve: IntArray): Int { var answer = 0 // null: 체육복은 가지고 있지만 누구를.. 2024. 5. 29.
[Android, 내일배움캠프] 공부일지(2024-05-28) 오늘 공부한 내용 정리(2024년 5월 28일)  1. 코드카타 문제풀이A. 기사단원의 무기문제 내용 문제 풀이 방법기사 number번까지 기사가 있을 때, number의 약수의 개수만큼의 공격력을 가진 무기를 쓸 수 있다.공격력이 limit를 초과했을 경우, power의 공격력을 가진 무기로 대체된다.공격력이 3일 때, 철의 무게가 3이 필요하다. 이때 기사들에게 모두 무기를 쥐어주려면 철의 무게가 얼마나 필요한지 계산해서 return. 해결 코드(스포 주의)더보기import kotlin.math.sqrtfun solution(number: Int, limit: Int, power: Int): Int { var answer: Int = 0 repeat(number) { num -> .. 2024. 5. 28.
[Android, 내일배움캠프] 공부일지(2024-05-27) 오늘 공부한 내용 정리(2024년 5월 27일)  1. 코드카타 문제풀이A. 모의고사문제 내용 문제 풀이 방법1, 2, 3번 수포자의 정답에서 answers와 비교해 가장 많은 정답을 맞힌 수포자를 구하기.수포자의 정답지는 정답 형식에서 규칙을 찾아서 구성해야 함. 해결 코드(스포 주의)더보기// 학생 1, 2, 3이 있고, answers가 있음.// 학생 1, 2, 3의 정답을 규칙에 맞게 구성한다(answers의 size 만큼).fun solution(answers: IntArray): IntArray { // 각 학생들의 시험 찍는 규칙 val stu1 = intArrayOf(1, 2, 3, 4, 5) val stu2 = intArrayOf(2, 1, 2, 3, 2, 4, 2, 5).. 2024. 5. 27.
[Android, 내일배움캠프] 공부일지(2024-05-18) 오늘 공부한 내용 정리(2024년 5월 18일)  1. 코드카타 문제풀이A. 직사각형 별 찍기문제 내용 문제 풀이 방법n x m의 별을 찍어서 출력한다. 해결 코드(스포 주의)더보기fun main(args: Array) { val (a, b) = readLine()!!.split(' ').map(String::toInt) repeat(b) { repeat(a) { print("*") } println() }} 풀이 과정세로 길이(b)를 바깥 repeat()으로, 가로길이를 내부 repeat()으로 구성함.가로 별 찍기가 끝날 때마다 줄 바꿈을 해주어야 하기 때문이다. B. x만큼 간격이 있는 n개의 숫자 문제 내용 문제 풀이 방법x.. 2024. 5. 18.
[Android, 내일배움캠프] 공부일지(2024-05-17) 오늘 공부한 내용 정리(2024년 5월 17일)  1. 코드카타 문제풀이A. 2016년문제 내용 문제 풀이 방법a가 월이고 b가 일일 때, 2016년 해당 날짜가 무슨 요일인지 출력출력 형식은 각 날짜의 앞에서 3 단어(SATURDAY -> SAT) 해결 코드(스포 주의)더보기fun solution(a: Int, b: Int): String { val date = LocalDate.of(2016, a, b) return date.dayOfWeek.name.substring(0, 3)} 풀이 과정날짜 데이터에 LocalDate()를 이용해 정확한 날짜 정보를 생성해 줌.LocalDate().dayOfWeek.name을 하게 되면 해당 날짜에 요일을 알 수 있는데, 풀네임으로 나오기 때문에 sub.. 2024. 5. 17.
728x90

티스토리툴바