공부(2018~2019) - 스킨변경전

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 ..

1. 섬연결하기(Programmers) 사용 알고리즘 : MST(prim), 우선순위 큐, 그리디 처음에 보자마자 MST문제라고 느낌이 왔었는데 그리디 카테고리로 분류 되어있어서 다른 방법이 있는 줄 알았다 .... MST 알고리즘을 살펴보면 그리디 인것을 알 수 있는데 순간마다 최적(cost가 작은) 경로를 선택하는 방법이라서 그렇다.MST는 https://www.crocus.co.kr/733 여기에 아주 자세~하게 잘 나와있다.. 문제에 대한 접근&생각최소 비용으로 모든 섬이 연결 가능하게 -> MST! 내 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575..

1. 1976번 여행가자(BJO) 사용 알고리즘 : Union-find 다음에 풀 MST 문제를 위해 오랜만에 Union-find를 다시 공부했다.이에 대한 내용은 https://www.crocus.co.kr/683 에 가장 잘 설명되어있다.(친절하게 그림까지! 감사합니다. )요약하면 서로 연결 되어있지 않은 그래프를 합치는 것 Union, 임의의 정점에 대한 루트를 찾는 것이 Find 이다.이문제를 보고 이거 Find로만 풀 수 있을 것 같은데? 라는 착각을 했었다... 당연히 틀렸지만 처음에 반례가 뭐지 하고 한참 고민했다.Find만 할 경우 뒤에 나오는 연결을 처리할 수가 없었다. ex) 1-2-9, 3-4-9 순차적으로 처리하면 3의 루트는 1이 아닌 3이 되버린다.. 내 코드 1234567891..

1. 가장 빠른 문자열 타이핑(SWExpert) 사용 알고리즘 : 포인터 쉬운 문제라고 생각해서 풀다가 꼼꼼한 처리를 못해서 조금 시간이 걸린 문제...문자열처리 문제는 대체로 쉽다고 생각해서 안풀어봤는데 문자열처리문제도 몇개 풀어봐야겠다는 생각이 들었다...문제에 대한 접근&생각문자열 처리 -> B열 갯수로 A열을 커팅해서 2중 for문 -> 비효율적!포인터를 이용 -> A열를 왼쪽부터 탐색하면서 idx를 늘이고 줄임 -> 테케 1개 맞음;;kaall al 일때 처음 a가 중복 될 경우 0부터 시작 -> 초기값 0을 카운트! 다른 방법 풀이A열을 B로 replace(B," ") 해서 이 길이를 구함;;; 생각지 못한 가장 간단한 방법이다..... 내 코드 12345678910111213141516171..

1. 1300번 K번째수(BJO) 사용 알고리즘 : 이분탐색 이분탐색으로 푸는 것을 알고 봤는데도 전혀 이해가 안됬던 문제, 정답 코드를 봤는데도 이해하기 쉽지 않았다.의문점이 들었던 부분은 1. n*n이아닌 k의 범위로 했을때도 정답이 출력됨, 2. 왜 조건(>=)을 만족하는 최솟값이 정답인지?1번은 중복없이 1 2 3~ 나열할때 K번째수를 구하면 딱 번호가 자기자신이 되므로 중복이 발생하면 더더욱 K번째 이하일 수 밖에 없다.2번은 n의 범위에 없는 수가 있어서 였다. 3*3에서 5는 나오지 않지만 이분탐색하면 5를 탐색한다. 이때 5는 6의 count를 가지게 되고 4도 6의 count를 가지게 된다. 이때 5는 범위에 속하지 않기 때문에 정답이 될 수 없다. 또한 3의 경우 5의 count를 가지..

1. 은기의 송아지 세기(SWExpert) 사용 알고리즘 : 구간합 간단한 구간합 문제, 풀면서 확실하게 구간합을 어떨때 쓰는지 알게 되었다.문제에 대한 접근&생각구간에 따라 송아지의 품종 합을 출력 -> 구간합! 내 코드 12345678910111213141516171819202122232425262728293031323334import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int test = sc.nextInt(); /*************************** * 송아지의 품종 수를 누적해서 누적합을 * 구하고 주어진..

1. 진수의 홀수약수(SWExpert) 사용 알고리즘 : 규칙,구간합 규칙을 잘 못 찾아서 조금 많이 해맨것 같다. 내가 생각한 규칙이 맞는지 범위를 넓게 가져가서 생각해야 겠다. 문제에 대한 접근&생각N이 100000000 -> 완전탐색 불가!, O(N^2) 불가!규칙이 존재할 것이라 판단 -> 누적되는 것 같아서 짝수를 2로 홀수는 3으로 나눈 값으로 구현 -> 약수가 4개 넘어갔을때 누적 되지않음모든 합을 구하되 NlgN으로 구해야함 -> i*j에서 j는 i의 배수를 이용 & i는 홀수이므로 연산↓답은 L~R에 합을 출력 -> 구간합! 내 코드 1234567891011121314151617181920212223242526272829303132333435import java.util.Arrays;im..

1. 의석이의 우뚝 선 산(SWExpert) 사용 알고리즘 : 규칙 규칙을 찾아야 하는 느낌은 있었는데 잘 떠오르지 않았다. 나는 이런 규칙 찾는 유형이 조금 약한 것 같다. 많이 풀어봐야겠다..... 문제에 대한 접근&생각왼쪽올라온산 * 아래로 내려간산 = 우뚝 선 산 경우의 수 다른 방법 풀이규칙은 같고 큐에 부등호를 넣어서 카운트 하는 방법 [참고] https://jokerkwu.tistory.com/92 내 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849import java.util.Scanner; public class Solution { static int UP =1; stat..

자기방으로 돌아가기(SWExpert) 사용 알고리즘 : 누적 문제는 간단했지만 상당히 어려웠던 문제... D4난이도에 걸맞지 않은 것 같다.(코드가 간단하기만 하면 D4 주는듯..) 힌트를 보고 풀었는데 어떻게 이런 사고가 가능한지 신기했다. 문제에 대한 접근&생각 방을 옮길때 겹치면 시간이 늘어남 -> 결과조건! 마주보는 방은 같은 복도를 사용함 -> 하나의 방으로 설정! 지나갈때마다 겹치는 구간이 존재함 -> 모든 이동경로를 카운트! 겹치는 구간 중 가장 많은 곳 발생 -> 가장 많이 겹치는 구간이 최솟값! 내 코드 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 im..