Java에서 배열 선언시 List를 만드는 방법엔 List를 통해 ArrayList를 만드는 방법이 있습니다.List list = new ArrayList();ArrayList list = new ArrayList(); 그러면 차이는 무엇일까요?🧐  List와 ArrayList 차이점List란 인터페이스입니다.즉 , Java의 다형성에 의해서 만약 아래와 같이 list를 List자료형으로 선언한 경우 그, 구현체를 ArrayList로도 구현 가능하지만 LinkedList로 구현도 가능합니다.  ArrayListArrayList는 클래스입니다. ArrayList 역시 아래처럼 List 인터페이스를 구현하고 있기 때문에 List가 제공하는 기능들을 다 제공할 수 있으므로 List 선언 시 구현 인스턴스의 ..

유클리드 호제법이란? 2개의 이상 자연수 또는 정식 최대공약수를 구하는 알고리즘입니다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어 결국 워하는 수를 얻는 알고리즘을 나타냅니다.  방법으로는 다음과 같습니다.1. 큰수에서 작은 수를 나눕니다.2. 나머지가 0이 아니라면, 나머지와 작은수로 1번부터 다시 시작합니다.3. 1번과 2번을 반복해 나머지가 0인 경우, 그 수가 최대공약수 입니다.   두 수 사이의 GCD, 최대 공약수유클리드 호제법은 재귀함수를 사용합니다.public class Main { public static void main(String[] args) { int a = 21; int b = 7; System.out.println("GCD =..

Queue 문제를 풀때 LinkedList를 쓰는데 그냥 왜 쓰는지 궁금하기도 하고 쨋든 쓰는 이유를 알아야 하니 글을 끄적끄적 적어본다.. 먼저 ArrayList와 LinkedList 각각에 대해 알아보자.   ArrayList 란?중복을 허용하고 순서를 유지Index로 원소들을 관리 배열과 상당히 유사그러나 배열은 크기가 값이 고정적이지만 ArrayList는 클래스로 배열을 추가, 삭제, 할 수 있는 메소드들도 존재 -> 이때 배열이 동적으로 늘어나는 것이 아닌 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 함add(E element) 배열 마지막에 원소를 추가 --> 빠르다! add(int index, E element)배열에 마지막이 나닌 처음, 중간에 즉 원하는 위치에 넣을수 ..

이분 탐색 (Binary Search)장점시간 효율성: 정렬된 배열에서의 탐색 시간 복잡도는 (O(\log n))으로 매우 빠르다.공간 효율성: 추가적인 데이터 구조가 필요 없고, 배열 자체만으로도 충분하다.간단한 구현: 이분 탐색 알고리즘은 비교적 간단하고 구현이 쉽다.단점정렬된 데이터 필요: 데이터가 정렬되어 있어야만 사용 가능하며, 정렬되지 않은 데이터에서는 사용할 수 없다.동적 데이터 처리 어려움: 데이터가 자주 변경되는 경우, 매번 정렬을 다시 해야 하므로 비효율적이다.고정된 데이터 구조: 배열과 같은 고정된 데이터 구조에서만 효율적이다.  사용하기 좋은 알고리즘정렬된 배열에서 특정 값 찾기: 정렬된 배열에서 특정 값을 빠르게 찾을 때 사용이진 검색 트리: 이분 탐색 트리에서의 탐색, 삽입, 삭..

동적 프로그래밍(Dynamic Programming)동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다. 라는 의미가 있다. - 위키백과 즉 코딩테스트에서는 DP는 메모리를 사용해서 중복 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선하는 것그리고 이미 계산한 결과를 메모리에 저장하여, 다시 계산하지 않도록 하는 것을 목적으로 한다. DP 알고리즘은 기억하기라고 생각을 하면 좀 더 쉽게 이해가 간다.   Dynamic Programming 조건동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고, "부분 문제"의 정답으로..

탐욕 알고리즘(Greedy Algorithm)Greedy는 탐욕 즉 욕심이 많은이란 뜻으로 탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달한다.탐욕 알고리즘은 최적해를 구하는 데 사용되는 근사적인 방법으로 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.순간마다 하는 선택은 그 순간에 대한 지역적으로 최적이지만, 그 선택이 계속 최적이라는 보장도 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.  탐욕 알고리즘 문제 해결 방법선택절차 : 현재 상태에서 최적을 해답 선택적절성 검사 : 선택된 해가 문제의 조건을 만족하는..

시간복잡도보통 알고리즘 구현시 시간복잡도를 고려해야한다는 말이 많다. 그럼 시간복잡도를 고려한다는 것은 무슨 의미인가?알고리즘 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 말이다.효율적인 알고리즘을 구현한다는 것 다시말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성이 시간 복잡도는 주로 빅-오 표기법을 사용  Big-O 표기법 Big-O(빅-오) ⇒ 상한 점근Big-Ω(빅-오메가) ⇒ 하한 점근Big-θ(빅-세타) ⇒ 그 둘의 평균위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.👉 가장 자주 사용되는 표기법은?빅오 표기법은 최악..

DFS루트노트에서 다음 분기로 넘어가기 전, 해당 분기를 모두 탐색하는 방법, 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색 특징자기 자신을 호출하느 순환 알고리즘 형태를 지님. (재귀, 스택)이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사(검사를 하지 않을 경우 무한루프...)ex)visit[index] = true;미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길(새로운 분기)로 돌아와서 다른 방향을 다시 탐색을 진행하는 방법가 유사모든 노드를 방문하고자 할 때, 이 방법을 선택너비우선탐색(BFS)보다 더 간단검색 속도 자체는 너비우선탐색(BFS)에 비해서 느림 과정 코..

스택(Stack)개념스택이란 쌍하 올린다는 것을 의미 따라서 스택 자료구조라는 것을 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태 자료구조 특징스택은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다.스택에서 top을 통해 삽입하는 연산을 push 삭제하는 연산을 pop이라고 하며 스택은 가장 마지막에 삽입된 자료가 먼저 삭제되고후입선출(LIFO) 방식구조 라고 한다. 코드public class Stack { private ArrayList items; public Stack() { items = new ArrayList(); } public boolean isEmpty() { return items.isEmpty(); } public voi..