Will Be Fine

1. 콩 많이심기(SWExpet) 사용 알고리즘 : 구현 규칙을 생각하고 접근을 했는데 매칭이 쉽지 않았다. 그래서 https://sangdo913.tistory.com/115 여기서 접근방법을 보고 풀었다.코드는 간결하지만 상당히 좋은 문제라 생각된다. 접근 방법 + 형태를 코드로 옮길 수 있는지가 이문제의 핵심인 것 같다. 문제에 대한 접근&생각길이가 2인 콩은 심을 수 없음 -> 위아래 2칸 차이나는 콩은 심을 수 없음 -> 처리 조건!배열을 탐색하면서 가로와 세로에 해당하는 두칸씩 지워나감 -> 구현 ! 코드 12345678910111213141516171819202122232425262728293031323334353637import java.util.Scanner; public class So..

1. Ladder1(SWExpet) 사용 알고리즘 : DFS 기본 DFS 문제, 특이하게 테스트케이스가 개수가 아닌 번호로 들어온다. 당연히 개수가 들어올줄 알고 구현했다가 로직은 분명 맞는 것 같은데 자꾸 하나만 맞길래 분노가 차올랐다. 테스트케이스가 번호인 것을 알고나서 너무 허탈했다. input이 어떻게 들어오는지 꼼꼼히 확인하자는 교훈을 얻었다.......문제에 대한 접근&생각사다리타고 내려가기 -> 3가지방향 왼쪽,오른쪽, 아래-> DFS! 다른 방법 풀이전부다 하지않고 도착지점(2) 부터 시작하여 거꾸로 탐색한다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535..

