Hello world;

스택(Stack)과 큐(Queue)는 컴퓨터 과학에서 중요한 개념으로, 각각의 자료구조는 데이터를 관리하고 처리하는 방식에 따라 차이점이 있습니다.

1. 스택(Stack): 스택은 가장 나중에 들어온 요소가 가장 먼저 나가는, 즉 LIFO(Last In First Out,후입선출) 구조로 작동하는 자료구조입니다. 스택은 용량이 정해져 있으며, 스택이 가득 차면 더 이상 요소를 추가할 수 없습니다. 주요 연산에는 push(스택에 요소를 추가), pop(스택의 가장 위에 있는 요소를 제거하고 그 요소를 반환), peek(스택의 가장 위에 있는 요소를 확인하는데 이때 요소가 제거되지는 않음)가 있습니다. 스택은 함수 호출, 문법 체크, 후위 표기법 계산 등에 활용됩니다.
2. 큐(Queue): 큐는 가장 먼저 들어온 요소가 가장 먼저 나가는, 즉 FIFO(First In First Out,선입선출) 구조로 작동하는 자료구조입니다. 주요 연산에는 enqueue(큐의 끝에 요소를 추가), dequeue(큐의 앞에서 요소를 제거하고 그 요소를 반환), peek/front(큐의 앞에 있는 요소를 확인하는데 이때 요소가 제거되지는 않음)가 있습니다. 큐는 운영 체제의 태스크 스케줄링, 너비 우선 탐색(Breadth First Search) 등에 활용됩니다.

즉 스택과 큐는 데이터를 추가하고 제거하는 순서에 따라 구분됩니다. 스택은 가장 나중에 추가된 데이터를 가장 먼저 처리하고, 큐는 가장 먼저 추가된 데이터를 가장 먼저 처리합니다. 

**예시

1. 스택(Stack): 스택은 책더미에 비유할 수 있습니다. 책을 쌓을 때는 위에서부터 쌓게 되고, 책을 꺼낼 때는 위에 있는 책부터 꺼내게 됩니다. 이처럼 가장 마지막에 들어온 것이 가장 먼저 나가는 구조를 스택이라고 합니다. 이것을 전문용어로는 LIFO(Last In First Out, 후입선출)라고 합니다.
2. 큐(Queue): 큐는 사람들이 줄을 서서 기다리는 모습에 비유할 수 있습니다. 사람들이 줄을 서서 차례대로 기다리다가 차례가 되면 서비스를 받게 됩니다. 이처럼 가장 먼저 들어온 것이 가장 먼저 나가는 구조를 큐라고 합니다. 이것을 전문용어로는 FIFO(First In First Out, 선입선출)라고 합니다.

** 스택의 활용

• 함수 호출: 프로그램에서 함수를 호출할 때마다 시스템은 그 호출 정보(인자, 리턴 주소 등)를 스택에 저장합니다. 함수 호출이 끝나면 그 정보를 스택에서 빼내어(팝) 원래의 상태로 돌아갑니다. 이러한 방식으로 함수의 호출 순서와 실행 순서를 관리합니다.
• 문법 체크: 컴파일러는 괄호의 쌍이 올바른지 확인하기 위해 스택을 사용합니다. 여는 괄호가 나올 때마다 스택에 넣고(푸시), 닫는 괄호가 나올 때마다 스택에서 꺼내서(팝) 괄호의 쌍이 맞는지 확인합니다.
• 후위 표기법 계산: 후위 표기법(예: 2 3 +)은 스택을 이용해서 계산합니다. 숫자를 만나면 스택에 넣고, 연산자를 만나면 스택에서 숫자를 두 개 꺼내서 연산 후 결과를 다시 스택에 넣습니다. 이런 과정을 반복해 최종 결과를 얻습니다.

** 큐의 활용

• 운영 체제의 태스크 스케줄링: 컴퓨터에서 여러 프로그램이 동시에 실행될 때, 어떤 프로그램을 먼저 실행할지 결정하는 것이 태스크 스케줄링입니다. 이 때 큐를 사용해 먼저 요청된 작업부터 순서대로 처리합니다.
• 너비 우선 탐색(Breadth First Search): 그래프나 트리 같은 데이터 구조를 너비 우선으로 탐색할 때 큐를 사용합니다. 방문할 노드를 큐에 넣고, 방문할 때마다 큐에서 노드를 하나씩 꺼내서 이웃 노드를 다시 큐에 넣습니다. 이런 과정을 큐가 빌 때까지 반복해 모든 노드를 방문하게 됩니다.

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO 구조이며 정해진 방향으로만 데이터를 쌓을 수 있고 top을 통해서만 접근 가능합니다. 순차적으로 데이터를 추가하고 삭제하기 때문에 Arraylist 같은 배열기반의 컬렉션 클래스가 적합합니다. 웹 브라우저 방문기록, undo/redo 등이 있습니다. 웹 브라우저의 뒤로 가기 기능

큐는 가장 먼저 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO 구조입니다. 한 쪽에서는 삽입 작업이, 다른 쪽에서는 삭제 작업이 이루어집니다. 배열 기반 클래스를 사용하면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 큐는 데이터의 추가와 삭제가 쉬운 링크드리스트로 구현하는 것이 더 적합합니다. 캐싱, 콜센터 대기시간, 최근 사용 문서가 있습니다. 프린터의 인쇄 대기열

