개공블

https://school.programmers.co.kr/learn/courses/30/lessons/181913# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr foreach문을 사용해 queries값을 하나씩 받아와 answerArray에 tempArray의 값을 query[1]값부터 query[0]까지 대입하도록 했다. 처음 코드는 아래와 같이 작성했다. public String solution(String my_string, int[][] queries) { char[] tempArray = my_string.toCharArray(); char[..

스택 스택은 삽입과 삭제 연산이 후입선출 (LIFO)로 이뤄지는 자료구조이다. 후입선출은 연산이 한쪽에서만 일어나는 특징이 있다. push : 데이터 삽입 pop : 데이터 삭제 후 확인 peek : 데이터 확인 스택은 깊이 우선 탐색 DFS, 백트래킹 종류의 코딩테스트에 많이 사용됨. 후입선출은 재귀함수와 원리가 비슷함. 큐 큐는 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조이다. rear : 큐의 가장 끝 데이터를 가리키는 영역 front : 큐의 가장 앞 데이터를 가리키는 영역 add : rear 부분에 새로운 데이터 삽입 poll : front 부분에 있는 데이터 삭제 후 확인 peek : front 부분에 있는 데이터 확인 큐는 너비 우선 탐색 BFS에서 많이 사용됨. 우선순위 큐 ..

구간 합 구간 합은 합 배열을 이용해 시간 복잡도를 더 줄이기 위해 사용하는 특수 목적의 알고리즘이다. 합 배열이란 ? 배열 A가 있다고 했을 때, 합 배열 S[i]는 A[0] ~ A[i]까지 합한 값을 의미한다. 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다. 합 배열 S를 만드는 공식 S{i] = S[i-1] + A[i] 위와 같은 배열이 있다고 할 때, S[1]은 위 공식에 따라 S[1] = S[0] + A[1]이므로 3 + 6 = 9가 된다. 구간 합을 구하는 공식 배열 A의 i ~ j까지의 구간 합은 다음과 같다. S[j] - S[i - 1] 만약 배열 A의 2 ~ 4까지의 구간 합을 구한다고 하면 위 공식에 따라 S[4] - S[..

시간복잡도 알고리즘에서 시간복잡도란 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 보통 1억번의 연산을 1초로 간주하여 예측한다. 시간 복잡도 유형 빅-오메가 : 최선일 때 연산 횟수를 나타낸 표기법 빅-세타 : 보통일 때 연산 횟수를 나타낸 표기법 빅-오 : 최악일 때 연산 횟수를 나타낸 표기법 이 중 코딩 테스트에서는 빅-오 표기법을 염두에 두고 풀어야 한다. 다양한 테스트 케이스를 수행해야 하므로 최악의 상황을 고려해야 한다. 빅-오 표기법의 시간 복잡도는 다음과 같다. O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!) 시간 복잡도 도출 기준 1. 상수는 시간 복잡도 계산에서 제외함. 2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복..