CS 이론/🤖 알고리즘, 자료구조 8 동적 계획법(Dynamic Programming) 알아보기 동적 계획법(Dynamic Programming) 알아보기 똑같은 계산을 계속 반복해야 하는 알고리즘에서 계산 값을 저장해 둬서 반복하지 않게 하는 방법 동적 계획법이라는 이름은 아마 정적으로 계획없이 똑같은 계산을 반복하는게 아니라 동적(적극적)으로 계획해서 계산을 줄이는 방법이라 그렇지 않을까 개인적으로 추측해 봅니다. 동적 계획법을 쓰던 안 쓰던, 정확성은 Brute-Force와 차이가 없습니다. 하지만, 훨씬 더 효율적입니다. 예시 : 피보나치 수열 구하기 피보나치 수열은 1, 1 부터 시작해서 그 전 2개의 항을 더한게 n번째 항인 수열입니다. 이 정의를 그대로 코드로 구현하면 아래와 같습니다. fun fibo(n: Int): Int { if (n 2023. 4. 15. 코딩 테스트에서 최대공약수(GCD), 최소공배수(LCM) 유클리드 알고리즘으로 구하기 코딩 테스트에서 최대공약수(GCD), 최소공배수(LCM) 유클리드 알고리즘으로 구하기 코딩 테스트를 풀다 보면 의외로 최대 공약수, 최소 공배수를 구해야 할 일이 많습니다. 직접적으로 최대 공약수 / 최소 공배수를 구하라고 하는 문제도 있지만, 아래의 문제는 모두 간접적으로 최대 공약수 / 최소 공배수를 구해 푸는 문제들입니다. 기약 분수로 만들기 n개로 나눌때 모든 사람이 같은 개수를 가질 수 있게 하기 무식하게 최대 공약수 구해보기 두 수의 약수를 모두 구한다 공통된 약수만 남긴다 거기서 가장 큰 수가 최대 공약수! 최소 공배수는 최대 공약수만 구하면 자동으로 최소 공배수의 의미가 뭘까요? x, y의 최소 공배수라 하면, x, y 모두와 나누어 떨어지는 가장 작은 수 즉, 만약 아래와 같이 x, y가 이루어져 있다면 x, y의 최소 공배수는 a, b, c 3개의 숫자로 모두 나누어 .. 2023. 4. 7. 코딩 테스트 속도 높이기 : 내가 자주 쓰는 Java 문법 설탕(Syntax Sugar) 총정리 코딩 테스트 속도 높이기 : 내가 자주 쓰는 Java 문법 설탕(Syntax Sugar) 총정리 문법 설탕이 뭐야? 말하는건 똑같아도 짜증나게 말하는 사람이 있고, 듣기 좋게 말하는 사람이 있듯, 코드도 하는건 똑같아도 읽기 쉬운 코드가 있고 읽기 힘든 코드가 있습니다. 문법 설탕은 꼭 써야 하는건 아니지만 2가지 장점이 있어 알아두면 좋습니다. 1. 더 읽기 쉬운 코드를 쓸 수 있습니다. 2. 자주 쓰는 기능을 내가 직접 구현하지 않고 내장함수를 써 더 빠른 코딩이 가능합니다. 어떻게 활용할까? 우선, 문법 설탕이 아무리 코딩을 빠르게 해 주고 읽기 쉬운 코드를 만들어 준다고 해서 영어 단어 외우듯 외울 필요는 없다고 생각합니다. 대신, 저는 많이 써 보면 자연스럽게 적재적소에 활용할 수 있게 됐습니다. 자연스럽게 활용하기 위해 추천하는건 항상 코딩 테스트나 코드를 작성하고 리팩토링(Refacto.. 2022. 12. 14. 가변 배열(Dynamic Array), 리스트(List) 가변 배열(Dynamic Array), 리스트(List) 가변 배열(Dynamic Array), 혹은 리스트(List)는, 가장 기초적인 자료구조라 할 수 있는 배열을 개조해서 크기가 자동으로 조절되게 만든 자료구조입니다. 배열은 처음에 크기를 고정해야 합니다. 여러가지 이유가 있지만, 가장 큰 이유는 속도 때문입니다. 하지만 현실의 프로그래밍에서는 크기를 미리 정해두면 불편함이 많아서, 자동으로 크기가 조절되는 배열이 매우 유용합니다. 가변배열의 정의, 추상자료형 가변 배열 (리스트)은 말 그대로 크기가 변할 수 있는 배열입니다. 하지만 크기가 변한다는 것 이외에는 일반적인 배열과 똑같습니다. 우선, 가변 배열에 필요한 매소드가 어떤 것이 있을지 생각해 보면 좋을거 같습니다. 우선 가변 배열은 외부적으로는 크기가 정해져 있지 않고 유연하게 늘어나는 것 처럼 .. 2021. 5. 28. 모든 자료구조는 배열(Array)로 통한다 모든 자료구조는 배열(Array)로 통한다 배열은 거의 대부분의 프로그래밍 언어가 가지고 있고, 많은 자료구조의 기초가 되는 중요하고 기본적인 자료구조이다. 배열은 프로그래밍을 조금이라도 한 사람이라면 이미 익숙한 경우가 많겠지만, 자료구조의 관점에서 다시 한번 배열을 들여다보자. 배열의 정의 배열은 데이터와 인덱스가 대응되도록 한 자료구조이다. 배열은 크기가 정해져 있고, 배열의 인덱스는 일반적으로 0에서 시작한다. 배열은 사실상 가장 간단한 자료구조 중에 하나이다. 배열은 단순히 데이터를 정해진 개수만큼 순서대로 배치한 것이기 때문에 이보다 더 간단하게 데이터를 배치할 방법은 없다. 하지만, 그만큼 제한이 많은 데이터 구조 중에 하나이다. 우선, 크기가 정해져 있기 때문에 정해진 크기가 다 차면 더 이상 데이터를 추가할 수 없고, 또 중간에 .. 2021. 5. 24. 추상 자료형(Abstract Data Type)을 왜 알아야 할까 추상 자료형(Abstract Data Type)을 왜 알아야 할까 자료구조를 배우기도 전에 추상 자료형을 배워야 하는 게 좀 이상할 수 있다. 하지만, 특정한 자료구조는 추상 자료형을 구현한 것에 지나지 않는다. 똑같은 추상 자료형도, 다양한 방법과 다양한 프로그래밍 언어로 구현할 수 있고, 구현을 하기 전에 규칙을 정의하는 건 기본이기 때문에 추상 자료형을 잘 이해하는 것은 자료구조를 이해하기 위한 첫걸음이다. 추상 자료형이란? 추상 자료형은 자료구조가 따라야 할 규칙들을 추상적으로 정의한 것이다. 추상 자료형은 실제로 이 자료구조를 어떻게 구현해야 하는지는 전혀 언급하지 않는다. 추상 자료형은, 영어로 Abstract Data Type라고도 하는데, 이를 줄여서 ADT로 나타내는 경우도 많다. 구체적으로는, 추상 자료형은 자료구조가 어떤 자료를 저장하는지와, 어떤 .. 2021. 5. 22. 빅 오 표기법(Big-O Notation), 알고리즘의 효율을 알려줘 빅 오 표기법(Big-O Notation), 알고리즘의 효율을 알려줘 컴퓨터 프로그램을 만들 때 가장 중요한 것은 2가지이다. 얼마나 빠른가 와 얼마나 적은 공간을 차지하는가. 아무리 좋은 프로그램이라도 너무 느리면 소용이 없고, 아무리 좋은 프로그램이라도 너무 크면 소용이 없다. 게임이 아무리 재밌어도 한 번 키는데 1시간이 걸리고, 용량이 2TB라고 해 보자. 그 게임을 사용할 사람은 없을 것이다. 이런 극단적인 예시가 아니라도, 프로그램을 최대한 빠르고 용량을 적게 차지하게 하는 건 중요하다. 이런 효율을 측정해 주는 방법 중 하나가 바로 빅 오 표기법이다. Big-O가 뭘까? Big-O 표기법은, 쉽게 말해 컴퓨터 프로그램의 효율성을 최악을 가장하고 측정해 주는 것이다. BIg-O 표기법에서는, 데이터가 말도 안 되게 커질때의 효율을 측정한다. 사실, 데이터가 적으.. 2021. 5. 20. 자료구조? 그게 뭔데 씹덕아 자료구조? 그게 뭔데 씹덕아 네카라쿠배당토에 갈 꿈을 꾸고 있거나, 프로그래머로서 어디서 말 좀 하고 싶다면 자료구조와 알고리즘을 알아야 한다고 합니다. 흔히 말하는 코딩 테스트가 바로 이 자료구조와 알고리즘을 다루는 능력을 보는 시험입니다. 이 자료구조가 뭐고, 왜 중요하고, 알고리즘이랑 무슨 상관이 있을까요? ⁉️ 자료구조가 뭐야? 어떤 단어가 뭐냐고 물어볼 때 가장 짜증나게 대답하는 방법은 그 단어를 그대로 반복하는 겁니다. 자료구조는 자료를 구조화하는 방법입니다. 더 자세히는 자료(데이터)를 저장하는 방법입니다. 데이터를 저장하는 방법이 왜 그렇게 중요할까요? 그 이유는 세상에는 다양한 종류의 데이터가 있는데 컴퓨터는 기본적으로 모든 자료를 1차원으로 저장하기 때문입니다. 예를 들어체스판도 일종의 데이터라고 할 수 있는데, .. 2021. 5. 18. 이전 1 다음 반응형
