누적합6

• 

  백준 1637 java - 날카로운 눈(이진탐색, 누적합, 정수론/feat.생애첫플레 1솔) 해당 문제는 결국 구선생님의 힘을 빌어서 풀게 되었으나 그래도 나만의 방식으로 풀어냈다. 이진탐색 + 누적합 + 정수론의 조합이기 때문에 좀 까다로웠다. 정수론이라고 치기에 애매하긴 하지만... 생애 첫 플레티넘 문제 1솔을 했다!! 1. 이진탐색(매개변수탐색)은 결국 순서대로 탐색하기 + 단절점 찾기가 핵심이다. 2. 일단 탐색할 값을 뭐로 할 지 정해야하는데 입력값중 압도적으로 큰 21XXXXX이 있어서 탐색값은 1 (C - A) / B + 1 의 누적합이 짝수인 경우에는 무조건 NOTHING일 수밖에 없다 왜냐하면 홀수개인게 하나고 나머지가 짝수이므로 누적합이 짝수인 경우에는 무조건 홀수가 없다는 뜻이기 때문이다. 5. 정답을 출력할 때는 홀수 개가 존재하는 특정 숫자에다가 그 숫자의 갯수를 출력해.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 29.

• 

  백준 11660 java - 구간 합 구하기 5(누적합) 이거 시간초과 나야 정상인 것 같은데 시간 초과가 애매하게 안났다. 1초 제한인데 최악 1,024 x 100,000이라서 102,400,000회=> 1초 될랑말랑이라 간당간당했나보다. 그냥 한 번 돌려봤는데 통과되서 놀랬다...! 사실 이러면 안되는 게 될까 말까가 아니라 이건 된다라는 마음으로 문제풀어야하는데... 요행을 바라는 건 실력이 아니다! ㅜ.ㅜ 1. 각 행 별로 누적합을 구해둔다. 2. 테스트 케이스 상 x좌표가 배열의 행좌표, y좌표가 열좌표이므로 헷갈리지 말자 -> 1트에 실패했음 3. 행별 구간합을 구해서 더 해준다. -> 소스코드 참조 package boj; import java.io.BufferedReader; import java.io.IOException; import java... 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 13.

• 

  백준 10986 java - 나머지 합(누적합, feat. 골드1달성) 해당 문제는 거의 하루 반나절을 고민했는데 결국 질문 검색의 힌트 + 굇수분들의 도움을 받아 푼 문제다. 누적합 + 수학적 사고력 + 데이터 타입의 조합으로 골드3인데 골드3보다 높아보인다... 1. 일단 구간합이 필요하므로 누적합 필요함. 2. 단순히 누적합끼리 2중 for문을 돌리면 1,000,000 * 1,000,000 = 1초 초과됨 -> 다른 방법 필요 3. 나머지들의 누적합을 활용해보면 나머지가 같은 구간끼리 뺀다면 그게 나머지 0이 됨 4. 나머지 0의 경우 그 자체로도 답이 되고 서로 빼서 구간합 만든 것도 답이 되므로 카운팅할 때 신경 써야함 5. n*(n-1)/2 (nC2)을 구할 때 n이 1,000,000일 경우 int범위를 벗어나므로 long범위로 선언하여야 하며 누적합 배열을 in.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 13.

• 

  백준 16139 java - 인간-컴퓨터 상호작용(누적합) 해당 문제는 누적합을 이용해 푼 문제이다. 0번째 인덱스부터 시작한다는 것 때문에 1트에 틀렸지만 바로 고쳐서 패스하였다. 1. 문자열 길이 200,000이하, 문제 수 200,000이하, 인덱스는 0부터 시작 2. 알파벳 갯수는 26개이므로 문자열을 한 인덱스씩 읽어내려가며 누적합을 만들면 최대 26 * 200,000 = 5,200,000회 순회, 문제 200,000개 읽는데 200,000번 순회 = 5,400,000번 for문 순회하면 답이 나온다. 3. 알파벳 갯수가 26개인지 알 필요도 없이 char형 z - char형 'a' +1 하면 알파벳 갯수만큼 배열 선언 가능 4. 그냥 문자열에서 인덱스마다 문자 읽을 때 누적합 배열 채워준 뒤 문제 읽고 누적합 차를 통해 특정 구간의 합을 구하면 되는 .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 11.

• 

  백준 2559 java - 수열(누적합) 누적합을 활용한 문제이다. 시그마(sum) 시그마(1~N) - 시그마(1-M) = 시그마(M+1 ~ N)이라는 식만 알고 있으면 되는 문제이다. 1. N은 2이상 100,000이하, K는 1이상 N사이의 정수 -> int 자료형까지만 필요 2. 누적합을 이용해서 풀어봐야겠다 3. 입력 받는 즉시 바로 누적합으로 빼서도 구할 수 있겠군 4. sum 배열 다 구한 후에 또 for문 돌리면 시간 차이가 많이 나나? 5. 최솟값은 -20,000,000정도까지 나올 수 있겠군? import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 10.

• 

  백준 1912 - 연속합 JAVA 해당 문제는 손으로 끄적여가면서 풀다가 탁 깨달은 시점에서 술술 풀어나간 문제이다. 생각보다 매우 간단한 로직이지만 그동안 풀었던 문제들 + 단계별로 풀기 끝에 있다는 것을 감안해서 스스로 어려운 문제일 것이다라고 되뇌다가 시간이 오래 걸린 문제이다. -> "생각보다 쉬웠다"라는 뜻 1. n개의 정수, 1 1 + 2 가 최대고 -1,000일 때는 굳이 안 더해주는 게 나을지도? 3. 그렇다면 합한 수가 0보다 낮아지지 않는 시점까지는 연속합(누적합)을 해주다가 0보다 낮은 경우에는 그냥 연속합(누적합)에 넣는 것을 포기하고 다시 0보다 큰 수가 나오는 시점부터 합해주면 좋을 듯 하다. 4. 동시에 max값은 유지하면서 n번 째까지 다 돌았을 때의 max값이 답일 것이다. 일반적으로 입력을 받을 때 로직을.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 3.