코테 61

99클럽 코테 스터디 28일차 TIL DP(가장 큰 증가하는 부분 수열)

https://www.acmicpc.net/problem/11055 어제와 비슷한 유형의 문제이다.문제에서 구해야 하는 값을 dp배열에 저장하는 값으로 설정하고, 그 규칙을 하나씩 찾아봤다.dp[0] 은 무조건 배열의 값일것이고, 그 뒤는 현재 값의 앞에 있는 값들을 탐색하면서 현재 값보다 작은 값이 있으면 그 값에 현재 값을 더한다.그리고 이런 값들을 Math.max를 통해 최댓값으로 갱신하며 구하면 끝!(자세한 건 아래 주석 참고)** 참 저 ans 때문에 98%에서 또 틀렸는데, ans를 자꾸 습관적으로 0으로 초기화해서 1 1을 넣었을 때 0이 나왔다(반목문 안돌아서)ans 초기화도 생각을 잘 해서 초기화하자.. 여기선 dp[0]으로.. package Study.Week04;/*1 : dp[0] ..

코테/백준 2024.11.24

99클럽 코테 스터디 27일차 TIL DP(가장 긴 감소하는 부분 수열)

https://www.acmicpc.net/problem/11722 1시간 동안 고민했는데 도오저히 아이디어가 안 떠올라서 힌트를 봤다 >.순서대로 탐색하면서 현재 값보다 이전 값의 크기를 비교하며 수열의 길이를 메모이제이션 하면 된다.현재 값보다 이전 값이 클 때 그 이전 값에 + 1을 수열의 크기로 저장하면서 갱신해주면 된다.자세히 분석해보면 아래와 같다.10 30 10 20 20 1010 : dp[0] = 110, 30 => 10 or 30 : dp[1] = 110, 30, 10 => 30, 10 : dp[2] = dp[1] + 110, 30, 10, 20 => 30, 20 : dp[3] = dp[1] + 110, 30, 10, 20, 20 => 30, 20 : dp[4] = dp[1] + 110,..

코테/백준 2024.11.23

99클럽 코테 스터디 26일차 TIL DP(돌게임)

https://www.acmicpc.net/problem/9655 DP문제 였는데 딱히 메모이제이션을 사용하진 않았다. 규칙을 도출하는 자체가 상향식 접근법이라고는 할 수 있겠지만..?무튼 코드에 주석으로 정리해놓고 풀긴했지만 한번 더 정리해보면!N을 1인 경우에서 부터 상근과 창영이 돌을 가져갈 수 있는 경우를 모두 정리해보았을 때결국은 홀수면 상근이 이기고, 짝수면 창영이 이기는 방법밖에 없다.따라서 N을 홀짝인 경우로 나누어 승자를 출력해주었다. 다만 여기서! 입력받는 값이 작아 Scanner를 사용했는데, 채점시간이 어어엄청 오래 걸리는 걸 확인했다.그래서 BufferedReader로 바꾸어서 한번 더 해봤는데, 확실히 좀 더 빨라졌고 이 기회에 Scanner와 BufferedReader에 대해 ..

코테/백준 2024.11.22

[BOJ] 2615 오목 (Java)

https://www.acmicpc.net/problem/2615 처음에 문제 읽고 설계했던 방식은 다음과 같다.1. 모든 바둑돌의 좌표를 구조체를 만들어 바둑돌 색상과 함께 큐에 저장한다.2. 하나씩 꺼내면서 dfs로 8방 탐색을 한다.3. 범위를 벗어나거나 방문했거나 다른 바둑돌 색상을 만나지 않고, 같은 바둑돌 색이면 cnt+1을 한다.4. 범위를 벗어나거나 방문했거나 다른 바둑돌 색상을 만나면 cnt를 확인해서 5이면 그 때의 시작 좌표를 출력한다.하지만 2-3%에서 틀렸고, 좌표를 찍어보며 수정하는 과정에서 엄청나게 많은 허점이 있음을 깨달았다. 1번 허점)그냥 큐에 저장하면 안됐다. 처음엔 위에서 아래로 배열을 탐색하기 때문에 조건을 만족한다고 생각했는데,반례를 보면서 만약 바둑돌이 왼쪽 아래..

코테/백준 2024.11.22

99클럽 코테 스터디 25일차 TIL 완전탐색(주사위 쌓기)

