알고리즘공부(Algorithm Study)83 백준 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. 백준 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. 이전 1 2 3 4 5 6 7 다음 728x90
