Algorithm

📝문제https://www.acmicpc.net/problem/2018수들의 합 5 2018티어: Silver 5 💡풀이문제 유형투포인터 걸린 시간거의 40분 시간 복잡도O(N) 풀이 방법 도출풀이법이 생각 안 나서 다른 사람의 풀이를 참고하였다..ㅠ완전 탐색으로 풀면 시간 초과 우려가 있어 투 포인터 알고리즘을 사용한다.start = 1, end = 1, sum = 1, count = 1로 선언 후sum sum > N 이면 start 위치를 오른쪽으로 옮겨 더 작은 수가 되도록 한다. sum -= startsum == N 이면 count 개수를 증가시키고 end 위치를 오른쪽으로 옮겨 더 큰 수가 되도록 한다. sum += end이 과정을 start import java.util.*;import j..

📝문제https://www.acmicpc.net/problem/7569토마토 7569티어 : Gold 5 💡풀이문제 유형너비우선 탐색 걸린시간거의 60분 시간 복잡도O(H×N×M) 풀이 방법 도출처음에 dfs로 접근하다가 최솟값 구하는 문제라 bfs로 방향을 틀었다. dfs로 30분 날린듯tomato = new int[H][N][M]; 토마토가 들어있는 3차원 배열을 선언하고 입력값을 차례대로 넣어주었다.이때 모든 토마토가 익어있는 상황을 확인하기 위해 boolean completed = true; 변수를 활용하였다. 0을 반견하면 false로 바꿔주고 completed = true면 조기 종료 해주었다.이후 익은 토마토를 발견하면 토마토의 위치와 day를 큐에 넣어준다.bfs 함수를 선언하여 익은 ..

📝문제https://www.acmicpc.net/problem/2875 💡풀이며칠 전에 풀려고 시도했다가 아이디어가 안 떠올라 포기했던 문제를 다시 도전해보았다.내 아이디어는 다음과 같다. 1)대회에 나가는 여학생을 변수 a로,대회에 나가는 남학생을 변수 b로 잡는다. 2)전체 여학생 인원이 N이고전체 남학생 인원이 M이므로(N-a)+(M-b) 는 인턴을 나가는 학생 수보다 같거나 커야한다. 3) 만약 N-a가 2보다 크거나 같고 M-b가 1보다 크거나 같으면 대회에 나가는 학생의 수를 추가해줄 수 있다.a = a + 2b = b + 1 4) 3번의 조건식에 맞지않는다면 대회에 나가려는 학생에 비해 나갈 수 있는 학생이 적기 때문에 팀을 꾸릴 수 없으므로 반복문을 빠져나온다. 전체풀이import ja..

