분류 전체보기 검색 결과

해당 글 230건

[백준 7453] 합이 0인 네 정수 -JAVA // le_effort//

문제만 오랫동안 쳐다본 거 같다. 문제를 이해하지 못했다 저기서 A B C D 배열이 어디있지? 이 생각부터 들었는데 배열이 세로로 되어있는 것이다 즉 A배열 B배열 -45 22 -41 -27 -36 53 -36 30 26 -38 -32 -54 그리고 n이 4000이니 A B C D 전부 4중반복문으로 검사를 하면 시간 내에 들어오지 못한다 그래서 두개의 배열을 한 개로 묶어서 해주는데 AB배열 ( 크기가 2일때 A [0]+B [0] A [0]+B [1] A [1]+B [0] A [1]+B [1]) CD 배열 이하 동문 그리고 주의할 점이 있는데 밑 코드 중 AB_cnt와 CD_cnt 그리고 ans는 int형을 벗어날 수 있으므로 long으로 써야 한다. 그러곤 여타 다른 문제와 같이 투 포인터 알고리즘..
알고리즘 2020. 3. 3. 10:04

[백준 13913] 숨바꼭질4 -JAVA // le_effort//

bfs를 활용한 가장 빠른 시간을 찾는 문제 이동한 경로도 출력을 해야 하는데 어떻게 해야 할지 고민을 많이 했다 여태껏 visited 배열을 보통 boolean으로 true / false 로만 접근을 했었는데 -1로 초기화를 하고 visited 배열 값을 방문한 위치로 넣었다. 출발지 (n) 에서 목적지(m)에 도착을 한다면 m == n 이 될 때까지 재귀 호출을 통해 값을 넣어주었다 이는 역순으로 저장되니 선입후출 개념인 스택을 사용했고 while문 실행 전 목적지는 visited 값에 들어가지 않음으로 먼저 넣어주고 while문을 실행 하였다. 전체 코드 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 ..
알고리즘 2020. 2. 28. 19:16

[백준 2143] 두 배열의 합 - JAVA // le_effort//

문제를 읽고 쉽게 풀 줄 알았는데 삽질을 했다. https://suhyeokeee.tistory.com/4 [백준 1208] 부분수열의 합2 자바// le_effot// 비슷한 유형의 문제들이 많은데 이 문제는 고생해서 풀었다. 일단 N이 40이니 2^40 이면 1초 안에 들어오지 못하니 2^20으로 두번 한다는 발상 조차 떠올리지 못해 다른 블로그들의 도움을 받았다 배열을 반으로.. suhyeokeee.tistory.com 이 문제와 똑같이 접근하면 된다고 생각했었는데 여전히 나의 실력이 부족하다는 걸 느끼게 해 준 문제였다 일단 1208번 문제의 경우 "부분 수열" 이다 즉 {1,2,3} 이 있다면 올 수 있는 부분 수열은 {1} , {2} , {3}, {1,2} , {1,3} {2,3} {1,2,3..
알고리즘 2020. 2. 28. 18:10

[백준 1208] 부분수열의 합2 자바// le_effot//

비슷한 유형의 문제들이 많은데 이 문제는 고생해서 풀었다. 일단 N이 40이니 2^40 이면 1초 안에 들어오지 못하니 2^20으로 두번 한다는 발상 조차 떠올리지 못해 다른 블로그들의 도움을 받았다 배열을 반으로 쪼개서 (left와 right로 나누겠다) 각각 left와 right에 들어 갈 수 있는 부분수열들을 집어 넣으면 되는데 재귀호출을 이용한다 1 2 3 4 5 6 7 8 public static void dfs(int level, int end, int sum ,ArrayListlist) { if(level == end) { list.add(sum); return ; } dfs(level+1,end,sum+arr[level],list); dfs(level+1,end,sum,list); } ht..
알고리즘 2020. 2. 28. 16:22

[백준 1644] 소수의 연속합 자바 //le_effort//

1806번 문제와 비슷한 문제이다 https://suhyeokeee.tistory.com/2 백준 1806 부분합 자바 //le_effort// 부분합을 구하는 문제이다 N이 100,000 으로써 일반적인 2중반복문을 한다면 O(N^2)으로 1초안에 들어오지 못해 오답을 받는다. 이를 해결하기 위해선 투포인터 알고리즘을 쓰면 된다. 1 2 3 4 5 6 7 8 9 10 11 1.. suhyeokeee.tistory.com 위 문제와 똑같은 투포인터 알고리즘으로 1806번 문제와는 달리 소수의 연속합을 구하는 것이다 이 문제에선 sum이 목표치와 도달하면 cnt를 증가 시켜주면 된다 소수를 구하는 알고리즘은 에라토스테네스의 체를 사용했다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..
알고리즘 2020. 2. 28. 14:44

[백준 1806] 부분합 자바 //le_effort//

부분합을 구하는 문제이다 N이 100,000 으로써 일반적인 2중반복문을 한다면 O(N^2)으로 1초안에 들어오지 못해 오답을 받는다. 이를 해결하기 위해선 투포인터 알고리즘을 쓰면 된다. 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 import java.io.*; import java.util.*; public class Main { static int n,s; static int arr[]; static int cnt=0; public static void main(String[] args) throws IOException{ ..
알고리즘 2020. 2. 28. 14:32