~51일차~코딩테스트 스터디에서 강의를 듣고 정리해보았다.매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법시간 복잡도 O(N2)로 비효울적인 정렬 알고리즘 중 하나각 단계에서 가장 작은 원소를 선택현재 처리되지 않은 원소들 중 가장 앞의 원소와 위치를 교
~51일차~정렬 기능이 필요할 때 매우 효율적으로 사용 가능sort() : JavaScript에서 제공, 배열에 포함된 데이터를 정렬하는 함수알고리즘 및 코딩 테스트 문제를 해결할 때 정렬 기능이 필요하다면 사용 권장다음과 같은 형태로 사용 가능 arr.sort(com
~51일차~오답 : function 다음으로 answer 부분 적지않음오답 : 1번 문제의 정답으로 제출함2번 문제와 동일미제출
~51일차~오답 : 런타임 에러1번 문제와 거의 같아서 정답 예시와 동일하게 작성오답 : 중복된 원소 제거 방법을 알지 못함
~51일차~오답 : 런타임 에러\-오답정답 : 정답이긴 하나, 출현 빈도 계산은 하지 않음
~54일차~현재 상황에서 당장 가장 좋아 보이는 상황만을 선택하는 알고리즘주로 최적의 해를 구하기 위한 근사적인 방법으로 사용루트에서 출발하여 단말 노드까지 가는 경우거쳐가는 노드의 합이 가장 큰 경우를 구하자.Alt text보기에는 1 - 4 - 5가 가장 큰 값이
~54일차~https://www.acmicpc.net/problem/11047각 화폐 단위는 서로 배수관계가치가 큰 동전은 가치가 작은 동전들의 합으로 표현 가능① 모든 화폐 단위를 내림차순으로 정렬② 화폐의 단위를 확인하여, 해당 화폐로 나눌 때의 몫을 더하
~57일차~https://www.acmicpc.net/problem/28391) 현재 값이 5로 나누어 떨어지는 경우, 5로 나누면 될 것이다.2) 그렇지 않다면, 기존의 값이 5로 나누어 떨어지는 값이 될 때까지 3을 빼준 뒤 1)을 수행한다.미제출\-오답
~58일차~https://www.acmicpc.net/problem/13305주유 비용을 비오름차순으로 변경자기보다 뒤에 있는 비싼 주유소에 대해서 미리 결제\-오답 !vs에서는 예시 3개가 모두 정상출력되었는데 백준에서는 틀렸다고 나온다.https:
~58일차~https://www.acmicpc.net/problem/19939가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되려면?\-> 공의 개수가 최대한 연속적이게항상 정답은 K-1 혹은 K\-오답 - vs는 정상 출력되었는데
~94일차~시작점(left)와 끝점(end)을 기준으로 탐색 범위를 명시각 단계마다 탐색 범위를 2로 나누는 것으로 이해할 수 있다.이상적인 경우 매 단계마다 범위가 반으로 감소, 로그(log) 복잡도를 가진다.매우 넓은 범위(억 단위 이상)에서 최적의 해를 찾아야 하
코딩 테스트에서는 정렬된 배열에서 값이 특정 범위에 해당하는 원소의 개수를 계산하는 것을 종종 요구이러한 문제를 해결하기 위해 lowerBound()함수와 upperBound() 함수를 사용할 수 있다.lowerBound(arr, x) : 정렬된 순서를 유지하면서 배열
변경할(최적화 할) 값 x에 대하여 f(x)가 단조 증가 혹은 단조 감소단조 증가 함수 : x ≤ y 이면 f(x) ≤ f(y)인 경우일반적으로 조건(constraint)은 f(x)에 대하여 정의된다.Alt text최적화 문제를 결정 문제('예' 혹은 '아니오')로 바
https://www.acmicpc.net/problem/2512문제 요구사항 : 적절한 상한 금액을 찾는 것이 문제의 목표전체 국가 예산이 485이고, 4개의 지방 예산 요청이 120, 110, 140,150이라고 하자\-> 상한 금액이 127인 경우, 배정
https://www.acmicpc.net/problem/10816이진 탐색을 위해 데이터를 오름차순 정렬lowerBound()와 upperBound() 이해countByRange()를 사용정답!정답 예시와 다른 점은 for of를 사용한 것https:
~102일차~일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용추후에 공부할 DFS와의 차이점DFS보다 백트래킹이 더 많이 출제DFS는 일반적으로 완전 탐색 목적, 재귀 함수를 이용해 구현백트래킹도 재귀 함수를 이용하는 것이 일반적이지만, 단순히 완
https://www.acmicpc.net/problem/156491부터 N까지 자연수 중에서 중복 없이 M개를 고른 모든 수열을 계산모든 순열의 수를 고려하기 위해 재귀 함수(백트래킹)를 사용할 수 있다.하나의 순열을 트리(tree)에서 리프 노드까지의 경로
https://www.acmicpc.net/problem/156505개의 수 1, 2, 3, 4, 5에서 3개를 고르는 모든 조합을 고려해보자.깊이가 3인 경우를 고려한다.경우의 수 : 10개모든 조합의 수를 고려하기 위해 재귀 함수(백트래킹)을 사용할 수 있
https://www.acmicpc.net/problem/10971외판원 순회(traveling salesman problem. TSP) 문제이다.어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아와야 한다.\-> 어떤 노드에서 출발해도
https://www.acmicpc.net/problem/96631부터 N까지 자연수 중에서 중복 없이 M개를 고른 모든 수열을 계산모든 순열의 수를 고려하기 위해 재귀 함수(백트래킹)를 사용할 수 있다.하나의 순열을 트리(tree)에서 리프 노드까지의 경로로