부트캠프 개발일기/Algorithm8 28일차: 알고리즘 with Math(순열, 조합) ❯ 순열(Permutation)과 조합(Combination) 알고리즘 문제를 풀기 위해서는, 일부 수학적인 개념이 필요하다. 순열이란, 요소 n개 중에서 m개를 선택하여 순서에 상관있게 뽑는 경우의 수를 말한다. 조합이란, 순서에 상관 없이 요소 n개 중에서 m개를 뽑는 경우의 수를 말한다. 순열과 조합은 반복문의 중첩을 통해 구현할 수 있으나 뽑아야하는 경우의 수가 많아지면 반복문을 사용하는것이 비효율적이다. 따라서 재귀함수를 통해서 구현할 수 있다. 다만, 재귀함수를 작성할때는 필요한 매개변수가 어떤것이 있을지 잘 생각해보는것이 중요하다. (재귀함수를 재호출하면서 변수가 초기화 되지 않도록) 순열을 사용해 뽑은 숫자 중 소수 개수 계산하기 import java.util.ArrayList; // n .. 2023. 3. 24. 27일차: 알고리즘(Greedy, Brute-Force, Binary Search) ❯ Greedy 알고리즘 탐욕 알고리즘이라고도 하며, 선택의 순간마다 최적의 선택을 해서 해답에 도달하는 방법을 말한다. 1. 선택 : 현재 상태에서 최적의 해답 선택 2. 적절성 검사 : 선택된 답이 문제 조건을 만족하는지 검사 3. 해답 검사 : 원래 문제가 해결되었는지 검사하고, 해결이 되지 않았으면 다시 선택단계로 돌아가서 반복함 1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후 선택에 영향을 주지 않아야한다. 2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결방법은 부분 문제에 대한 최적 해결방법으로 구성된다. ❯ Brute-Force 알고리즘 (완전 탐색) 모든 값을 대입하여 올바른 값을 찾는 방법. 모든 경우를 시도해.. 2023. 3. 22. 26일차: 알고리즘(Algorithm)과 시간복잡도(Time Complexity) ❯ 알고리즘(Algorithm) 알고리즘이란, 문제를 해결하는 최선의 선택을 구하는 것을 의미한다. 이를 위해 문제를 정확하게 이해하고, 어떻게 해결할지 전략을 수립하고, 수립한 전략을 실제 코드로 작성할 수 있어야한다. 알고리즘 문제 풀이를 위해서는 의사코드(PseudoCode)를 잘 작성하는것이 중요하다. 자연어(혹은 프로그램언어)를 사용하여 프로그램 작동 논리를 작성하게된다. 의사코드를 구체적이고 논리적으로 작성해야 코드 작성시 시간이 단축되고 디버깅이 용이해진다. ❯ 시간 복잡도(Time Complexity) 이때까지 문제 풀이 혹은 기능 구현만 신경써서 연산 수행시간은 전혀 고려하지 않았다. 시간 복잡도란, 프로그램 입력값과 연산 수행시간의 상관관계를 나타내는 척도로 입력값의 변화에 따라 연산을.. 2023. 3. 21. 25일차: 순회(Traversal) ❯ Tree traversal 트리의 모든 노드를 한번씩 방문하는 것을 트리 순회라고 한다. 트리 구조는 계층적 구조를 가지므로 모든 노드를 순회하는 방법으로는 크게 세가지가 있다. 전위 순회(Preorder traverse) 먼저 노드를 방문하고, 왼쪽 서브트리를 전위순회하고, 오른쪽 서브트리를 전위순회 하는것을 말한다. 트리구조에서 방문하는 순서는 아래와 같다. 더보기 /* 최소한의 기능만 구현되어 있습니다. 자식 노드가 없는 경우는 node == null이라고 가정합니다. 이미 이진 트리는 구현되어 있다고 가정합니다. */ class Node { String data; Node left; Node right; public Node getLeft() { return left; } public Stri.. 2023. 3. 20. 24일차: 자료구조(Graph, Tree, BST) ❯ Graph 여러 점들이 서로 복잡하게 연결된 관계를 나타내는 자료구조. 흔히 그래프라고 생각하면 수학에서 접했던 이차함수그래프, 정규분포그래프 등을 생각하기 쉽다. 하지만 컴퓨터 공학에서 이야기하는 자료구조로서의 Graph는 여러개의 점이 선으로 이어진 네트워크망 구조를 가진다. 그래프의 구조 점간의 직접적인 관계가 있으면 두 점 사이를 이어주는 선이 있다. 간접적인 관계라면 몇개의 점과 선을 통해 이어진다. 이 때 하나의 점을 정점(Vertex), 이를 잇는 선은 간선(edge)이라고 한다. 그래프의 표현방식 두 정점을 잇는 간선이 있다면 이 두 정점은 인접한 것이다. 이를 표현하는 방법으로는 인접행렬을 이용하는 방법과 인접리스트를 사용하는 방법이 있다. 1) 인접행렬 : 두 정점간의 관계가 있는.. 2023. 3. 17. 23일차: 자료구조 (Stack, Queue) ❯ 자료구조 프로그래밍을 하다보면 다양한 데이터를 사용하게 된다. 데이터의 특징에 따라 체계적으로 정리하고 관리해야 데이터를 효율적으로 사용할 수 있다. 이렇게 데이터 묶음을 저장하고 사용하는 방법을 정의한 것을 자료구조라고 한다. 위의 다양한 자료구조 중 자주 사용하는 자료구조는 Stack, Queue, Tree, Graph로 이 네가지에 대해 학습한다. 자료구조의 특성과 기능에 대해 알면 어떤 상황에서 어떠한 자료구조를 사용할수 있을지 알 수 있다. 특히, 학습을 위해 직접 해당 자료 구조를 사용자정의 클래스를 작성해보면서 기능을 익힐 예정이다. ❯ Stack Stack 의 사전적 의미인 "쌓다. 쌓이다."처럼 데이터를 순서대로 쌓는 구조를 의미한다. 가장 나중에 들어간 데이터가 가장 먼저 나온다.(.. 2023. 3. 16. 이전 1 2 다음
