.

타겟 넘버🔗 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr🚨모든 가능한 조합을 탐색해서 target에 도달하는 경우의 수 세는 문제 → 어떤 방식으로 모든 조합을 탐색할 수 있을까? ✅ 문제 풀이[문제 탐색]숫자 배열 각 원소에 대해 가능한 선택 : 2가지총 n개의 숫자가 있을 때, 모든 가능한 경우의 수 : 2^n가지모든 경로를 따라가며 누적합을 구하는 방식 : DFS 사용루트 노드(초기 합 0) 에서 시작각 레벨마다 숫자 하나씩 선택하며 + or - 붙여서 내려감마지막 레벨까지 내려..

폰켓몬🔗 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🚨맨 처음에 문제 푸는 방향성을 잘못 잡아서 먼 산을 돌아왔다 (..)조합(Combination)을 통해서 풀었는데 브루트포스(완전탐색) 방식으로 nums.length가 커질수록 시간복잡도가 O(N!)에 가까워진다. 가장 비효율적이고 타임아웃이 나므로 수학적 사고 + 자료구조(Set)를 사용해서 풀어줘야 한다.✅ 효율적으로 풀기[문제 탐색]선택할 수 있는 최대 수 : nums/2폰켓몬 종류의 수 : Set.size() (중..

완주하지 못한 선수🔗 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr💡 문제 설명더보기수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해 주세요. 제한사항마라톤 경기에 참여한 선수의 수는 1명 이상 100,..

K번째 수🔗 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42748 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr💡 문제 설명배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.2에서 나온 배열의 3번째 숫자는 5입니다.배열 array, [i, j, k..

문제https://www.acmicpc.net/problem/11866 문제 탐색하기요세푸스 : 1부터 시작하여 K-1개의 수를 건너뛰고 그 다음 K번째 수를 제거, 이 과정이 N명의 사람이 모두 제거될 때까지 반복순서대로 삽입/삭제가 일어나므로 Queue를 활용하여 구현K-1 만큼 건너뛰고 K번째 사람을 삭제하기 위해서 큐에 있는 데이터를 K-1만큼 꺼내서 뒤로 보내고 K번째 사람을 제거코드 설계하기사람의 수 N과 매번 제거될 사람의 위치 K를 입력받는다큐를 이용해서 사람들을 순서대로 입력K-1만큼 건너뛰고 K번째 사람을 제거맨 앞에 있는 사람을 제거하고 다시 큐의 맨 뒤에 추가이 과정으로 K-1번째까지의 사람을 뒤로 보내고 K번째 사람 제거K번째 사람 제거 될 때 StringBuilder 객체에 추가..

문제https://www.acmicpc.net/problem/2193문제 탐색하기N자리 이친수의 개수 구하기N = 1인 경우, 이친수 개수 1개 (1)N = 2인 경우, 이친수 개수 1개 (10)N = 3인 경우, 이친수 개수 2개 (100, 101)N = 4인 경우, 이친수 개수 3개 (1000, 1001, 1010)위의 결과를 보면, N자리는 N-1의 마지막 끝자리에 따라 결정난다.뒷자리가 0으로 끝나는 경우뒤에 0, 1 붙이기뒷자리가 1로 끝나는 경우뒤에 0 붙이기DP 설계하기dp[i][0] : 숫자 N을 만드는 경우의 수 중 끝자리가 0인 경우의 수dp[i][1] : 숫자 N을 만드는 경우의 수 중 끝자리가 1인 경우의 수초기값dp[1][0] = 0dp[1][1] = 1i 자리의 끝자리가 0으로 ..

문제https://www.acmicpc.net/problem/2303문제 탐색하기5장의 카드 중 3장을 더한 합의 일의 자리 수가 큰 사람의 번호 출력하기 일의 자리 수가 같은 경우, 번호가 큰 사람을 출력 가능한 시간복잡도입력 범위 ( 2 ≤ N ≤ 1000)가장 큰 일의 자리 수 구하기5장 중 3장을 고르는 조합 5*4*3 = 60각 사람에 대해 최대 60번의 연산 수행 시간 복잡도 O(N*60) N명의 사람 중 가장 큰 수를 가지고 있는 사람 탐색 시간 복잡도 O(N)전체 시간 복잡도 시간 복잡도 O(60*N ) + O(N)코드 설계하기각 사람 당 입력 받은 카드 값 저장카드 조합각 사람에게 주어진 5장의 카드 중 3장을 선택하는 조합 계산 일의 자리 계산그 조합의 합을 계산하고 그 합의 일의 자리..

문제https://www.acmicpc.net/problem/5567 문제 탐색하기n : 상근이 동기의 수m : 친구 관계 수a, b : 관계를 나타내는 값 상근이의 친구와 그 친구의 친구까지 초대하기 위해 depth 확인을 위해 DFS 이용그래프는 인접리스트로 구현 / 인접리스트로 구현 시 양방향 그래프로 구현상근이  depth = 0, 상근이 친구 depth = 1, 상근이 친구의 친구 depth = 2 가능한 시간복잡도입력 범위 ( 2 ≤ n ≤ 500, 1≤ m ≤ 10000)인접리스트 초기화 : 시간 복잡도 O(n) 그래프 생성 n : 상근이 동기의 수 (그래프의 노드 수)m : 친구 관계 개수 (그래프의 간선 수)관계를 입력받고 그래프를 구성할 때, m개의 간선을 입력받으므로 시간 복잡도 O(..

문제https://www.acmicpc.net/problem/2204문제 탐색하기n : 단어 개수 입력 : 알파벳 대소문자로 이루어진 단어 n개출력 : 대소문자 구분없이 사전순으로 나열 후 가장 첫 번쨰 단어 출력가능한 시간복잡도거의 모든 정렬 함수는 N개의 원소를 정렬할 때 O(NlogN)의 시간복잡도 가짐 코드 설계하기단어 개수 N를  입력받는다.단어를  Array로 저장한다.사전 순에 따라 정렬한다.정렬된 배열 중 가장 첫 번째 단어를 출력한다. 풀이 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Compara..

문제https://www.acmicpc.net/problem/2644 문제 탐색하기n : 전체 사람의 수start, end : 촌수를 계산해야하는 서로 다른 두 사람m : 부모 자식들 간 관계 개수x, y : 관계를 나타내는 수 (x는 y의 부모)촌수를 계산하는 것은 이어진 그래프에서 깊이 차이 구하기이므로 DFS 이용어떤 사람부터 탐색을 시작해도 깊이를 구할 수 있도록 양방향 간선으로 입력받음 DFS 탐색start 부터 탐색 시작탐색 중 end를 만나는지 확인만났을 경우 깊이 값 출력 가능한 시간복잡도입력 범위 ( 1 ≤ n ≤ 100)그래프 생성 n : 전체 사람의 수 (그래프의 노드 수)m : 부모-자식 간의 관계 개수 (그래프의 간선 수)부모-자식 관계를 입력받고, 그래프를 구성할 때, m개의 간..