알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving)72 백준 1637 java - 날카로운 눈(이진탐색, 누적합, 정수론/feat.생애첫플레 1솔) 해당 문제는 결국 구선생님의 힘을 빌어서 풀게 되었으나 그래도 나만의 방식으로 풀어냈다. 이진탐색 + 누적합 + 정수론의 조합이기 때문에 좀 까다로웠다. 정수론이라고 치기에 애매하긴 하지만... 생애 첫 플레티넘 문제 1솔을 했다!! 1. 이진탐색(매개변수탐색)은 결국 순서대로 탐색하기 + 단절점 찾기가 핵심이다. 2. 일단 탐색할 값을 뭐로 할 지 정해야하는데 입력값중 압도적으로 큰 21XXXXX이 있어서 탐색값은 1 (C - A) / B + 1 의 누적합이 짝수인 경우에는 무조건 NOTHING일 수밖에 없다 왜냐하면 홀수개인게 하나고 나머지가 짝수이므로 누적합이 짝수인 경우에는 무조건 홀수가 없다는 뜻이기 때문이다. 5. 정답을 출력할 때는 홀수 개가 존재하는 특정 숫자에다가 그 숫자의 갯수를 출력해.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 29. 백준 12015 java - 가장 긴 증가하는 부분 수열 2(이진 탐색/2가지 풀이) 어제 오늘은 이진탐색 부수기를 하고 있다. 드디어 백준 단계별로 풀기에서 이진탐색을 밀었다! 이진 탐색에 대해서 심리적 거부감이 있던 터라 극복하면 보이지 않는 벽을 부순다는 일념으로 열심히 도전했다. 이진 탐색은 결국 매개변수 탐색과 연결된다는 점이 핵심인 것 같다. 풀이는 List 활용 방식과 Array(배열) 탐색 방식이며 Array방식이 시간이 더 짧다. ( 756ms[List] > 592ms[Array]) 1. 이진탐색(매개변수 탐색)을 사용하기 위해서는 다음 두 가지 조건이 필요하다. 1.1 순차대로 탐색이 가능해야한다. 1.2 특정 단절점이 있어야 한다. 2. 거진 반나절을 꼬박 생각해도 특정 위 두 가지 조건에 맞추는 방법을 생각지 못해서 구글링을 했더니 list 풀이 방식이 나왔다. 3... 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 29. 백준 24444 & 24445 알고리즘 수업 - 너비 우선 탐색1 & 너비우선 탐색 2 해당 문제를 잘못 이해한 부분이 있었다. 인접 정점을 오름차순, 내림차순으로 방문한다고 해서 특정 차수 기준 오름차순 방문인 줄 알고 PriorityQueue를 썼다가 여러번 시도 끝에 그냥 queue로 돌렸더니 pass가 됐다. 1. 시간 제한 : 1초 => 약 1억 번 연산 가능 2. 메모리 제한 : 512MB => 정수(4바이트) 기준 256 x 1024 x 512 개 생성 가능 = 2^8 x 2^10 x 2^9 = 2^27 3. N개 정점, M개 간선 & 무향 그래프 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤N) -> 2차원 배열로는 100,000 x 100,000이므로 인접리스트, 리스트로 풀어야 함 4. 1 ~.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 28. 백준 24479 & 24480 알고리즘 수업 - 깊이 우선 탐색 1&2(DFS) 이번에는 두 문제를 갖고와봤다. 백준 단계별로 풀어보기 1, 2번 문젠데 그냥 dfs를 오름차순, 내림차순으로 하느냐의 차이여서 java에서 오름, 내림차순 정렬하는 법만 알면 되니 한 큐에 풀어제꼈다 1. DFS로 풀어야한다. 2. 정점의 수가 100,000개까지이므로 100,000 x 100,000이므로 2차원 배열로는 안된다. 3. 리스트나 우선순위큐를 이용하여 풀어야 한다. 4. 리스트를 사용할 경우 정렬 함수를 써야하며 우선순위큐를 사용할 경우 오름차순인지 내림차순인지 정의해줘야 한다. -> 본인은 리스트 + 정렬 함수를 썼다. 정렬과 관련해서는 이전에 작성한 글을 참고하면 좋을 듯 하다. 2022.02.20 - [프로그래밍공부(ProgrammingStudy)/자바(JAVA)] - (JAVA/자.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 24. 백준 1520 java - 내리막길(DP, 동적계획법) 해당 문제는 자력으로 푼 건 아니고 다른 분의 풀이를 참고하여 푼 것이다. 왜 Queue를 사용한 bfs는 안되는 걸까 생각하다가 힙을 쓰면 된다고 생각하니 풀렸다. 정석으로는 탑다운 방식의 DP였다. 1. 내리막길의 개념은 현재 방문한 곳의 높이(값) 보다 다음에 방문할 곳의 값이 더 낮은 경우이다. 2. BFS+DP또는 DFS+DP로 풀면 된다. 3. 두 가지 접근법이 있는데 0,0(시작점-바텀업) 부터 아래로 쌓거나, M-1, N-1(도착점-탑다운)부터 쌓으면 된다. 4. 해당 문제는 dp다 보니까 탑다운, 바텀업 전부 되지만 나는 바텀업(0,0 부터 쌓기)방식으로 풀었다. 5. PriorityQueue를 쓰지 않으면 주변 내리막길이란 내리막길은 다 가기 때문에내리막길 다음의 그다음 제일 큰 내리막.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 23. 백준 11049 java - 행렬 곱셈 순서(DP/동적계획법) 해당 문제는 거진 3일? 4일? 생각했다가 파일합치기를 응용하면 된다는 것은 알지만 점화식이 도출안돼서 답답해하다가 범죄도시 2 영화 보고 카페와서 깨닫고 풀 수 있게 된 문제이다. 파일합치기에서 응용이므로 참고하면 좋을 것 같다. 2022.05.08 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 11066 java - 파일합치기(DP) 백준 11066 java - 파일합치기(DP) 해당 문제의 경우 1주일 정도 붙잡고 있다가 결국 구선생님의 도움으로 풀게 된 문제이다. 아이디어 자체는 생각할 수 있었는데 그게 맞는 건지, 구현을 어떻게 해야하는 지 감이 오질 않았다. dp chaaany.tistory.com 1. 두 개의 파일을 합칠 때 필요한 비용 = .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 22. 백준 1358 java - 하키(기하/백준단계별로풀기 기하 clear) 2022.05.18 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 1004 java - 어린왕자(기하) 백준 1004 java - 어린왕자(기하) 해당 문제는 이게 되나? 라고 했다가 테케 1번 맞추고 바로 제출하니 패스된 문제이다. 논리상 이거 밖에 없다!라고 해서 냈더니 너무 순순히 성공이 뜬... 신기하다. 1. 그림 chaaany.tistory.com 종전에 풀었던 어린왕자와 같이 원의 방정식과 좌표평면 상의 거리구하기 개념으로 접근하면 바로 풀린다. 기하는 그냥 아냐 모르냐의 개념이기에 바로 소스코드 들어간다. 1.1 x 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 19. 백준 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. 이전 1 2 3 4 5 6 다음 728x90