1. 전송 시 암호화: 사용자의 패스워드는 절대 평문(암호화되지 않은 텍스트)으로 전송되어서는 안됩니다. HTTPS와 같은 보안 프로토콜을 사용해 데이터를 암호화해서 전송해야 합니다. 이렇게 하면 중간에 데이터를 가로채도 원본 패스워드를 알아내기 어렵습니다.
2. 보관 시 해싱: 사용자의 패스워드를 데이터베이스에 저장할 때도, 평문으로 저장하면 안됩니다. 대신 해싱 함수를 사용해서 패스워드를 해시값으로 변환한 뒤, 그 해시값을 저장해야 합니다. 해시 함수는 원래 데이터를 일정한 길이의 무작위 문자열로 변환하는 함수입니다. 해시 함수의 특성 상, 해시값에서 원래 데이터를 복원하는 것은 불가능에 가깝습니다. 따라서 해시값만 봐서는 원본 패스워드를 알아내기 매우 어렵습니다.
3. 솔트 사용: 그러나 해싱만으로는 충분하지 않습니다. 같은 패스워드는 항상 같은 해시값으로 변환되므로, 악의적인 사람이 미리 많은 수의 패스워드와 그 해시값을 계산해 놓은 "레인보우 테이블"을 이용하면, 해시값을 통해 원본 패스워드를 알아낼 수 있습니다. 이를 방지하기 위해 "솔트"라는 랜덤 문자열을 패스워드에 추가한 뒤 해싱합니다. 솔트는 각 사용자마다 다르게 생성되며, 패스워드 해시값과 함께 저장됩니다. 이렇게 하면, 레인보우 테이블을 사용한 공격을 막을 수 있습니다.
4. 보안을 더 높이려면: 이런 기본적인 보안 조치 외에도, 반복적인 해싱, 키 스트레칭, 페퍼(pepper, 전체 시스템에서 공통으로 사용하는 비밀 값) 추가 등 보안을 더 높일 수 있는 방법들이 있습니다.
   

** 대표적인 암호화(해싱) 알고리즘

1. Bcrypt: 솔트와 반복적인 해싱을 사용해 보안을 강화한 알고리즘입니다. 레인보우 테이블 공격을 방어하고, 작업량을 조절해 브루트 포스 공격을 어렵게 만드는 특징이 있습니다.
2. Scrypt: Bcrypt와 비슷하지만, 메모리를 많이 사용하도록 설계된 알고리즘입니다. 이로 인해 하드웨어를 이용한 공격을 더 어렵게 만듭니다. 같은 시간에 시도할 수 있는 암호화 해석 시도 횟수가 제한되어 보안이 향상됩니다.
3. Argon2: 메모리와 CPU 시간을 많이 필요로 하도록 설계된 알고리즘으로복잡한 하드웨어 공격도 어렵게 만들 수 있습니다. 최근에는 많은 시스템에서 이 알고리즘을 사용하는 추세입니다.
4. PBKDF2 (Password-Based Key Derivation Function 2): 솔트와 반복적인 해싱을 사용하는 알고리즘입니다. 원래 암호화된 키를 생성하기 위해 설계되었지만, 패스워드 저장에도 사용됩니다. iOS에서는 이 알고리즘을 사용하여 키를 생성합니다.

**페퍼(pepper)는 "솔트"와 비슷하지만 저장되지 않는 추가적인 랜덤값입니다. 페퍼는 시스템 전체에서 같은 값이 사용되며, 해시를 계산할 때 패스워드와 솔트에 추가로 더해집니다. 페퍼를 사용하면 데이터베이스가 노출되더라도 페퍼를 모르는 공격자는 해시를 제대로 계산할 수 없습니다. 예를 들어, "1234"라는 패스워드를 해시할 때, 패스워드에 "abc"라는 솔트와 "xyz"라는 페퍼를 추가하고 이를 해시합니다. 이렇게 하면 공격자가 "1234abc"에 대한 해시를 미리 계산해놔도 "xyz" 페퍼를 모르기 때문에 실제 해시 값을 얻을 수 없습니다.

유저의 패스워드를 받은 클라이언트는 평문으로 서버로 전송합니다. 평문을 받은 서버는 패스워드를 단방향 해시 함수로 암호화하여 보관합니다. 단방향 해시함수는 수학적 연산에 의해 원본 데이터를 완전히 다른 암호화된 데이터(다이제스트)로 변환하는 것을 말합니다. 원본 데이터로는 다이제스트를 구할 수 있지만 다이제스트로는 원본데이터를 구할 수 없어야 합니다. 이것을 단방향이라 합니다. 단방향 해시함수는 브루트포스 공격으로 쉽게 당할 수 있기 때문에 이를 보완하기 위해 입력된 다이제스트를 N번 반복해서 생성하는 것인 key stretching과 원문 패스워드에 임의의 문자열을 추가하여 해싱하는 것인 salting을 이용해 보안의 강도를 높힐 수 있습니다.

클라이언트에서 패스워드를 전송하고 서버에서 해당 패스워드를 보관해야 할 때 서버에서 패스워드를 그대로 보관하지 않습니다. Bcrypt와 같은 모듈을 이용하여 패스워드를 특정 알고리즘으로 암호화하여 서버에 저장하게 됩니다. 이때 암호화는 주로 단방향 암호화로 진행합니다. 패스워드를 어떤 알고리즘으로 암호화하여 같은 암호화 결과물을 얻을 수 있지만 암호화 된 결과물을 다시 암호화 전의 패스워드로 복구가 불가능 한 것이 단방향 암호화입니다.

기본적으로 정부 지침에 따라 패스워드는 복호화할 수 없는(암호화 방식에 따라 다르지만) 랜덤한 임의의 값으로 암호화 시키지 않으면 형사적 처벌을 받을 수도 있다. 때문에 서버단에서 적절한 상황에 어울리는 인코딩 방식에 따라(Base64 또는 HS256 등등) 단방향 암호화를 적용할지, 양방향 암호화를 적용할지를 정의하고 유저로부터 POST(보안을 위해) 방식으로 비밀번호를 입력받아 암호화 하여 DB에 저장한다. DB에 암호화 되어 저장된 값을 로그인 시에 확인할 때는 동일한 알고리즘을 사용하여 로그인 시에 입력받은 값을 암호화하면 복호화 할 필요없이 DB에 있는 값과 동일한 Value를 가지게 되므로 이를 Match 하여 동일 값인지만 확인하면 본인 확인을 할 수 있다.