https://www.acmicpc.net/problem/2116 이 문제는 처음에 아이디어 설계하는 게 젤 힘들었다.이렇게 하는 게 맞나..? 하면서 풀긴 했는데 주사위 개수 범위가 작아서 완탐으로 가능했던 것 같다.아이디어를 정리해보면1. 1번 주사위의 모든 면을 바닥으로 두고 각각의 경우를 계산 시작한다.2. 0-5, 1-3, 2-4 면이 각각 마주보는 면이라는 것을 이용하여 현재 바닥의 윗면을 찾는다.3. 이렇게 찾은 바닥과 윗면을 제외한 모든 수를 열의 크기가 4인 map 배열에 넣어준다.4. 이때, 현재 윗면이 다음 주사위의 바닥이 될 것이므로, 다음 주사위의 바닥을 새롭게 찾아주어야 한다(nBottom)5. 이런식으로 계속 바닥면과 윗면을 찾아서 각각의 옆면이 될 수 있는 모든 수를 map에..

코테/백준 2024.11.21

99클럽 코테 스터디 24일차 TIL 완전탐색(전력망을 둘로 나누기)

https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  모든 전선들 중 하나를 차례대로 끊어보면서 각각의 송전탑의 차이를 구했다. 1. j번째 전선 끊고 전력망 연결for(int j=0; j 2. 어느 하나의 노드에 연결되어 있는 송전탑 개수 계산public static void dfs(int x){ visited[x] = true; for(int i=0; i 3. 두 전력망 송전탑의 개수 차의 최솟값 갱신 (cnt, (n-cnt) 차의 절댓값)// 두 전력망의 송전탑 차의 최솟값 갱신answer..

99클럽 코테 스터디 23일차 TIL 완전탐색(소수찾기)

https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 주어진 수를 가지고 만들 수 있는 모든 자릿수의 소수를 구하는 문제이다.모든 자릿수를 구하기위해 부분집합을 사용했고,이 자릿수로 만들 수 있는 모든 순서를 구하기위해 순열을 사용했다.그리고 각각의 수를 소수판별을 해서 소수는 set에 넣어주고, 마지막엔 set의 사이즈를 리턴했다. (중복 제거 위해) 그리고 제출했으나, 2/10/11/12번 테케가 틀렸다.이유는 소수 판별을 할 때 Math.sqrt(num) 범위까지의 수로만 판별해서 121과 ..

99클럽 코테 스터디 22일차 TIL 완전탐색(피로도)

https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 현재 피로도로 탐험할 수 있는 최대 던전 수를 구하는 문제.어떤 '순서'로 탐험하느냐에 따라 최대 던전 수가 달라진다. 범위가 크지 않은 것을 참고하여 순열로 구현했다.1. 탐험할 던전의 순서를 순열로 정한다.2. 현재 던전 순서에 따라 탐험 가능한 던전 수(cnt)를 구하고, 이때 마다 최댓값(answer)으로 갱신한다.3. 모든 경우를 구하고 정해진 최댓값을 반환한다. import java.util.*;class Solution { ..

99클럽 코테 스터디 21일차 TIL 완전탐색(카펫)

https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 그냥 수학처럼 풀었다,,1) x >= y2) x + y = (brown / 2) + 2;3) xy = brown + yellow이 3가지 조건을 만족하는 값을 배열에 저장하면 된다! class Solution { public int[] solution(int brown, int yellow) { int[] answer = new int[2]; for(int x=brown; x>=0; x--){ ..

99클럽 코테 스터디 20일차 TIL 완전탐색(모의고사)

https://school.programmers.co.kr/learn/courses/30/lessons/42840 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 우선 삼인방의 답이 반복되니 반복되는 구간을 1차원 배열에 지정했다.값으로 들어온 정답 배열과 비교해서 각 삼인방의 정답개수를 저장해둔다.정답개수를 탐색하며 최댓값(동점 포함)을 구한다.이 최댓값을 가진 사람의 번호를 저장해 리턴한다. 처음에 제출하고 런타임에러가 엄청 났는데, 알고보니...삼인방 정답을 확인할 때, 단순히 p1[i] 형식으로 비교하고 있었다..각 삼인방의 배열의 크기가 지정되어 있기에 들어오는 answers 배열의 크기에 따라..