1. 9465번 스티커(BJO) 사용 알고리즘 : DP 처음에 문제를 볼때는 어렵게 보였는데 이전에 푼 와인 문제와 비슷한 DP의 유형이었다.문제에서 최댓값을 원하면서 몇가지 제약조건을 주면 DP로 접근해 점화식을 세워보면 좋을 것 같다.문제에 대한 접근&생각인접한 스티커는 땔 수 없으면서 n번쨰 라인까지 스티커의 합의 최대값을 구해야함 -> DP!임의의 숫자를 선택 -> 이 숫자로 오는 경우들을 확인 -> 점화식 조건! 내 코드 123456789101112131415161718192021222324252627282930313233343536373839import java.util.Scanner; public class Main { public static void main(String[] args) {..

1. 11052번 카드 구매하기(BJO) 사용 알고리즘 : DP DP는 정말 알다가도 모르는 류에 속하는 것 같다. DP는 확실히 꾸준히 접해야 늘 것 같다는 생각이 많이 들었다.이문제는 답을 보면서도 이해가 안되는 부분이 있어서 직접 케이스를 대입하면서 이해했다. (아래의 주석부분....)문제에 대한 접근&생각카드의 개수가 정해져 있고 최댓값을 출력 -> DP! 내 코드 1234567891011121314151617181920212223242526272829303132333435363738import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in..

1. 2156번 포도주시식(BJO) 사용 알고리즘 : DP 전형적인 DP 문제, 마신 개수로 접근하다보니 통 답이 안나와서 https://limkydev.tistory.com/112 를 보고 이해를 했다.보면서 조금 이해하기 어려운 부분들을 정리하면 먼저 가장 큰 틀은 i번째 와인 앞에 서있을때 최대 와인의 합이 dp[i] 이다.i번째 와인 앞에 서있을때 발생하는 경우의 수가 와인을 안마시는 경우(앞에서 연잔으로 마신 상황)앞에 있는 와인만 마시는 경우 ( ex) 3 1 1 7 8 일때 이전의 최대치 플러스 앞의 와인을 마시는 상황 )바로옆 와인과 앞에 있는 와인을 연잔으로 마시는 경우 ( ex) 3 1 1 7 8 일때 3을 마시고 가운데 두개는 건너뛰는 상황)문제에 대한 접근&생각연속으로 최대 2개까지..

1. 1003번 피보나치 사용 알고리즘 : DP 포스팅 안해도 되는 문제라 생각했는데 가끔 피보나치 구현하는게 헷갈릴때가 있어서 메모해둘겸 올리면 좋겠다는 생각이 들었다.Lambda로 피보나치 구현하는 방법은 2019/04/01 - [공부/Lambda] - 5. JAVA8 in Action - Chapter 5 이글 맨 아래에 있다. 내 코드 12345678910111213141516171819202122232425262728293031323334353637import java.util.Scanner; public class Main { static int[][] dp; public static void main(String[] args){ Scanner sc = new Scanner(System.in)..

1. 10800번 컬러볼 사용 알고리즘 : 누적합 상당히 어려웠던 문제지만 추천할만한 문제이다. 합을 구하는데 N이 200,000 이므로 O(N^2) 풀수 없는 문제다.처음에 구현하기 어려워보이는 부분이 같은 색일때는 처리를 안해야 한다는게 어렵게 느껴졌다.같은 색은 처리 안하면서 또 같은 사이즈도 처리하지 않고 출력은 순서를 유지해야하는 생각이 필요한 문제였다.다른 사람 풀이 방법을 보면서 풀었는데 color 마다 누적합을 구하면 간단하게 풀 수 있었다.큰 방법은 size로 정렬하고 모든 size 누적값과 컬러별 누적값이 각각 필요하다. 이 후 가장 큰값부터 시작해 이전 것이 작다면 전체에서 color 누적값을 빼주면 된다. (color와 size값은 이중으로 빼지않도록 주의!)그리고 사이즈가 같을 경..

1. 1992번 쿼드트리(BJO) 사용 알고리즘 : 분할정복 분할정복을 잘 이해했는지 확인하기 위해 한문제 더 풀어보았다. 문제가 살짝 난해하다는 느낌이 있는데 해보면 별다를게없는 문제이다.마지막에 출력이 쿼드트리 형태로 나와야하기 때문에 이부분이 헷갈렸지만 분할로직의 진행과정을 이해했다면 금방 풀수 있는 부분이다.출력형태가 파고드는게 아닌 옆으로 진행되었다면 쉽지 않았을 것 같다.문제에 대한 접근&생각배열을 4등분해서 분할된 배열의 원소가 같아야함 -> 분할정복! 내 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import java.io.BufferedReader;i..

1. 1780번 종이의 개수(BJO) 사용 알고리즘 : 분할정복 갑자기 분할정복 문제를 풀어야겠다는 생각이 들어서 이걸 풀어보았다. 역시 전혀 기억이 나지않았다..(뭐든지 확실하게 이해해둬야겠다.)단순이 구현으로 풀수있는 문제이지만 간결하지 못할 것 같다는 생각이 들었고 다른 블로그를 참고하면서 풀어보았다.분할정복의 큰 틀은 체크하고 분할하고 체크하고 분할하고의 반복인데 분할이 0.0 기준으로 이루어진다는게 핵심포인트이다.즉 27 -> 9 -> 3 -> 1 0.0 기준으로 분할하고 오른쪽 0.1이 실행된다. 문제에 대한 접근&생각배열을 분할해서 분할된 배열의 값이 일치해야함 -> 분할정복! 내 코드 12345678910111213141516171819202122232425262728293031323334..

1. 2580번 스도쿠(BJO) 사용 알고리즘 : DFS, 백트래킹 처음에 이걸 완전탐색으로 풀수 있을까 라는 의문이 들었다. 왜냐면 9가지 숫자에 대한 경우의 수이므로 한줄에만 9! 발생했다.그래서 규칙을 활용 해야하는건가 해서 힌트를 봤는데 백트래킹 카테고리였고 가로,세로, 3*3에대한 부분을 체크가 필요했다. 이걸 보고 저 세가지조건을 만족하는 경우의 수는 1억번 연산 이하로 가능 할 것이라는 느낌이 왔다(+n은 9*9로 고정)보통 백트래킹할때 기존의 값을 다시 복구 시켜주는 방법을 사용하는데 그래서 0으로 놓고 진행했다.문제는 스도쿠에 0은 존재 할 수 없다. 그리고 로직이 0을 카운팅하기 때문에 시간초과가 발생해버렸다.해결방법은 탐색이 끝난 위치는 더이상 진행할 필요가 없게 하면된다. (1~9 ..

1. 1062번 가르침(BJO) 사용 알고리즘 : 완전탐색(조합) 놓친부분도 많았고 이걸 찾아서 고쳐도 메모리 초과가 계속 발생해 분노한 문제 핵심이 인사말을 무조건 알아야 된다는 걸 놓친 것 같다. 인사말을 빼는게 아닌 포함해서(무조건 배워야함) 구해야 한다.메모리초과 부분은 String을 int로 바꿨더니 해결되었다. String은 char 배열로 볼 수 있고 즉 문자당 2Byte의 메모리를 가진다.이문제는 최대 (27-5)!/10!에 연산을 가지므로 String을 사용했을시 메모리가 꽤 많이 발생하기 때문에 시간 초과가 발생한 것 같다. 문제에 대한 접근&생각알파벳을 배워서 최대 몇개 맞출 수 있나 -> 완전탐색 -> a b c와 c b a는 같다 -> 조합! 내 코드 1234567891011121..

1. 창용마을 무리의 개수(SWExpert) 사용 알고리즘 : UnionFind UnionFind를 공부했더니 보자마자 UnionFind 문제라는 느낌이 왔다. 이제 좀 감을 확실하게 잡은 것 같다. 문제에 대한 접근&생각 친한 사람이 연결 되어있고 무리를 지음, 이 무리의 개수 -> 각각의 루트노드를 가지면 되겠다 -> UnionFind 연결된 모든 사람에 대해 Union -> Set을 이용해 모든 사람의 노드를 저장 내 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 ..