사용자의 패스워드를 관리하기 위해서는 Spring Security의 BCryptPasswordEncoder를 통한 BCrtpt 형식의 해시 함수로 인코딩이 필요합니다. 사용자가 패스워드를 전송하면 BCryptPasswordEncoder로 구현된 encoder() 메서드를 사용해 인코딩하게 되고, 이는 단방향 흐름으로 진행됩니다. 추가로 일치 여부 판단을 위해서 matches() 메서드를 사용합니다.

사용자의 패스워드는 단방향인 해싱, 양방향인 암호화로 전송 및 보관이 가능하다. 해싱은 복호화가 불가능하며, 암호화는 복호화가 가능하다. 따라서, 대부분의 개발자들은 단방향 해시로 안전하게 패스워드를 전송 및 보관하려고 한다. 단방향 해시 함수는 어떤 수학적 연산 및 알고리즘에 의해 원본 데이터를 완전히 다른 암호화된 데이터로 변환시키는 것이다. 이렇게 변환된 데이터를 다이제스트라고 한다. 단점으로는 동일한 메세지는 동일한 다이제스트를 갖고있어 레인보우 테이블을 통해 메세지의 원문을 찾을 수 있다. 또한 상징성 있는 문자를 추려서 조합하여 브루트포스 공격을 당할 수 있다. 단방향 해시 함수를 보완하기 위해서 해시 함수를 여러번 수행하거나 해시함수를 돌리기 전 원문에 임의의 문자열을 덧붙이는 솔트를 사용하여 보완할 수 있으며, 둘을 모두 사용할 수 있다.

2023.05.24 - [Mockterview] - 사용자 패스워드를 전송하고 보관하는 방법(일반적인 보안 방법) pt.2

시간 복잡도와 공간 복잡도는 알고리즘의 효율성을 측정하는 두 가지 주요 지표입니다.

시간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 시간을 나타냅니다. 입력 크기에 따라 얼마나 많은 계산이 필요한지를 설명합니다. 예를 들어, 'O(n)'의 시간 복잡도를 가진 알고리즘이 있다면, 입력 데이터의 크기 n에 비례하여 시간이 증가한다는 것을 의미합니다.

공간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리 공간을 나타냅니다. 입력 크기에 따라 얼마나 많은 저장 공간이 필요한지를 설명합니다. 예를 들어, 'O(n)'의 공간 복잡도를 가진 알고리즘이 있다면, 입력 데이터의 크기 n에 비례하여 메모리 사용량이 증가한다는 것을 의미합니다.

개발자는 시간 복잡도와 공간 복잡도를 모두 고려하여 알고리즘을 선택하고 구현해야 합니다. 일반적으로 두 가지 복잡도 사이에는 트레이드오프(trade-off) 관계가 있습니다.

즉, 시간 복잡도를 줄이려면 더 많은 메모리를 사용해야 할 수 있고, 반대로 메모리 사용량을 줄이려면 더 많은 계산이 필요할 수 있습니다. 

어떠한 알고리즘의 성능 평가가 필요할 때 복잡도의 척도를 사용하는데 그 복잡도가 낮을수록 좋은 알고리즘입니다. 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미하고 공간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 차지하는 공간(메모리)을 의미합니다.

시간 복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타냅니다. 시간 복잡도에는 빅오 표기법이라는 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법을 사용합니다. 공간 복잡도는 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타냅니다. 알고리즘을 실행시키기 위해 필요한 공간은 고정 공간과 가변 공간이 있습니다.

시간복잡도(time complexity)란 알고리즘을 실행하여 종료할때까지 필요한 시간 입니다. 공간복잡도(space complexity)란 알고리즘을 실행하여 종료할때까지 필요한 기억창치의 크기 입니다. 시간복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는지를 센 결과에 각 명령어의 실행시간을 곱한 합계를 의미합니다. 그러나 각 명령어의 실행 시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 됩니다. 공간 복잡도는 알고리즘과 무관한 부분과 밀접한 부분으로 분류 할 수 있는데, 일반적으로 공간 복잡도를 분석할때는 알고리즘과 밀접한 부분 , 알고리즘의 특성과 밀접한 관계가 있는 부분으로써 문제를 해결하기 위해 필요로 하는 공간, 즉, 변수를 저장하기 위한 공간이나 순환 프로그램일 경우 순환스택을 계산하여 공간 복잡도를 계산합니다.

최근에는 대용량 시스템이 보편화되면서 공간복잡도보다는 시간복잡도가 중심이 되고 있습니다.

** 빅 오 표기법(Big O notation)은 알고리즘의 복잡도를 표현하는 방법입니다. 이는 알고리즘이 처리해야 하는 데이터의 크기에 따라 시간 복잡도와 공간 복잡도가 어떻게 증가하는지를 설명하는 표기법입니다.

빅 오 표기법은 알고리즘의 최악의 성능을 표현합니다. 즉, 입력 크기가 무한대로 가정했을 때, 알고리즘이 어떻게 수행될지에 대한 상한선을 설명합니다.

다음은 몇 가지 일반적인 빅 오 표기법의 예입니다:

