Algorithm

조합 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우이다. 순열에서 중복 제거한 것과 같다. [1, 2, 3] 배열에서. 2개의 수를 순서 없이 뽑으면 다음과 같다. 순열과 달리 조합은 r 을 유지할 필요 없이 숫자를 하나 뽑을 때마다 r을 하나씩 줄여준

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (회색) 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다 남아있는 수 가운데 3은 소수 이므로

문제점입력받는 원소 리스트로 dfs 트리를 구현해야하는데 어떻게 짜야할지 감이 안 잡힌다.‘원소의 합 / 2’ 가 두 부분집합이 가지는 합이다. 이것을 활용할 수 있을까풀이이진 트리 + DFS 로 풀었다(level = 0 , sum = 0) 으로 root를 두고 lt

풀이최대 무게를 넘지 않는 선에서 최대 값을 dfs 돌면서 계속 갱신해준다.

Node 클래스에 score, times 변수를 만들고 노드 마다 아래 조건을 비교하면서 최대 점수를 갱신하였다.m 시간을 넘기면 return한다.최대 점수와 비교했을 때 현재 점수가 더 크면 새로 갱신한다.배열의 수 보다 깊이가 깊어지면 바로 return

금액의 합을 담을 sum최소 횟수를 담을 minCount동전의 가격을 담을 coinArr배열을 만든다.sum != 0 은 아무 동전도 쓰지 않을 경우 m을 절대 초과하지 않아 추가했다.같은 동전의 합을 계속 더하면서 m을 초과하는지 확인한다.합이 m 보다 높거나 최소

조합의 성질에 따라 n == r 이거나 r == 0일 경우 1을 반환한다.문제에서 주어진 공식대로 dfs를 돌려서 최종 값을 출력한다.위 방법은 이미 한번 계산한 값을 다시 계산하므로 비효율적이다.한번 계산한 값은 chn에 담아서 필요하면 바로 불러다 쓸 수 있게 한다

수열 문제n개 중에 n개를 뽑는 수열을 사용하여 1,2,3,4 ~ 4,3,2,1 까지 돌려보면서 f(16)이 나올 때 까지 dfs 돌린다. 처음에 수열인지 모르고 도대체 어떻게 풀어야 하나 했는데 문득 순열 조합이 생각나면서 순열 구현 방법부터 공부하고 다시 풀어보니

dx, dy : 상,하,좌,우 움직일 수 있도록 좌표 배열 설정방문한 곳은 true로 변경1은 벽 0은 통로로, dfs로 돌면서 도착 지점에 다다르는 경우의 수를 카운트하면 된다.여기서 주의할 점은 지나온 곳은 visited 체크를 해줘야하는데 한 번 도착하면 뒤로 빠

dfs의 한 루트만 끝까지 파고 드는 것에 반해 Queue에 branch(열린 곳)를 모두 담고 순차적으로 모든 가지들을 한 단계씩 점진하여 최적의 경로를 구한다.dfs : 재귀bfs : queue

문제 풀이 전체 코드

문제 풀이 8 방향 dfs로 풀었다. 0,0 부터 n,n 까지 돌면서 1(섬)인 곳을 찾으면 카운팅하고 dfs돌면서 방문한 곳은 0으로 바꿔준다. 끝나면 다시 1인 곳을 찾으며 n,n 까지 돌린다. 전체 코드

조합 + dfs 문제피자집 m개를 제외하고 폐업하기 때문에 전체 피자집에서 m개를 선택해야한다.즉 피자집 배열에서 m개를 선택하는 조합을 사용한다.dfs 에서 m개를 뽑으면(level==m) 각 집마다 뽑힌 피자집과의 거리를 계산한다.최소 배달 거리의 합을 구하고 m개

키와 몸무게에서 키를 기준으로 정렬한다.키나 몸무게가 제일 크면 무조건 선발되므로 첫번째 선수는 선발된다.몸무게 최대 값 변수를 만들고 순서대로 몸무게 최대 값이 갱신될 때마다 선발 선수가 늘어난다.왜냐하면 뒤로 갈수록 키는 작아지는데 몸무게가 더 크므로 선발 대상이기

