[백준] 5676.음주코딩 - 세그먼트 트리 (JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/5676 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net ​ 📕 문제 접근 📕 -기존 세그먼트 트리와 매우 유사하지만 EOF 를 처리하는 유형의 문제이다 - 여러가지 방법이 존재하지만 본인의 경우 try - catch 방식을 활용하여 문제를 해결하였다. - 문제에서 정확한 숫자가 아닌 음수 혹은 정수 혹은 0을 요구했기에 입력 받는 과정에서 음수면 - 양수면 +의 로직을 활용하였다. 💻 Code 💻 import java.io.Buffer..

• format_list_bulleted Algo 풀이
• · 2023. 7. 16.
• textsms

[백준] 2268.수들의 합 7 - 세그먼트트리(JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/2268 ​ 📕 문제 접근 📕 해당 문제는 세그먼트 트리에서 트리를 만드는 과정에 없어지고 modify와 sum만하면 풀 수 있도록 만들어진 문제다 세그먼트 트리의 정석적인 풀이 방법대로 풀면 매우 쉽지만 문제를 잘 읽어야한다. N개의 수 A[1], A[2], …, A[N] 이 주어졌을 때, 함수 Sum(i, j)는 A[i] + A[i+1] + … + A[j]를 구하는 함수이다. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때** 해당 조건을 확인하면 i > j 일 때 도 있다는 의미가 내포되어있다. 해당 부분을 놓친다면 답이 틀리게된다. 💻 Code 💻 import java.io.Buffer..

• format_list_bulleted Algo 풀이
• · 2023. 7. 15.
• textsms

SegmentTree 개념

💡 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 연산을 진행하기 위해 사용하는 자료구조 문제인식 N개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지의 합을 구하는 것은 어려운 일이 아니다. 예를 들면, 아래 배열에서 5번째에서 11번째 까지 더하는 방법은 그냥 배열을 돌면서 더하면 된다. 그 시간 복잡도는 대략 O(N) 이다. 하지만 이와 같은 a, b의 쌍이 M개 주어졌을 때는 O(M*N) 이 된다. 너무 오래 걸리니까 더 좋은 방법을 찾아보자. 구간 합을 구할 때마다 N을 전부 도는게 너무 오래 걸린다면, 특정 구간의 합을 미리 저장하고 이 값들의 합을 구해보자. 이때, 이진 트리를 활용할 수 있다. 트리 생성 구간 합을 저장해 보자. 이 전체 의 합은 66이다. 이 구간의..

• format_list_bulleted Algo 개념
• · 2023. 7. 13.
• textsms