• O(1): 상수 시간 복잡도. 입력 데이터의 크기와 관계없이 알고리즘의 실행 시간이 일정합니다. 예를 들어, 배열의 특정 인덱스에 있는 요소에 접근하는 작업은 O(1)의 시간 복잡도를 가집니다.
• O(n): 선형 시간 복잡도. 입력 데이터의 크기와 알고리즘의 실행 시간이 직접적으로 비례합니다. 예를 들어, 배열의 모든 요소를 한 번씩 방문하는 작업은 O(n)의 시간 복잡도를 가집니다.
• O(log n): 로그 시간 복잡도. 입력 데이터가 증가함에 따라 알고리즘의 실행 시간은 로그 증가합니다. 예를 들어, 이진 검색 알고리즘은 O(log n)의 시간 복잡도를 가집니다.
• O(n^2): 제곱 시간 복잡도. 입력 데이터의 크기의 제곱에 비례하여 알고리즘의 실행 시간이 증가합니다. 예를 들어, 버블 정렬 같은 간단한 정렬 알고리즘은 O(n^2)의 시간 복잡도를 가집니다.

이와 같이 빅 오 표기법은 알고리즘의 성능을 분석하고 다른 알고리즘과 비교하는 데 중요한 도구입니다.

**알고리즘의 공간 복잡도를 분석할 때, 고정 공간(fixed space)와 가변 공간(variable space)라는 두 가지 요소를 고려합니다.

1. 고정 공간(Fixed Space): 이는 알고리즘이 실행되는 동안 변경되지 않는 메모리 공간을 의미합니다. 고정 공간에는 알고리즘에서 사용하는 변수, 상수, 고정 배열 등이 포함됩니다. 입력의 크기에 관계없이 이 공간의 크기는 변하지 않습니다.
2. 가변 공간(Variable Space): 이는 알고리즘 실행 동안 변경될 수 있는 메모리 공간을 의미합니다. 이 공간은 입력의 크기나 알고리즘의 특정 조건에 따라 달라질 수 있습니다. 가변 공간에는 동적으로 할당되는 데이터 구조(예: 연결 리스트, 스택, 큐, 동적 배열 등), 재귀 스택 프레임 등이 포함될 수 있습니다.

알고리즘의 전체 공간 복잡도는 이 두 가지 공간의 합으로 계산되며, 일반적으로 가변 공간이 고정 공간보다 더 큰 영향을 미칩니다. 따라서 공간 복잡도 분석 시 주로 가변 공간에 초점을 맞춥니다.

1. 동적으로 할당되는 데이터 구조: 이는 프로그램 실행 중에 데이터의 크기가 변할 때 사용하는 데이터 구조입니다. 예를 들어, 리스트, 스택, 큐, 동적 배열 등이 이에 해당합니다. 이들은 데이터의 개수나 크기에 따라 메모리 공간을 늘리거나 줄일 수 있습니다.
2. 재귀 스택 프레임: 재귀 함수는 함수가 자기 자신을 호출하는 방식으로 작동하는데, 이때 각 함수 호출마다 메모리 스택에 프레임이 생성됩니다. 이 프레임은 함수의 변수, 매개변수 등을 저장하는데 사용되는데, 함수 호출이 끝나면 이 프레임은 사라집니다. 따라서 재귀 함수의 깊이(즉, 함수가 자기 자신을 몇 번 호출하는지)에 따라 필요한 메모리 공간이 달라집니다.

시간 복잡도 예시:

데이터 배열에서 특정 요소를 찾는 문제를 가정

1. 선형 검색(Linear Search): 이 방법은 각 요소를 하나씩 차례로 확인하여 원하는 값을 찾습니다. 최악의 경우, 배열의 모든 요소를 확인해야 하므로 시간 복잡도는 O(n)입니다.
2. 이진 검색(Binary Search): 이 방법은 배열이 정렬되어 있을 때 사용할 수 있습니다. 중간 값과 찾고자 하는 값을 비교하여 검색 범위를 절반씩 줄여나갑니다. 이렇게 로그 시간에 원하는 값을 찾을 수 있으므로 시간 복잡도는 O(log n)입니다.

이 두 가지 방법을 비교하면, 이진 검색이 선형 검색보다 더 빠르지만, 이진 검색을 사용하려면 배열이 먼저 정렬되어 있어야 한다는 제약이 있습니다.

공간 복잡도 예시: 재귀를 사용하는 알고리즘과 그렇지 않은 알고리즘의 비교

• 반복문을 사용한 팩토리얼 계산: 이 경우, 단지 몇 개의 변수만 필요하므로 공간 복잡도는 O(1)입니다.

public int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

• 재귀를 사용한 팩토리얼 계산: 이 경우, 재귀 호출이 발생할 때마다 스택에 새로운 레이어가 추가됩니다. 따라서 n이 증가함에 따라 메모리 사용량도 증가하므로 공간 복잡도는 O(n)입니다.

public int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

이 두 가지 방법을 비교하면, 반복문을 사용하는 방법이 재귀를 사용하는 방법보다 메모리 사용량이 적지만, 재귀를 사용하는 방법이 코드를 더 간결하고 이해하기 쉽게 만들 수 있습니다. 

1. 포트폴리오에서 시간복잡도를 낮춘 사례가 있다면 설명해주실 수 있을까요?