📝문제 💡풀이예제의 입력을 그림으로 표현하면 아래와 같다.각 정점에 대해 가장 긴 거리 경로를 구하면1-3-4-5 :112-4-3-1 :93-4-5 :94-5 :6 5-4-3-1 :11 위 결과의 공통 점은 1또는 5가 경로에 포함 된다는 것이다.트리의 지름은 1에서 5의 거리인데 어떤 정점에서 구해도 1또는 5를 포함해야 가장 긴 경로가 나온다. 이러한 결과로 이 문제의 아이디어는 다음과 같이 구할 수 있다.1. 임의의 정점에서 가장 긴 거리의 정점을 찾는다. 2. 1에서 찾은 정점을 기준으로 한번 더 가장 긴 거리의 정점을 찾는다. dfs를 두번 호출하여 정답을 구할 수 있다. 전체풀이import java.util.*;import java.io.*;class Main{ static boole..

https://www.acmicpc.net/problem/2146이 문제는 차근차근 풀어가면 엄청 어렵진않다 중간에 실수만 안 하면 ..?조건이 많아 다소 복잡해보일뿐 알고리즘 자체는 어렵지않다,, 1) 섬을 구분해준다. 섬 구분은 dfs로 구현하였다.입력값이 아래와 같을 때 서로 다른 섬을 숫자로 구분해주었다. 2) 해안선의 위치를 큐에 넣어준다.이 문제는 해안선으로 시작해 다른 육지까지의 최소 거리를 구하는 것이므로해안선을 찾아줘야한다. (상하좌우에 0이 있는지 확인)if(!isCoastLine && island[nx][ny] == 0){ //해안선 위치를 큐에 넣음 isCoastLine = true; coastline.add(new int[] {n,m});} 3) 찾은 해안선들을 기준으로..

📝문제 💡풀이N의 크기가 10¹² 까지 허용된다는 점이 이 문제의 킥이다.처음엔 반복문으로 풀어 메모리 초과가 났었다. 재귀문을 사용하여 풀면 기존 O(N)에서 O(logN)으로 시간복잡도를 향상시킬 수 있다. solve(7)solve(7/2=3)+solve(7/3=2)solve(3/2=1)+solve(3/3=1)+solve(2/2=1)+solve(2/3=0)solve(1/2=0)+solve(1/3=0)+solve(1/2=0)+solve(1/3=0)+solve(1/2=0)+solve(1/3=0)+solve(0) 위와 같이 한 번의 호출에서 최대 두 번의 호출이 발생하고 solve(0)을 만나면 1을 반환해주는 방식을 사용한다. 전체 풀이import java.util.*;import java.io.*;..

📝문제 💡풀이dp[k][n] : 0부터 n까지의 수 중 k개의 수를 합해 n을 만들 수 있는 개수dp[1][0] = 1  (0)dp[2][0] = 1 (0+0)dp[3][0] = 1 (0+0+0)dp[4][0] = 1 (0+0+0+0) dp[1][1] = 1 (1)dp[2][1] = 2 (0+1), (1+0)dp[3][1] = 3 (0+1+0), (1+0+0), (0+0+1)dp[4][1] = 4 (0+1+0+0), (1+0+0+0), (0+0+1+0), (0+0+0+1) dp[1][2] = 1 (2)dp[2][2] = 3 (0+2), (2+0), (1+1)dp[3][2] = 6 (0+2+0), (2+0+0), (0+0+2), (0+1+1), (1+1+0), (1+0+1)dp[4][2] = 10 (0..

📝문제 💡풀이첫 번째로 주어지는 문장을 str1, 두 번째로 주어지는 문장을 str2라고 하자. dp[i][j] 는 str1 문장의 0번째 문자부터 i번째 문자까지의 원소와 str2 문장의 0번째 문자부터 j번째 문자까지의 원소들 가운데 만들 수 있는 최대 공통 수열을  의미한다. str1: ACAYKPstr2: CAPCAK dp[0][0] => {A}, {C} 로 만들 수 있는 최대 공통 수열 => 없음dp[0][1] => {A}, {C,A} 로 만들 수 있는 최대 공통 수열 => {A}dp[0][2] => {A}, {C,A,P} 로 만들 수 있는 최대 공통 수열 => {A}dp[0][3] => {A}, {C,A,P,C} 로 만들 수 있는 최대 공통 수열 => {A}dp[0][4] => {A}, {..

이전 풀이https://girokeulhaja.tistory.com/89 [Algorithm] 99클럽 코테 스터디 6일차 TIL | 백준_DFS와 BFS(1260번)https://www.acmicpc.net/problem/1260dfs와 bfs의 개념만 알고 있다면 풀 수 있는 문제나는 2차원 배열에 입력값을 그대로 담아간선 리스트를 사용하여 그래프를 표현하였다. 문제에 정점이 여러 개인 경우girokeulhaja.tistory.com 한 달 전에 풀어본 문제를 다시 풀어보았다.풀고 나니 같은 사람이 푼 문제가 맞나 싶을 정도로 코드가 훨씬 깔끔해졌다는 생각이 든다!메모리와 시간 모두 이전보다 절약해서 풀기도 하여 뿌듯함에 기록해본다.🫠 ArrayList를 정렬하는 방법이 Collections.sor..

📝문제 💡풀이1) dp 배열을 만들고 1로 초기화한다.2) 현재 수arr[i]가 이전 수arr[j]보다 크다면 증가하는 수열이므로 dp[i] = dp[j]+1이 될 수 있다.여기서 10 20 10 30 이 있을 때 i=3라면dp[3] = dp[1] + 1도 답이 될 수 있고 dp[3] = dp[2] + 1도 답이 될 수 있으므로두 경우의 수 중 더 큰 값을 구해 dp[3]에 넣어줘야한다.그러므로 해당 식이 필요하다.dp[i] = Math.max(dp[i],dp[j]+1);3) 이후 dp 배열에서 가장 큰 값을 찾으면 정답이다. 전체풀이import java.util.*;import java.io.*;class Main{ public static void main(String args[]) thro..