끝나는 시간 -> 시작하는 시간 순서로 오름차순 정렬한다. 왜냐하면 빨리 끝나는 대로 최대 횟수로 회의를 할 수 있기 때문이다. 끝->시작 으로 정렬되면 시작 시간을 비교하면서 이전 회의가 끝나는 시간과 비교하면서 회의를 할 수 있으면 (t.start >= endTi

1\. 입장, 퇴장할 때 기록을 모두 array에 추가한다.2\. 담을 때 입장은 's' 퇴장은 'e' 로 Times클래스로 묶어 추가한다.3\. 시간 순으로 정렬을 하는데 동시간대에 출입은 퇴장('e') -> 입장('s')순으로 정렬한다. \- 정각이 되면 먼저 나

유니온 파인드 문제union(합집합 연산) : 두 원소 a,b가 있으면 각 원소가 속한 집합을 하나로 합친다.find(찾기 연산) : 어떠한 원소 a가 주어지면 해당 원소가 속한 집합(최상위 노드)을 찾아서 반환즉 학생 관계를 a,b라고 했을 때 Union으로 학생들이

문제 풀이 잡담 > 그래프는 회로가 존재하고, 트리는 절대 회로가 존재하지 않는다. 간선의 수 = 정점의 수 - 1 전체 코드

이 문제는 계단을 한 칸씩 높게 올라갈 때 마다 규칙이 보여서 그걸 기반으로 해결했다.1칸은 1번 2칸은 2번 3칸은 3번 4칸은 5번 ... 7칸은 21번증가량을 보면 피보나치 수열이 보인다. 피보나치 n번째 + n-1번째의 합이 답이 나온다.조건에는 최대 계단이 3

문제 풀이 LIS 설명이 잘 되어 있다. DP 풀이 방식 : 시간 복잡도 O(N²) 인풋 배열의 크기 만큼 빈 배열(dy)을 만든다. 인풋 배열 i 를 순회하며 매 차례 이전 원소들 j를 검사하면서 현재 원소가 몇 번 째로 큰 원소인지 판단한다. > 잡담 전체코

완전탐색 dfs 로 풀리던 문제를 시간 복잡도를 고려하여 냅색으로 풀어본다.coin 배열 coinArr과 동전 개수를 저장할 dp 배열 dy를 만든다.j번째 동전의 개수 인 dyj는 j원을 거슬러 주기 위해 사용된 동전의 최소 개수 이다. coin 별로 거슬러 줄 동전

정렬하기 쉽게 Music 클래스를 만들어서 관리한다.장르 별 합을 가지고 정렬하기 때문에 HashMap 으로 각 장르별 재생된 노래 횟수의 합을 저장한다. hashMap.put(genresi, hashMap.getOrDefault(genresi, 0) + playsi)

파라미터 a가 소수인지 판단하는 함수이건 외우자!!

이분 탐색하나씩 줄여가면서 탐색하면 시간초과가 뜬다.N은 1이상 1,000,000의 범위를 가지기 때문에 범위를 절반씩 줄여가면서 타겟을 찾는 O(log n)의 시간 복잡도를 가질 필요가 있다.start와 end로 투 포인트(left, right)를 잡고 start가

1\. 처음에 0 ~ n만큼 배열을 초기화 한다.point를 하나 두고 주어진 스택 배열에서 값을 빼내면서 point를 움직여 값이 일치하면 pop 시킨다.point는 현재 쌓여있는 스택과 일치하므로 최상단 스택이 아닌 밑에 있는 값이 불려질 경우 연산이 불가능 하므로

완전 탐색 문제정답이 될 수 있는 123~987 의 경우의 수를 모두 검사하면서 답이 될 수 없는 경우를 줄여 나간다.답이 될 수 없는 경우는 어떻게 구하는가? 1\. 입력 받은 값(숫자,S,B)과 비교해서 Strike 와 Ball 의 값이 같다면 정답일 수도 있다.

문제에서 주어진 재귀함수 식에 DP 배열을 사용해서 한 번 계산한 값을 DP 배열 저장했다가 필요하면 반환해주면 끝0 \* 21 해도 되는데 for문 썼다이게 실버2 수준은 아닌거 같다

수열에서 규칙을 찾아 답을 구현하는 문제그림을 잘 보면 2 = 1+1 3 = 1+24 = 2+2...이런식으로 증가한다. 이 값은 문제에서 주어진 삼각형들의 값이다. 이를 통해(n>3) An = An-3 + An-2 로 정의할 수 있다. 재귀로 풀 것이기 때문에 시간복

N의 수를 통해 나타낼 수 있는 모든 값을 구하고 그 사이에 원하는 답(number)가 있을 경우 리턴해준다.풀다가 포기했다.문제는 이해하겠는데 4중 for문 구현하는게 아직도 잘 이해가 안된다.레벨 3은 아직 어려운 것 같다

문제가 너무 길어서 링크로 대체기존 토마토 문제에서 위 아래로 틀을 여러겹 쌓아 탐색의 범위를 넓힌 문제이다.좌표평면 탐색을 dx, dy, dz 로 총 6방향으로 탐색하면 토마토1 과 다를게 없다!2차평면에 비해서 탐색해야할게 많아서 입력값을 input에서 sys.st

문제 풀이 정렬 + 이분 탐색 + 딕셔너리 문제 전체코드

분할정복 + 재귀 문제정사각형 2차원 배열에서 모든 값이 0이나 1로 일치할 때 이 배열은 0, 1로 압축할 수 있다.즉 일치하지 않으면 일치하는 정사각형을 찾아서 계속 분할정복을 해주면 된다.

문제가 길어서 링크로 대체그래프 탐색, BFS로 푼 문제크게 두가지 과정이 있다. 1\. 녹인다. 2\. 덩어리 수를 확인한다.녹일 때는 순차적으로 녹이면 이전에 녹아버린 빙산 좌표 값이 0이 되버리면서 틀리게 되므로deepcopy()를 사용하여 배열을 깊은 복사