1. 인덱싱: 데이터베이스에서 데이터 조회 속도를 높이기 위한 주요 방법 중 하나는 인덱싱입니다. 인덱스는 테이블의 데이터를 빠르게 탐색할 수 있도록 도와줍니다. 적절한 인덱스를 설정함으로써, DBMS는 전체 테이블을 스캔하지 않고도 필요한 데이터를 빠르게 찾을 수 있습니다.
2. 필요한 데이터만 조회: 전체 엔티티를 조회하는 대신 필요한 필드만 선택하여 조회하면, 데이터 전송량을 줄이고 처리 시간을 단축할 수 있습니다. 이는 특히 대용량 데이터를 다룰 때 유용합니다.
3. 카운트 쿼리 사용: 페이지네이션을 구현할 때, 전체 데이터의 수를 알아야 할 필요가 종종 있습니다. 이럴 때 별도의 카운트 쿼리를 사용하면, 전체 데이터를 불러온 후 개수를 세는 비효율적인 작업을 피할 수 있습니다.
4. 레디스(Redis)는 인메모리 데이터베이스로, 데이터를 메모리에 저장하기 때문에 디스크 기반의 데이터베이스보다 훨씬 빠른 처리 속도를 보여줍니다. 이런 특성 때문에 레디스는 주로 캐싱, 세션 관리, 토큰 저장 등에 사용되며, 이러한 작업들은 대개 시간 복잡도가 O(1)입니다. 여기서 O(1)이란 알고리즘의 시간 복잡도 표기법으로, 입력 데이터의 크기와 상관 없이 알고리즘의 실행 시간이 일정하다는 것을 의미합니다. 즉, 레디스에서 키-값 쌍을 사용하여 데이터를 조회하거나 저장하는데 필요한 시간은 데이터의 양에 관계없이 거의 일정합니다.
5. 데이터베이스에서 인덱스를 사용하면 특정 데이터를 찾는 속도를 크게 향상시킬 수 있습니다. 예를 들어, LIKE '%word%'와 같은 검색 쿼리는 데이터베이스에서 전체 행을 스캔하므로 시간 복잡도가 O(n)이 됩니다. 하지만 B-Tree 인덱스를 사용하면 데이터를 로그 시간에 찾을 수 있게 되어 시간 복잡도가 O(log n)으로 줄어듭니다.
6. 또한, 불필요한 코드를 제거하고, 중첩된 반복문을 최적화하고, 더 효율적인 알고리즘을 사용하여 시간 복잡도를 줄이는 것은 모든 프로그래밍 작업에서 중요합니다.

CORS는 Cross-Origin Resource Sharing/교차 출처 리소스 공유 의 줄임말로, 다른 도메인으로부터 리소스가 요청될 경우, 해당 도메인에서 요청이 허용되는지를 결정하는 메커니즘이라고 볼 수 있습니다. 웹 페이지는 보안 상의 이유로 같은 출처(same-origin) 정책을 따르는데, 이는 한 도메인에서 로드된 웹 페이지가 다른 도메인에 있는 리소스를 요청할 때 이를 제한하는 정책입니다.

CORS는 이 같은 출처 정책을 특정 조건 하에 완화시켜, 안전하게 다른 도메인의 리소스에 접근할 수 있게 해주는 방법입니다. 이는 웹 서버 측에서 HTTP 헤더를 사용해 구현되며, 어떤 도메인, 메소드, 헤더가 CORS를 통해 자원에 접근할 수 있는지를 설정할 수 있습니다.

CORS는 프론트엔드와 백엔드가 다른 도메인에 위치하는 경우나, API 서버를 별도로 두는 등의 상황에서 중요한 개념입니다. 하지만 잘못 설정된 CORS는 보안 문제를 일으킬 수 있으므로, 어떤 요청을 허용할지 신중하게 결정해야 합니다.

스프링에서는 CORS 설정을 위해 WebMvcConfigurer 인터페이스를 구현하거나, @CrossOrigin 어노테이션을 사용할 수 있습니다.

예를 들어, 모든 요청에 대해 CORS를 허용하도록 설정하려면 스프링의 설정 클래스에서 WebMvcConfigurer를 구현하는 방법이 있습니다:
addMapping("/**")는 모든 요청 경로에 대해, allowedOrigins("*")는 모든 출처에 대해, allowedMethods("*")는 모든 HTTP 메소드에 대해 CORS를 허용하도록 설정합니다.

@Configuration
public class WebConfig implements WebMvcConfigurer {

    @Override
    public void addCorsMappings(CorsRegistry registry) {
        registry.addMapping("/**")
                .allowedOrigins("*")
                .allowedMethods("*");
    }
}

또는, 특정 컨트롤러나 핸들러 메소드에 대해 CORS를 허용하려면 @CrossOrigin 어노테이션을 사용할 수 있습니다:
@CrossOrigin 어노테이션에서 origins 속성은 허용할 출처를, allowedHeaders 속성은 허용할 요청 헤더를, methods 속성은 허용할 HTTP 메소드를 지정합니다. 아래 예시에서는 모든 출처, 헤더, GET 및 POST 메소드에 대해 CORS를 허용하도록 설정했습니다.

@RestController
@CrossOrigin(origins = "*", allowedHeaders = "*", methods = {RequestMethod.GET, RequestMethod.POST})
public class MyController {
    // ...
}

Cross-Origin Resource Sharing(교차 출처 리소스 공유) 의 약자로 브라우저에서 실행 중인 스크립트에서 시작되는 cross-origin HTTP 요청을 제한하는 브라우저 보안 기능이다. 브라우저는 same-origin policy(동일 출처 정책)에 의해 cross-origin의 리소스를 요청을 차단한다. 제일 쉬운 해결방안은 서버 단에서 특정 origin 혹은 모든 origin 을 허용하도록 설정 하면 된다. 하지만 여기에서 끝나면 GET, POST 요청은 정상적으로 요청이 되지만 HEAD, PUT, DELETE HTTP method에 대해서는 CORS가 발생한다. SpringBoot 에서는 allowedOrigins 를 통해 CORS허용을 하면 기본적으로 GET, POST, HEAD 만 허용을 해준다. 따라서 allowedMethods를 이용해 허용할 HTTP Method를 추가해준다.

