IT 개발 돼지의 일상

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yC3pqCegDFAUx "와 어려웠다.인수분해" 처음엔 0~9 까지 숫자를 눌러 X를 구하려고 했다. 굉장히 구현이 잘 되지 않았다. 1 = 11*1 = 11*1*1 = 1 이런 경우 어떻게 처리할까.. 그래서. 약간의 기초적인 수학적인 지식이 필요했다. 어떤 수들을 곱해서 X가 만들어 졌고, X를 계속 인수분해 하다보면 계산기를 눌러 가능한 a * b *.. *... * 의 형태로 나올 것이다.. 따라서 해당 문제에서는 주어진 X값을 인수분해 하여 해당 a * b 의 형태로 바꾼 후에, a와 b를 계산기로 칠 수 있는지 확인하고, 그렇지 않다면 다시 ..

출저 : https://www.acmicpc.net/problem/2026 "DFS 문제를 잘 읽어야함..." 문제를 잘 안 읽어서 계속 틀렸음. 문제를 잘 읽어 보면 선택된 K명의 모든 애들이 다 친구여야 함. 최초에 1-3-2-4 의 관계가 되면 나는 1,2,3,4 모두 답으로 출력했음. 이거 빼고는 그냥 DFS 문제. 따라서 아래 68~ 73 라인을 추가했음. 팁으로 경로를 찍을 때는 list 보다는 아래와 같이 result 배열 하나만을 생성해 이를 이용해 경로를 찍는 것이 더 좋다고 생각됨. 또 하나, 전부 친구인지 아닌지 판별하는 부분에서 boolean 변수를 사용할 수도 있지만 이미 생성된 j를 가지고 끝까지 돌았는지 j == index 인지 판별하면 변수 생성을 하나 줄일수 있으미.. 12..

출저 : https://www.acmicpc.net/problem/2579 "DP 쓸 때, dp값과 map에 값을 활용해보자.." 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int N; static int[] dp; static int[] map; public static void main(String[] args) throws IOException{ BufferedReader br = n..

출저 : https://www.acmicpc.net/problem/1149 "DP" 어려웠다. 기초적인 dp문제라고 했는데 왜 이리 어려웠지...ㅎㅎ dp[x] = dp[x-1] + min(x) ; 까지는 생각을 하고, 해답을 봤다. 그리고 최초 dp[0] 가 R,G,B 일 때를 모두 체크하기위해 dp[x][3] 배열을 만들어 해당 dp 값을 이용한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringToken..

출저 : https://www.acmicpc.net/problem/1932 "DP, bottom-up / DP라고 무조건 재귀 생각하지말자." 알고리즘은 삼각형의 맨 밑부분부터 시작해서 dp 갱신을 시작한다. 처음에 재귀로 구현했는데 시간초과가 났다. dp 값을 비교해서 기존 dp 값보다 작으면 탐색하지 못하게 하였는데??? 라고 생각했다. dp 값이 나중에 큰 값으로 갱신된다면, 이전 까지 탐색 경로들은 그냥 지나칠 거임.. 따라서 해당 지점에 가능한 가장 큰 값이 맨 나중에 갱신되는 데이터가 주어졌다면 아마 dp 값 비교를 통한 가지치기는 적용 안될듯. 1234567891011121314151617181920212223242526272829303132333435363738394041424344impo..

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn "구현... 다시보자! 꾸에에에엑" 다시보자... 왜 이런 생각을 못했을까. 처음에 그냥 브루트 포스로 전체 경우의 수를 재귀로 다 돌려보았다. 시간 초과. 풀이 참고해서 풀었따. 알고리즘은 아래와 같다. 1. 각 배점을 받을 때마다 최대값을 갱신한다.2. 갱신된 최대값 ~ 0 까지 탐색하며, 만약 이전에 이미 맞았던 점수가 있다면 이 점수에 내가 방금 입력받은 점수를 더해준 값도 체크한다.3. true 로 체크된 값들의 개수를 센다. 12345678910111213141516171819202122232425262728293031..

출저 : https://www.acmicpc.net/problem/3019 "아구가 맞니?" 해당 문제를 처음에는 모든 조각의 상대 위치를 3?4? 차원 배열로 만들어서 모든 경우에 수에 따라 검색하려고 했다. 하지만 조각의 위치를 정의하는데 너무 복잡하고 더러워서 다른 방법을 찾아봄... 아구가 맞는지를 탐색하는 방법이다. 아래와 같이 돌출된 부분에 값을 준다. 전체 높이가 같은지 확인한다.아래 왼쪽 그림의 경우 높이는 2,1 이고 ㅓ 의 경우 돌출된 칸이 1칸 이므로 0,1 이렇게 한 후 높이와 이 값을 더한다. 왼쪽) 2 + 0 = 1+ 1오른쪽 ) 2+ 0 = 1 + 1 = 2 + 0 123456789101112131415161718192021222324252627282930313233343536..

출저 : https://www.acmicpc.net/problem/1783 "그리디 알고리즘, 내 머리속으로 계산." 여러 조건들이 있었다. 오른쪽으로만 이동하며, 이동 횟수가 4가 넘어가는 경우 가능한 4가지의 방법 모두 적어도 한번씩은 사용해야 한다. 이러한 부분들을 조건문으로 분기시킨다... 잘 생각해보자. n이 1,2,3,... 일때를 생각해보고, m이 7보다 작을때, 크거나 같을 때를 생각해보자. 12345678910111213141516171819202122232425import java.util.Scanner; public class Main { static int n,m; static Scanner sc = new Scanner(System.in); public static void mai..

출저 : https://www.acmicpc.net/problem/1937 "DP" DP를 이용한 문제이다. top down 방식을 사용한다. 재귀를 할 때, 리턴 값이 있는 경우 처리를 잘해 주어야 겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Main { s..

출저 : https://www.acmicpc.net/problem/1890 "DP 와 2^63" 전형적인 DP 문제로서 Top-down 방식의 메모이제이션을 사용한다. Start 부터 시작해서 End 까지 탐색한다. 검색 중에 End 에 도착했다면 한 가지 방법이 있는 것이므로 1을 리턴하고 이 값은 함수를 호출한 dp[x] 에 누적된다. 아래 예를 보면 4,5,6 번 노드가 이와 같다. 이런식으로 "누적"을 하게 되면 해당 노드에서 End로 갈 수 있는 방법의 수가 dp[x]에 저장된다. DFS 나 BFS 로 풀면 시간초과가 날 것이 왜 dp를 쓰면 시간이 단축 되나? 라는 질문에 답은 7번 노드를 보면 된다. 7번 노드까지 탐색한 후에 6번 노드의 dp값을 체크하였더니 1이 저장되어 있더라. 6번 이..