본문 바로가기

dev.

 (140)
[TIL] 99클럽 코테 스터디 23일차 TIL + 프로그래머스 소수찾기 문제 풀이 문제 탐색하기DFS 알고리즘을 활용하여 주어진 값으로 숫자를 만들며 진행하면 됩니다. 숫자를 만들고 그 숫자가 소수인지 판단하는 메소드를 작성하여 소수라면 Set에 저장하게 합니다. Set에 저장하는 이유는 중복되는 숫자가 저장되었을 경우를 대비하기 위함입니다. 숫자 종이는 숫자를 만들때 한번씩만 사용할 수 있기때문에 DFS 탐색을 반복하면서 방문한 인덱스는 visited 배열에 표시합니다. 그리고 백트래킹을 하기 위해서 재귀호출이 끝나면 visited배열의 값을 초기화 시키도록 합니다.  이렇게 탐색이 끝난 후 set의 size를 출력하면 만들 수 있는 소수의 수를 알아낼 수 있습니다. 문제 풀이import java.util.Arrays;import java.util.HashSet;impor..
[TIL] 99클럽 코테 스터디 22일차 TIL + 프로그래머스 피로도 문제 풀이문제 탐색하기알고리즘 파악하기예시를 통해서 문제를 풀 수 있는 알고리즘에 대해 알아보도록 하겠습니다. 순서대로 던전을 탐험하는 경우첫번째 던전 진행 최소 피로도 : 80, 소모 피로도 : 20 이므로 k = 60두번째 던전 진행 최소 피로도 : 50, 소모 피로도 : 40 이므로 k = 20세번재 던전 진행 최소 피로도 : 30 이므로 k 보다 크기에 세번째 던전을 탐험할 수 없습니다.첫번째 세번째 두번째 순으로 던전을 탐험하는 경우첫번째 던전 진행 최소 피로도 : 80, 소모 피로도 : 20 이므로 k = 60세번째 던전 진행 최소 피로도 : 30, 소모 피로도 : 10 이므로 k = 50세번재 던전 진행 최소 피로도 : 50, 소모 피로도 : 40 이므로 k = 10으로써 세번째 던전까지 탐..
[TIL] 99클럽 코테 스터디 21일차 TIL + 프로그래머스 카펫 문제 풀이 문제 탐색하기중앙에 노란색 카펫이 있고 겉으로 갈색 카펫이 1줄 테두리로 위치하고 있습니다. 중앙에 노란색 카펫을 기준으로 규칙을 생각해보면 노란색 카펫의 가로 길이 : x, 세로 길이 : y라 할 때 아래의 공식이 성립됩니다.x*y = yellow카펫 개수2(x+y) + 4 = brown카펫 개수 따라서 x, y로 각각 for문을 돌면서 해당 공식에 맞는 값을 배열에 추가해주면 되는 완전 탐색 문제입니다.for문의 범위는 x,y의 범위가 brown/2 로 나눈 값보다 작을 것이기 때문에 brown/2까지 탐색하는 것으로 하였습니다. 문제 풀이class Solution { public int[] solution(int brown, int yellow) { int..
[TIL] 99클럽 코테 스터디 20일차 TIL + 프로그래머스 모의고사 문제 풀이 문제 탐색하기이 문제는 답으로 주어진 배열을 1번 수포자가 찍는 규칙, 2번 수포자가 찍는 규칙, 3번 수포자가 찍는 규칙을 다 확인하면서 1,2,3번 수포자의 점수를 체크해야하는 완전 탐색 문제입니다. 각 수포자가 찍는 방식을 한 사이클이 끝날때까지를 배열로 선언하여  map에 key는 수포자의 번호, value는 점수를 저장합니다. 정답은 최고점을 가진 수포자를 출력하면 되는데 여기서 고려해야할 점은 같은 최고점을 가진 수포자를 오름차순으로 출력해야합니다. 따라서 map에 value로 저장된 점수 중 최고점을 구하고 최고점과 같은 점수를 가진 수포자를 따로 List에 저장합니다. 여기서 list를 배열로 변환하여 오름차순으로 정렬하게 되면 답을 구할 수 있습니다. 문제 풀이import ja..
[TIL] 99클럽 코테 스터디 19일차 TIL 우선 순위 큐 (Priority Queue) + 백준 1374 강의실 문제 풀이 문제 탐색하기문제를 읽어보면 강의실을 배정하는 규칙을 알 수 있습니다. 강의실에 배정된 강의가 끝나는 시간이 다음 강의가 시작하는 시작시간보다 클 경우 새 강의실에서 강의를 시작해야 한다는 것과 시작시간보다 작은 강의실이 있다면 다음 강의를 진행할 수 있다는 것입니다. 강의 시작시간과 끝나는 시간은 2차원 배열을 활용하여 오름차순 정렬 후 탐색에 사용합니다. 여기서 매 탐색마다 제일 빠르게 끝나는 강의실을 찾는 것이 중요합니다. 이 부분을 우선순위 큐를 활용하여 문제를 풀 수 있습니다. 우선 순위 큐(Priority Queue)란?큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 FIFO(First In First Out)의 구조 즉 먼저 들어온 데이터가 먼저 나가는 구조를 뜻합니다. Prio..
[TIL] 99클럽 코테 스터디 18일차 TIL + 백준 2212 센서 문제 풀이 문제 탐색하기오늘 문제는 문제를 여러번 읽어도 이해하기가 어려운 문제였습니다.첫번째 예제를 바탕으로 이해해보도록 하겠습니다. 센서의 개수 : 6개송신탑의 개수 : 2개센서의 위치 : [1, 3, 6, 6, 7, 9]  도로 위의 센서의 위치를 나타내면 위 그림과 같습니다. 여기서 각 센서에서 집중국으로 가는 거리의 합이 최소가 되도록 집중국을 위치시켜야합니다. 집중국으로 가는 거리의 합이 최소가 되도록 하려면 위 그림과 같습니다. 집중국의 개수 만큼 분리가 된다고 하면 2개의 그룹으로 분리된다는 것을 알 수 있습니다.   이 그림에서 보면 결국 집중국으로 인해 센서 간 가장 거리가 긴 3과 6의 사이를 기점으로 분리가 되었기때문에 가장 긴 길이인 3은 답을 구할때 사용하지 않습니다. 집중국의 ..
[TIL] 99클럽 코테 스터디 17일차 TIL + 백준 31926 밤양갱 문제 풀이 문제 탐색하기"daldidalgo" 라는 문자열을 N번 반복하고 마지막에는 "daldidan"을 입력하는 최소시간을 구하는 문제입니다.문자열을 완성시킬 수 있는 방법은 2가지가 있습니다.알파벳 소문자를 직접 입력원하는 부분의 연속된 문자열을 복사하여 끝부분에 붙이기 이 문제에 대한 예시로 N이 17이 주어졌을 때 밤양갱 가사를 완성하는 과정에 대해 설명하도록 하겠습니다. 첫 "daldidalgo"를 완성 시키는 방법은 아래와 같습니다. 총 8초가 걸리는 것을 알 수 있습니다.d a l d i : 알파벳 5개를 하나씩 입력입력된 문자열에서 "dal" 문자를 복사해서 뒤에 붙이기 -> daldidalg o : 알파벳 2개를 추가로 입력이제 부터는 앞의 문자열을 복사해서 가사를 완성할 수 있습니다...
[TIL] 99클럽 코테 스터디 16일차 TIL + 백준 2847 게임을 만든 동준이 문제 풀이 문제 탐색하기이 문제는 그리디 알고리즘을 활용하여 풀 수 있습니다. 우선 맨 마지막 레벨을 클리어 했을 때 얻는 점수보다 그 앞 레벨을 클리어했을 때 얻을 수 있는 점수는 낮아야합니다. 현재의 레벨과 그 앞의 레벨을 비교하면서 앞의 레벨에서 얻을 수 있는 점수가 현재 레벨에서 얻을 수 있는 점수보다 높을 때 얻을 수 있는 점수를 현재 레벨의 점수보다 1 낮게 감소시킵니다. 이를 반복하면서 총 감소시키는 점수를 카운트 하게되면 답을 구할 수 있습니다.  문제 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;public class Ma..

티스토리툴바