교차 출처 리소스 공유(Cross-Origin Resource Sharing)의 약자입니다. 리소스를 공유할 때 브라우저는 출처(Origin)- 프로토콜, 호스트, 포트가 동일한지 비교하고 다를 경우 차단하게 됩니다. 클라이언트의 경우 HTTP요청의 헤더에 Origin을 담아 서버에 전달하게 될텐데 서버는 Access-Control-Allow-Origin 헤더에 허용할 출처를 기재해서 클라이언트에 응답하여 허용해주면 되는 것입니다.

Cross-Origin Resource Sharing, 교차 출처 리소스 공유 라는 뜻으로 브라우저에서 보안적인 이유로 제한된 요청들을 안전하게 처리할 수 있도록 서버에서 허가를 해주는 메커니즘입니다. 서버측 응답에서 접근 권한을 주는 Access-Control-Allow-Origin 응답 헤더를 추가하여 브라우저가 해당 origin이 자원에 접근할 수 있도록 허용할 수 있습니다.

CORS (Cross Origin Resource Sharing) 란 가져오는 리소스들이 안전한지 검사하는 브라우저의 방화벽이라고 생각합니다. Cross-Origin Resource Sharing" 문장을 직역하면 "교차 출처 리소스 공유 정책"이라고 해석할 수 있는데, 여기서 교차 출처라고 하는 것은 (엇갈린) 다른 출처를 의미하는 것으로 보면 됩니다. 여기서 Origin이란 Protolcol 과 Host 그리고 Port 까지 모두 합친 URL을 의미합니다. Access-Control-Allow-Origin 응답 헤더 세팅 서버측 응답에서 접근 권한을 주는 헤더를 추가하여 해결할 수 있습니다. 

다른 출처 소스를 허용해준다는 의미이다. 이와 반대되는 개념으로 SOP라는 동일출처공유가 있다. => 자신의 컴퓨터에서 서버에게 요청을 보내고 request가 왓는데 같은 주소(포트 포함)이 아니라면 SOP를 지키기 위해 차단한다.(기본 SOP를 지키게 Default). => 이렇게 설정되어 있는 이유는 자바스크립트를 받아왔을때 그 기능이 해킹에 관련 되어 있는 사이트요청을 보내는 것이라면 요청을 보내고 응답으로 악성코드가 들어올수 있기 때문이다. 이를 허용해 주기위해서는 springboot security에서 cors를 허용하고 그 설정값 매겨주어야 한다. => 설정값에는 어느 주소, 허용할 헤더 key, 허용할 메소드(Post등) 등이 있다. 원리는 서버가 요청에 대한 응답을 보낼때 ~~출처는 받아도되 검증되어 있어 라고 보내는것

CORS를 설명하기 위해서는 SOP를 먼저 설명해야한다. SOP는 동일한 origin으로만 요청을 보낼 수 있는 브라우저의 보안 정책이다. SOP때문에 다른 origin으로 요청을 보내는 것이 금지되어 있는데 다른 origin간의 데이터 교환의 필요성이 늘어나자 특정 정책을 지키는 경우에는 다른 origin으로의 요청을 허가할 수 있도록 되었는데 그 정책이 CORS다. 즉, CORS는 다른 origin으로 요청을 보내기위해서 지켜야하는 정책 혹은 규칙이다. CORS의 동작원리는 다음과 같다. 요청을 보낼 때 origin 헤더에 본인의 origin을 입력해서 요청을 보낸다. 서버는 허용가능한 origin을 헤더에 실어서 응답한다. 클라이언트는 응답의 허용 헤더에서 본인의 origin이 속해있으면 응답을 받아 들인다.

CORS는 교차 출처 리소스 공유의 약자이다. 웹 애플리케이션에서 다른 도메인의 자원을 요청하는 경우 발생하는 보안 문제를 해결하기 위한 방법이다. 보안상의 이유로 브라우저는 동일한 출처에서만 HTTP 요청을 보낼 수 있도록 제한하고 있다. 그러나 웹 애플리케이션을 개발하다 보면, 다른 도메인의 자원(이미지, API)을 요청해야 하는 경우가 생긴다. 이때 CORS를 사용하면 다른 도메인의 자원도 요청할 수 있다. CORS를 허용하려면 서버에서 Access-Control-Allow-Origin 헤더를 설정한다. 이 헤더는 어떤 도메인에서 요청이 허용되는지 설정한다. 모든 도메인에서 요청을 허용하려면 “*” 값을 설정한다. 스프링에서는 allowedOrigins를 통해 CORS를 허용하는데 기본적으로 GET, POST, HEAD만 허용한다. 따라서 allowedMethods를 통해 허용할 HTTP Method를 추가한다.

CorsConfigurationSource을 사용하여 허용할 CORS를 지정해준 후 filterChain에 등록하여 허용해줍니다.

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.web.cors.CorsConfiguration;
import org.springframework.web.cors.CorsConfigurationSource;
import org.springframework.web.cors.UrlBasedCorsConfigurationSource;
import org.springframework.web.filter.CorsFilter;
import org.springframework.security.config.annotation.web.builders.HttpSecurity;
import org.springframework.security.config.annotation.web.configuration.WebSecurityConfigurerAdapter;

import java.util.Arrays;

@Configuration
public class SecurityConfig extends WebSecurityConfigurerAdapter {

    @Override
    protected void configure(HttpSecurity http) throws Exception {
        http.cors().and() // enable CORS
            // other configurations
    }

