알고리즘공부(Algorithm Study)78 백준 1004 java - 어린왕자(기하) 해당 문제는 이게 되나? 라고 했다가 테케 1번 맞추고 바로 제출하니 패스된 문제이다. 논리상 이거 밖에 없다!라고 해서 냈더니 너무 순순히 성공이 뜬... 신기하다. 1. 그림을 살펴보니 출발점을 포함한 행성계(원)의 개수 + 도착점 포함한 행성계(원)의 개수이다. 2. 더 잘 살펴보니 같은 행성계에 있을 땐 개수에 포함 안되고 다른 행성계에 있을 때 세면 된다. 3. 원 내부에 있는지 확인하는 식은 원의 방정식 x^2 + y^2 = r^2을 변형해서 (x - x1)^2 + (y - y1)^2 이게 가능한 이유는 문제의 전제조건 중에 원이 교차하지 않고 경계 위에 출발, 도착점이 없다고 정의했기 때문이다. package boj; import java.io.Buffered.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 18. 백준 2477 java - 참외밭(기하) 1. ㄱ의 모양은 상관이 없다. 임의의 위치에서 반시계방향으로 돌기 때문에 ㄱ방향보다 중요한 것은 움푹패인 곳이 어디냐이다. 2. 원형큐 개념으로 접근하면 움푹패인 곳을 파악할 수 있는 방법은 두 가지가 있다(한 가지는 스터디의 굇수분이 유도한 개념) 2-1 움푹패인곳의 길이는 이전 배열의 선분과 다음 배열의 선분의 수직이다 -> 1 3 1 / 1 4 1 / 2 3 2 / 2 4 2 / 3 1 3 / 3 2 3 / 4 1 4 / 4 2 4 2-2 가장 긴 가로, 세로 변은 붙어 있을 수 밖에 없다. 가장긴 선분 다음의 +2, +3번째 인덱스의 선분이 바로 움푹패인 곳이다. 3. 구현은 모듈러로 해도 되지만 그냥 하드코딩으로 짰다. package boj; import java.util.Scanner; pu.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 18. 백준 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. 백준 11066 java - 파일합치기(DP) 해당 문제의 경우 1주일 정도 붙잡고 있다가 결국 구선생님의 도움으로 풀게 된 문제이다. 아이디어 자체는 생각할 수 있었는데 그게 맞는 건지, 구현을 어떻게 해야하는 지 감이 오질 않았다. dp의 세계는 정말 무궁무진한 것 같다. 1. 두 개의 파일을 합칠 때 필요한 비용 = 두 파일 크기의 합 2. 최종파일 만드는 데 합치는 횟수 = 총 파일 -1 3. 서로 인접한 파일들끼리만 합칠 수 있음 4. 테스트케이스 관찰 결과 C1 + C2 / C1 + C2 + C3 / C1 + C2 + C3 + C4 = 3*C1 + 3*C2 + 2*C3 + C4 = 9 / 3 3 2 1 C1 + C2 / C3 + C4 / C1 + C2 + C3 + C4 = 2*(C1 + C2 + C3 + C4) = 8 = 2 2 2 2 C.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 8. 백준 13549 java - 숨바꼭질 3(BFS) 단순한 BFS라고 생각하면 틀리는 문제이다. 조건이 필요한 BFS 문제이다. 1. 0 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 6. 백준 2470 java - 두 용액(투 포인터) package boj; import java.io.*; import java.util.*; public class Boj_2470 { public static void main(String[] args) throws Exception { // 완탐 불가능 //-99, -2, -1, 4, 98 // O O // O O // O O // O O // O O // O O // O O // O O // O O // O O // // O O // 4, 98 // O, O = // 이미 0이 된 경우는 그냥 답 // 왼쪽 끝 커서, 오른쪽 끝 커서로 시작 // 오른쪽 커서 움직이다가 이전보다 0에서 멀어지면 왼쪽 커서 움직임 // 왼쪽커서 < 오른쪽커서 일때까지 돌림 BufferedReader br = new Bu.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 5. 백준 3273 java 두 수의 합(투 포인터) 전형적인 투포인터 문제 였다. 잔디심기용으로 제격! 1. 각 끝에서 시작 2. 합보다 클경우 오른쪽 포인터를 --, 합보다 작은 경우 왼쪽 포인터를 ++ 3. 합과 같을 경우 왼쪽 ++, 오른쪽 ++ 4. 왼쪽 포인터 < 오른쪽포인터 일 때까지 반복 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Boj_3273 { public static void main(String[] args) throws NumberFormatException, .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 5. 백준 1504 java - 특정한 최단 경로(최적화된 다익스트라) 해당 문제는 다익스트라를 이용한 문제로 다익스트라를 까먹고 다시 공부해서 풀게 된 문제이다. 1. 정점의 개수 N(2 ≤ N ≤ 800), 간선의 개수 E(0 ≤ E ≤ 200,000), 거리 c (1 ≤ c ≤ 1,000) 2. 다익스트라를 3번 돌리면 된다. (1에서 한 번, v1에서 한 번, v2에서 한 번) 3. 최적화된 다익스트라 기준 시간 복잡도 O(logN*(N+M)) = O((N+M)logN)(N은 정점 수 , M은 간선 수) -> 3번 돌리므로 3*O((N+M)logN) 4. distance의 INF값은 무지성 Integer.MAX_VALUE를 쓰기보다 정확한 계산을 근거로 넣어야 하므로 싸이클 다 돈다고 생각하면 800 x 1000 이므로 800,000보다 큰 값을 INF값으로 대체해서.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 4. 백준 2914 java - 저작권 SSAFY에서 관통프로젝트 후 너무 눈이 아프고 집중도 안돼서 잔디심기용으로 풀어본 브론즈5 문제이다. 1. 자바의 나눗셈은 버림을 기본으로 함 2. 창영이 앨범에 수록된 곡에 포함되어 있는 저작권이 있는 멜로디의 개수) / (앨범에 수록된 곡의 개수) = 저작권이 있는 멜로디의 평균값 = X / A = I => 결국 A*(I-1)< X A*(I-1) < X 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 3. 이전 1 2 3 4 5 6 7 다음 728x90