흰 스타렉스에서 내가 내리지

x의 n-거듭제곱인 x^n 을 계산하기 # 1. 억지기법 def slow_power(x, n): result = 1.0 for i in range(n): result *= x return result 3행의 반복문에 의해 n에 비례하는 시간이 거릴고, 따라서 시간복잡도가 O(n)이다. # 2. 축소 정복을 이용한 거듭제곱 1번 방법대로 x^10을 구하려면, 총 9번의 곱셈이 필요하다. 하지만 곱셈 한 번으로 x^2를 구하고, 이를 4번 곱하면, 총 5번의 곱셈으로 x^10을 구할 수 있다. 더 복잡하게 한다면, (x^2) * ( (x^2)^2 )^2 와 같은 방식으로, 총 4번의 곱셈으로 x^10을 구할 수 있다. def power(x, n): if n == 0: return 1 # 종료 조건 elif ..

# 1. 필터와 DispatcherType @Slf4j public class LogFilter implements Filter { @Override public void init(FilterConfig filterConfig) throws ServletException { log.info("log filter init!"); } @Override public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain) throws IOException, ServletException { HttpServletRequest httpRequest = (HttpServletRequest) request; String req..

Servlet(서블릿)은 자바 언어를 기반으로 하는 웹 애플리케이션 개발을 위한 서버 측 프로그래밍 기술 중 하나입니다. Servlet은 클라이언트의 요청에 동적으로 반응하고, 그 결과를 생성하여 다시 클라이언트에게 반환하는 역할을 합니다. 주로 웹 애플리케이션 서버에서 실행되며, Java EE(Enterprise Edition)와 Jakarta EE(이전의 Java EE)에서 사용됩니다. Servlet의 주요 특징과 개념은 다음과 같습니다: 1. 라이프사이클(Lifecycle): Servlet은 라이프사이클을 가지고 있습니다. 초기화, 서비스 처리, 소멸 등의 단계로 나뉩니다. 이 라이프사이클을 통해 Servlet은 특정 이벤트에 대한 처리를 수행할 수 있습니다. 2. HTTP 프로토콜 지원: 주로 H..

목차 서로소 집합 :: union-find 신장 트리 :: Spanning Tree 크루스칼 알고리즘 프림 알고리즘 위상 정렬 :: Topology Sort # 1. 서로소 집합 :: Disjoint Sets "서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조" - 서로소 집합을 union-find 자료구조 라고 부르기도 한다. - union과 find, 이 2개의 연산으로 조작할 수 있다. 1. union : - 2개의 집합을 하나의 집합으로 합치는 연산이다. 2. find : - 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - 스택과 큐 자료구조가 push와 pop 연산으로 이루어졌던 것처럼, 서로소 집합 자료구조는 union과 find 연산으로 구성된다. - 트리 자..

- 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 다익스트라 최단 경로 알고리즘 ✅ 플로이드 워셜 알고리즘 ✅ 벨만 포드 알고리즘 # 다익스트라 최단 경로 알고리즘 - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - '음의 간선'이 없을 때 정상적으로 동작한다. - 실제로 GPS 소프트웨어의 기본 알고리즘이다. - 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드..

'한 번 계산한 문제는 다시 계산하지 않도록 한다.' 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. # 메모이제이션 :: memoization - 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면, 메모한 결과를 그대로 가져오는 기법을 의미한다. - 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다. - 구현: 단순하게, 한 번 구한 정보를 리스트에 저장한다. - 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때에는 이미 구한 정답을 그대로 리스트에서 가져온다. # 다이나믹 프로그래밍과 분할 정복의 차이 - 다이나믹 프로그래밍은 ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net # Parametric Search - 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. - '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 파라메트릭 서치를 사용한다. - 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면, 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다. - 코딩 테스트에서는 보통 파라..

- 입력 데이터의 개수가 많은 문제에 input()을 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다. - 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하며 시간 초과를 피할 수 있다. import sys input_data = sys.stdin.readline().rstrip() - rstrip() 함수를 꼭 호출해야 한다. - 소스코드에 readline() 으로 입력하면 '\n' 도 입력되기 때문.

순차 탐색 이진 탐색 # 1. 순차 탐색 - 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다. - 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다. # 2. 이진 탐색 - 배열 내부에 데이터가 정렬되어 있어야만 사용할 수 있다. - 3개의 변수를 사용한다. → 시작점, 끝점, 그리고 중간점 - 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. - 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN) 이다. * 이진 탐색 구현 ..

선택 정렬 :: selection sort 삽입 정렬 :: insertion sort 퀵 정렬 :: quick sort 병합 정렬 :: merge sort 계수 정렬 :: count sort ... # 1. 선택 정렬 :: Selection Sort - O(N^2) - 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾼다. - 가장 원시적인 방법으로 매번 '가장 작은 것을 선택' 한다는 의미에서 선택 정렬 알고리즘이라 한다. arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(arr)): min_index = i for j in range(i+1, len(arr)): if arr[min_i..