    @Bean
    public CorsConfigurationSource corsConfigurationSource() {
        CorsConfiguration configuration = new CorsConfiguration();
        configuration.setAllowedOrigins(Arrays.asList("*")); // or specify specific origins 
        configuration.setAllowedMethods(Arrays.asList("GET","POST", "PUT", "DELETE", "OPTIONS")); // or specify specific HTTP methods
        configuration.setAllowedHeaders(Arrays.asList("*")); // or specify specific request headers
        UrlBasedCorsConfigurationSource source = new UrlBasedCorsConfigurationSource();
        source.registerCorsConfiguration("/**", configuration);
        return source;
    }
}

** CORS 는 에러인가요? 

CORS(Cross-Origin Resource Sharing)는 자체적으로 오류나 에러를 나타내는 것은 아닙니다. CORS는 웹 페이지의 요청이 어떠한 출처에서 왔는지를 식별하고, 이를 기반으로 서버가 이 요청을 수용할지를 결정하는 메커니즘입니다. 

만약 CORS 관련 에러 메시지를 보았다면, 그것은 웹 페이지가 다른 출처(origin)에 있는 리소스에 접근하려 했지만 해당 서버에서 이를 허용하지 않았기 때문일 가능성이 높습니다. 이런 상황은 웹 보안을 위해 존재하는데, 같은 출처 정책(Same-Origin Policy)을 지키기 위함입니다. 같은 출처 정책은 특정 웹 페이지가 다른 출처의 리소스에 자유롭게 접근하지 못하도록 제한하는 보안 방침입니다.

CORS를 통해 서버는 특정 웹 페이지에 대해 리소스 접근을 허용할 수 있습니다. 이를 위해 서버는 응답 헤더에 'Access-Control-Allow-Origin'을 추가해야 합니다. 이 헤더가 없거나 해당 웹 페이지의 출처를 허용하지 않으면, 웹 브라우저는 CORS 정책 위반으로 인해 에러를 발생시킵니다. 이를 해결하기 위해서는 서버 설정을 변경하여 적절한 CORS 헤더를 포함하도록 해야 합니다.

배열과 링크드리스트는 둘 다 컴퓨터 과학에서 사용하는 기본적인 데이터 구조입니다 .

데이터의 크기가 고정되어 있고, 특정 요소에 빠르게 접근해야 하는 경우에는 배열을 사용하는 것이 좋습니다.
반면에, 데이터의 크기가 동적으로 변하고, 요소의 추가와 삭제가 빈번한 경우에는 링크드리스트를 사용하는 것이 좋습니다.

배열과 링크드리스트는 데이터를 저장하는 방식이 다릅니다.

배열은:

• 데이터를 연속적인 메모리 공간에 저장합니다. 즉, 한 줄로 나란히 놓는 것을 생각하시면 됩니다.
• 각 데이터는 번호(인덱스)가 있어서 바로 접근할 수 있습니다.
• 하지만 나머지 데이터를 이동시켜야 하기 때문에 크기를 변경하거나 중간에 데이터를 추가하거나 삭제하는 것은 번거롭습니다.
• • 배열은 고정된 크기를 가지며, 연속된 메모리 공간에 동일한 타입의 데이터를 저장합니다.
  • 배열의 각 요소는 인덱스를 통해 직접 접근할 수 있으므로, 특정 요소에 대한 조회는 O(1)의 시간 복잡도를 가집니다.
  • 하지만, 배열의 크기는 생성 시점에 결정되며 변경할 수 없기 때문에, 크기를 확장하거나 축소하려면 전체 배열을 복사해야 합니다. 이는 O(n)의 시간 복잡도를 가집니다.
  • 배열에 요소를 추가하거나 삭제하는 연산도 O(n)의 시간 복잡도를 가집니다. 왜냐하면 요소를 추가하거나 삭제한 후에 배열의 다른 요소들을 이동해야 하기 때문입니다.

public class ArrayExample {
    public static void main(String[] args) {
        // 크기가 5인 정수 배열 생성
        int[] array = new int[5];

        // 배열에 값 할당
        for(int i=0; i<array.length; i++) {
            array[i] = i * 2;
        }

        // 배열 출력
        for(int i=0; i<array.length; i++) {
            System.out.println("Element at index " + i + ": " + array[i]);
        }
    }
}

링크드리스트는:

• 각 데이터(노드)가 다음 데이터를 가리키는 방식으로 저장합니다. 이런 노드들이 연결되어 있는 것을 생각하시면 됩니다.
• 데이터를 추가하거나 삭제하는 것은 쉽지만, 특정 데이터를 찾으려면 처음부터 하나씩 따라가야 합니다.
• 따라서 중간에 데이터를 추가하거나 삭제하는 경우에 유용합니다.
• 링크드리스트는 동적인 크기를 가지며, 비연속적인 메모리 공간에 데이터를 저장합니다. 각 요소(노드)는 데이터와 다음 노드에 대한 참조를 가지고 있습니다.
• 링크드리스트의 요소는 인덱스를 통해 직접 접근할 수 없으므로, 특정 요소에 대한 조회는 O(n)의 시간 복잡도를 가집니다. 왜냐하면 특정 요소를 찾기 위해 리스트를 순회해야 하기 때문입니다.
• 하지만, 링크드리스트는 동적으로 크기를 변경할 수 있으므로, 요소를 추가하거나 삭제하는 연산은 O(1)의 시간 복잡도를 가질 수 있습니다. 하지만 이는 해당 위치의 참조가 이미 알려져 있을 때만 가능합니다. 그렇지 않은 경우에는 O(n)의 시간 복잡도를 가집니다.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // LinkedList 생성
        LinkedList<String> linkedList = new LinkedList<>();

        // LinkedList에 요소 추가
        linkedList.add("Element 1");
        linkedList.add("Element 2");
        linkedList.add("Element 3");

        // LinkedList 출력
        for(int i=0; i<linkedList.size(); i++) {
            System.out.println("Element at index " + i + ": " + linkedList.get(i));
        }
    }
}

