전체 글1104 누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java 목차 ※ 배열의 인덱스는 알다시피 0부터 시작한다. 예를들어 N개의 데이터가 있다면 0번 인덱스부터 N-1번 인덱스까지 존재한다. 다만 구현에 있어 누적 합을 구현할 때는 인덱스 1번부터 사용하는게 훨씬 편하다. 즉, N개의 데이터가 존재할 경우, N+1크기의 배열을 만든 후 1번 인덱스부터 N번 인덱스까지를 사용하는게 구현하기 편하다. 따라서 이하 글에서는 후자의 방식을 사용해 서술한다. ※ 코드는 자바 기준으로 작성했지만, 어려운 코드가 아니므로 다른 언어 사용자도 문제없이 볼 수 있어요. 누적 합 (prefix sum) 1. 반복문으로 구간 합을 구할때의 문제점 특정 구간의 합을 구하는 경우를 생각해보자. 예를들어 백준의 구간 합 구하기 4 문제를 보자. 최대 10만개짜리 배열에서, 최대 10만개의.. 2022. 8. 9. [자바, 코틀린] 백준 17390 - 이건 꼭 풀어야 해! (java, kotlin) 문제 : boj17390 필요 알고리즘 개념 누적 합 (prefix sum) 연속된 범위의 합을 O(1)로 구하기 위해 누적 합을 사용한다. 누적 합에 대한 개념이 있어야 풀 수 있다. 정렬 정렬이 무엇인지, 자바나 코틀린으로 정렬은 어떻게 하는지 알아야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 비내림차순으로 정렬해야 한다. 비내림차순이 생소할 수 있다. 그냥 이 문제에서는 오름차순이라고 생각하면 된.. 2022. 8. 8. [자바] 백준 2986 - 파스칼 (java) 문제 : boj2986 필요 알고리즘 개념 소수 판정 소수 판정 시 소수인지 알고 싶은 값 N에 대해 sqrt(N) 까지만 살펴보면 된다는 점을 알아야 풀 수 있다. 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 글에서 해당 개념을 익힐 수 있다. 수학, 정수론 기본적인 수학 지식이 있어야 풀 수 있다. 정확힌 나머지 연산에 대한 개념과 소수(prime number)가 무엇인지, 약수가 무엇인지 정도만 알면 된다. 나머지 연산 : 코드에서는 일반적으로 '%'로 표현된다. A%B는 A를 B로 나누고 남은 나머지를 뜻한다. A%B==0 이라면 B가 A의 약수임을 뜻한다. 소수(prime number) : 2이상의 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 예를들어 2,3,.. 2022. 8. 7. [자바] 백준 8394 - 악수 (java) 문제 : boj8394 필요 알고리즘 개념 동적계획법 (다이나믹 프로그래밍, DP, dynamic programming) 동적계획법을 안다면 어렵지 않게 풀 수 있다. 동적계획법을 몇 개 풀어봤었다면 풀이를 몇초만에 떠올릴 수 있는 정도로 응용없이 기본적인 형태의 문제이다. 참고로 방법의 수, 경우의 수를 구하는 문제들은 높은 확률로 동적계획법을 사용해 풀리는 경우가 많다. 나머지 연산 (모듈러, modular) 수가 매우 커지므로, 자바의 BigInteger(큰 수 표현 가능. 대신 느림)를 쓰거나, 나머지 연산을 사용해줘야 한다(안해보긴 했는데 BigInteger 사용하면 메모리초과날 것 같긴하다). '%'를 사용하는 나머지 연산을 알고 있어야 더 쉽게 통과 가능하다. ※ 제 코드에서 왜 main 함.. 2022. 8. 6. [자바] 백준 23882 - 알고리즘 수업 - 선택 정렬 2 (java) 문제 : boj23882 필요 알고리즘 개념 시뮬레이션 문제 자체가 풀이에 해당하고 문제 그대로 구현해주면 되므로 시뮬레이션이라 볼 수 있다. 딱히 이걸 알아야 풀 수 있는건 아니다. 정렬 정렬이 뭘 하는건지 알고 있어야 한다.역시 딱히 이걸 알아야 풀 수 있는건 아니다. 문제 자체가 풀이에 해당하므로! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 자체가 풀이에 해당하기 떄문에 별도로 말할건 없을 것 같다. 그래도 설.. 2022. 8. 6. [자바] 백준 23881 - 알고리즘 수업 - 선택 정렬 1 (java) 문제 : boj23881 필요 알고리즘 개념 시뮬레이션 문제 자체가 풀이에 해당하고 문제 그대로 구현해주면 되므로 시뮬레이션이라 볼 수 있다. 딱히 이걸 알아야 풀 수 있는건 아니다. 정렬 정렬이 뭘 하는건지 알고 있어야 한다.역시 딱히 이걸 알아야 풀 수 있는건 아니다. 문제 자체가 풀이에 해당하므로! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 자체가 풀이에 해당하기 떄문에 별도로 말할건 없을 것 같다. 그래도 설.. 2022. 8. 4. [자바] 백준 10829 - 이진수 변환 (java) 문제 : boj10829 필요 알고리즘 개념 이진수 이진수가 무엇인지 알아야 풀 수 있다. int보다 큰 수 int형으로 표현할 수 없는 수를 다룰 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N이 int 표현 범위를 넘어간다. long 범위 이내로는 들어오므로 long으로 받아주면 된다. 자바에 이미 int나 long을 이진수 String으로 변환하는 함수가 있다. 해당 함수를 사용해주면 단순하게 .. 2022. 8. 3. [자바] 백준 10830 - 행렬 제곱 (java) 문제 : boj10830 필요 알고리즘 개념 행렬 곱셈 (수학) 행렬끼리 곱하는 방법을 알아야 한다. 분할정복을 이용한 거듭제곱 분할정복을 이용해 거듭제곱을 최적화하는 방법을 알아야 한다. 나머지 연산의 분배법칙 나머지 연산의 분배법칙을 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 행렬끼리 곱하는 방법을 모른다면, 구글링을 통해 알아보자. 기초 수학이므로 반드시 알고 있어야 한다. N이 3인.. 2022. 8. 2. [자바] 백준 1148 - 단어 만들기 (java) 문제 : boj1148 필요 알고리즘 개념 문자열 문자열의 각 character에서 원하는 정보를 뽑아낼 수 있어야 한다. 아스키 코드 아스키 코드에 대한 이해가 좀 있어야 한다. 구현력(?) 사실 로직 자체의 난이도는 실버 중하위수준인데, 구현이 빡쌘편이라 골드로 책정된 문제이다 ㅋㅋ 자신이 생각난걸 구현하는데 평소에 무리가 없었어야 풀만할 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 로직부터 한번 살펴보자. .. 2022. 8. 2. [자바] 백준 20955 - 민서의 응급 수술 (java) 문제 : boj20955 필요 알고리즘 개념 트리 트리의 특징에 대해 알고 있어야 이 문제를 풀 수 있다. 분리 집합 (disjoint set) 혹은 유니온 파인드 (union-find) 분리 집합 알고리즘인 유니온 파인드를 알고 있으면 간단하게 이 문제를 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서는 정점의 개수가 주어지고(N), M개의 간선 정보가 주어진다. 그럼 다음의 입력값을 생각해보자. .. 2022. 7. 31. 이전 1 ··· 60 61 62 63 64 65 66 ··· 111 다음
