코딩테스트

쏟아지는 코테들 앞두고 답답해서 하는 Java 코딩테스트 문법 정리한 번 만들어지면 문자를 추가하거나 삭제할 수 없는 변경 불가한 타입많은 문자열을 연결하면 많은 중간 문자열 객체가 생성되어 비효율적(성능 저하)한 번 만든 후에도 변경이 가능한 타입String을 연결하

원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시켜 저장하는 방식의 선형 자료구조K번째 원소를 확인/변경하기 위해 O(k)가 필요임의의 위치에 원소를 추가/제거는 O(1)단일 연결 리스트(Singly Linked List)각 원소가 자신의 다음 원소의 주소를 포함

정점(vertex)과 간선(edge)들의 집합그래프가 이루어진 정점과 간선의 숫자 집합1 21 32 42 5 3 43 14 25 2인접행렬 구하기그래프가 이루어진 정점과 간선의 숫자 집합1 3 1 23 44 22 5인접행렬 구하기그래프가 이루어진 정점과 간선의 숫자 집

키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근키 값의 연산에 의해 직접 접근이 가능한 구조<key, value>로 이루어짐Map 인터페이스의 구현체로 value들이 key에 mapping되어있음👉 <key, value>key 값 중

a를 b로 나눈 나머지(단, a>b) = ra와 b의 최대공약수 = b와 r의 최대공약수b를 r로 나눈 나머지 r1을 구하고, 다시 r을 r1로 나눈 나머지를 구하는 과정을 반복해 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수최소공배수 = 두 자연수의 곱/

N이 주어졌을 때 N을 2부터 N-1까지의 모든 수로 나누어봐 나누어떨어지는 수가 하나라도 존재하면 소수 아님=> 시간복잡도가 O(N)이기에 비효율적알고리즘 개선: 제곱근까지만 확인하면 됨=> 시간복잡도가 O(N의 2분의 1승)여러 개의 수가 소수인지 아닌지를 판별할

가까운 노드부터 우선적으로 탐색 (넓게 탐색)그래프 탐색에 사용두 노드 사이의 최단 경로 혹은 임의의 경로를 찾을 때 사용큐를 이용해 구현 (선입선출)루트 노드에서 시작해 거리에 따라 단계별로 탐색재귀적으로 동작하지 않음어떤 노드를 방문했는지에 대한 여부를 반드시 검사

다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색모든 노드를 방문할 때 사용단순 검색 속도는 BFS가 더 빠름자기 자신을 호출하는 순환 알고리즘의 형태방문한 노드 여부 반드시 검사스택 사용해 구현거리 계산할 땐 사용할 수 없음그래프 전체 탐색전위 순회(표기법)미로

다음 순열(Next Permutation) 순열 및 조합을 생성할 때 재귀적으로 구현하지 않고, 각 인덱스 값을 비교하여 모든 경우의 인덱스 값을 뽑아내는 방법 과정 1.순열을 사전순(오름차순)으로 생성 가장 작은 값부터 가장 큰 값이 될 때 까지 한 자리씩 s

완전 탐색 모든 경우의 수를 전부 탐색해보는 알고리즘 다음과 같은 방법이 있음 브루트포스 순열 백트래킹(재귀) 탐색 비트 마스크 DFS, BFS 탐색 완전탐색 사용법 다음을 고려하여 사용 해결하고자 하는 문제의 가능한 경우의 수 대략적으로 계산 가능한

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장해다시 큰 문제를 해결할 때 사용하는 것큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용일반적인 재귀를 단순 사용 시 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 됨DP를 사용하면 앞에서

욕심쟁이 알고리즘👉 현재 상황에서 지금 당장 좋은 것만 고르는 방법항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 함문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우

코드설명이차원 배열의 각 요소는 Fish 객체를 저장하는 ArrayList임map의 배열에는 list의 참조(주소)가 저장👉 즉, ArrayList가 각 위치에 대한 정보를 가지고 있는 것객체 변수에는 해당 객체의 참조가 저장되고, 이 참조를 통해 객체에 접근이를 통

정렬되지 않은 배열 안에서 특정 원소를 찾기 위해 인덱스 0부터 마지막까지 하나씩 차례대로 탐색시간 복잡도: O(n)정렬된 배열 안에서 특정 원소를 찾기 위해 중앙에 있는 값을 조사하여 찾고자 하는 원소가 왼쪽 혹은 오른쪽 배열에 있는지를 알아내 탐색의 범위를 반으로

투포인터 배열이나 리스트와 같은 선형 자료 구조에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 배열이나 원소 쌍을 찾는 기법 사용 예시 특정 합을 가지는 부분 수열의 개수 투포인터와 이분탐색의 차이 투포인터 주로 배열 내의 부분 배열이나 원소 쌍을 찾을