** 노드(Node)는 데이터를 담는 공간입니다.

예를 들어, 링크드리스트에서는 각 데이터가 저장되는 곳을 '노드'라고 부릅니다.

또한, 링크드리스트의 노드는 다음 노드를 가리키는 정보도 함께 저장하고 있습니다.

** O(n)의 시간 복잡도는 컴퓨터가 어떤 일을 하는데 걸리는 시간을 나타내는 표현 방식 중 하나입니다.

여기서 'n'은 데이터의 개수를 의미하고, O(n)은 '데이터 개수에 비례하여 시간이 걸린다'는 의미입니다.

예를 들어, 데이터가 10개 있을 때 10초가 걸리면, 데이터가 100개 있을 때는 100초가 걸린다는 뜻입니다.

간단히 말해, 배열에서는 어떤 데이터를 찾아가는데 한번에 갈 수 있지만,

링크드리스트에서는 첫 번째 데이터부터 하나씩 따라가며 찾아야 해서 시간이 더 걸린다는 것입니다.

이 때문에 링크드리스트에서 데이터를 찾는 시간을 O(n)으로 표현합니다.

**O(1)의 시간 복잡도는 어떤 작업을 수행하는 데 걸리는 시간이 데이터의 개수와 상관없이 항상 일정하다는 것을 의미합니다.

배열에서 특정 위치의 데이터에 바로 접근하는 것은 O(1)의 시간 복잡도를 가집니다.

왜냐하면 배열에서 각 데이터는 인덱스를 통해 바로 접근할 수 있기 때문입니다.

배열의 크기가 늘어나도, 특정 위치의 데이터에 접근하는데 걸리는 시간은 변하지 않습니다.

Array는 연속된 메모리 공간에 존재하고 Linked List는 메모리 상에서 떨어져 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하는 형태로 존재한다. Array에 저장되어 있는 데이터를 조회할 때는 O(1)로 가능하지만 Linked List는 O(N)이 소요된다. Array에 데이터 추가 및 삭제할 때는 O(N)이 소요되지만 Linked List는 O(1)로 가능하다. 추가적으로 Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당인 반면 Linked List는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다. 또한 배열은 Stack 영역에 메모리 할당이 되고, Linked List는 Heap 영역에 할당이 된다.

추가/삭제가 많다면 링크드리스트, 탐색/정렬이 많다면 배열을 사용하는 게 유리하다. 둘 다 선형 데이터 구조지만, 배열은 물리적으로도 연속된 메모리를 사용하고 링크드리스트는 다음 노드의 위치를 저장함으로써 흩어진 메모리를 연결해서 쓴다는 게 둘 사이의 차이점을 만드는 주요한 요인이다. 링크드리스트의 장점은 데이터의 추가/삽입 및 삭제가 용이하다. 즉, 새로운 노드를 끼워넣기 쉽다. 길이를 동적으로 조절 가능하다. 단점은 인덱스없이 연결관계만 있기 때문에 특정 노드를 불러내기 어렵다. (일반적으로) O(N)이 걸리며 순차적으로 탐색하게 되기 때문이다.(B+tree자료구조 등은 예외) 거꾸로 탐색하기도 어렵다. 정렬은 O(NlogN)이 걸린다. 배열의 장점은 자료마다 인덱스가 있어서 특정 자료를 불러내기 편하다. 단점은 연속된 메모리 공간을 할당받아야 하다보니 크기를 크게 키우기가 어렵다. 또한, 안 쓰는 공간까지 전부 예약해두고 있어야 하므로 공간 낭비가 생긴다.

배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이며 메모리상에서 연속적으로 저장되어 있는 특징을 갖기 때문에 index를 통한 접근이 용이하다는 장점이 있으나 삽입/삭제가 오래 걸리고 배열 중간의 데이터가 삭제 되면 공간 낭비가 발생할 수 있는 단점이 존재합니다. 링크드리스트(연결리스트)는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있는 트리(tree)구조의 근간이 되는 자료구조입니다. 배열과 달리 메모리를 연속적으로 사용하지 않아 삽입/삭제에 용이하다는 장점이 있습니다. 그러나 index로 임의 접근이 불가하며 처음부터 탐색을 해야하는 단점이 있습니다. 따라서 배열은 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 사용하고 링크드리스트는 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 사용합니다.

** 배열,링크드리스트 사용 예시:

영화관의 좌석 배치의 경우 각 좌석은 행과 열에 따라 정확한 위치를 가지고 있습니다.

이러한 좌석 배치는 '배열'과 유사하게 생각할 수 있습니다.

좌석의 번호(예: A열 5번)를 알면, 해당 좌석을 즉시 찾아갈 수 있습니다. 이렇게 빠르게 접근이 가능한 것은 배열의 특징입니다.

하지만 한번 정해진 좌석 배치(배열의 크기)는 변경하기 어렵습니다.

즉, 중간에 좌석을 추가하거나 제거하기는 어렵다는 것이 배열의 단점입니다.

기차의 경우 각각의 칸(= 노드)이 연결되어 있습니다.

각 칸은 다음 칸을 '가리키고' 있습니다. 이것이 바로 링크드리스트의 구조입니다.

기차는 필요에 따라 칸을 추가하거나 제거할 수 있습니다. 이렇게 동적으로 크기를 변경하는 것이 링크드리스트의 장점입니다.

하지만, 특정 칸에 바로 접근하려면 기차의 첫 칸부터 시작해서 원하는 칸을 찾을 때까지 한 칸씩 이동해야 합니다.

이렇게 특정 위치에 접근하는 데에 시간이 더 걸리는 것이 링크드리스트의 단점입니다.