본문 바로가기

분류 전체보기108

[백준] 2357번 최솟값과 최댓값 자바 문제 (세그먼트 트리) https://www.acmicpc.net/problem/2357  문제 풀이 일일이 구간 내에서 for문을 돌려서 최대 최소를 구하면 시간초과가 난다.정수 배열의 특정 구간 내에서 연산을 해야 하는 세그먼트 트리의 응용 버전이다. 그래서 구간 별로 최소값과 최댓값을 미리 한번에 저장해두고 입력값을 바로 도출해 내야 한다.구간 별 최소값 및 최대값 을 저장해놓은 트리배열 2개를 각각 생성하여 따로 호출하여 출력했다.   소스 코드 public class b_2357 { static int[] arr; static int[] minTree, maxTree; public static void main(String[] args) { Scanner sc = new Scanner(Sys.. 2024. 10. 28.
[JAVA] 세그먼트 트리 (Segment Tree) 세그먼트 트리 - 연속된 구간 또는 특정 구간 내 데이터에 대한 연산을 빠르게 구할 수 있는 트리- 리프노드에는 배열의 수 자체 저장  리프노드가 아닌 노드에는 왼쪽 자식노드와 오른쪽 자식노드의 합 저장- 리프노드를 제외한 다른 모드 노드는 항상 2개의 자식을 가진다- 어떤 노드의 인덱스가 n일때, 왼쪽 자식노드는 2n이고 오른쪽 자식노드는 2n+1 이다- Full Binary Tree 이다 (N이 2의 제곱근일 경우 Perfect Binary Tree)- 리프노드가 N개인 Full Binary Tree에는 리프노드가 아닌 노드가 N-1개 있으므로  필요한 노드 개수는 2N - 1개 이다 ✅ 참고사항 : 트리 개념- 이진트리 (Binary Tree) : 각 노드가 최대 2개의 자식 노드를 가지는 트리- .. 2024. 10. 21.
[2024 SQLD] SQLD 52회 시험 후기 SQLD SQLD(Developer)는 국가공인자격증으로 데이터베이스 관련 자격증이다. 국가공인자격증은 법인, 단체 등 민간 기관에서 운영하는 자격증 중 국가의 공인을 받아 신뢰성을 확보한 자격증이라고 한다. 취득일 1년 6개월이 지난 시점부터 2년 이내에 보수교육을 받아야 영구 자격증으로 갱신이 가능하다. (데이터 자격검정 사이트 → 로그인 → 마이페이지 → 보수교육) 시험 범위 이번에 2024년 52회 부터 개정이 되었다. 옵티마이저랑 실행계획 부분이 있었는데 빠졌다. 근데 원래도 해당 부분은 SQLP에서 나오는 부분이라 시험 출제는 거의 안되었다고 하니 저번이나 개정 후 범위나 비슷할 것 같다. 시험 커트라인은 총점 60점 이상, 각 과목 별로 40% 미만은 과락이다. 결론적으로 1과목에서 4문제,.. 2024. 3. 11.
[PCCP모의고사2] 3번 카페 확장 JAVA 문제 (구현) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 0초 부터 손님이 마지막으로 입장할 시간의 초까지 for문으로 돌리면서 계산하였다. i초 동안 반복하면서 1. 음료가 만들어지는 경우 / 2. 손님이 들어오는 경우 두 가지를 처리하면서 현재 인원을 계산했다. 여기서 내가 실수했던 부분은 음료가 다 만들어져서 사람이 나가자마자 바로 다음 음료를 만드는 것으로 구현했는데, 사람이 한 명 더 들어오기 전에 음료 제조가 끝나는 경우도 생각을 해주어야 했다. 그래서 처음에 몇몇 테스트케이스가 맞지않아서 해당 질문 목록에 있는 반례 예시로 다시.. 2024. 2. 19.
[PCCP모의고사2] 2번 신입사원 교육 JAVA 문제 (우선순위 큐) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음에는 Arrays.sort() 사용하여 매번 반복해서 정렬 후 앞 2개를 뽑아내서 더해줬었다. 시간초과 날 것 같긴했는데 역시나..ㅎ 제일 작은 수를 뽑아내기 위해 정렬말고 다른 자료 구조를 써야 효과적으로 뽑아낼 수 있을까 고민했는데 결국에는 구글링을 통해 Priority Queue(우선순위큐) 를 이용해야 한다는 것을 알게 되었다. 우선순위큐 자체는 자바에 내장되어 있는 자료구조를 바로 이용하면 되서 구현은 참 쉬웠지만 내부적인 원리를 이해하려면 조금 각잡고 트리 공부를.. 2024. 2. 19.
[PCCP모의고사2] 1번 실습용 로봇 JAVA 문제 (구현) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제에 나온대로 명령어 4개에 따른 이동값을 분기별로 처리해주었다. R : 오른쪽 90도 회전 L : 왼쪽 90도 회전 G : 한칸 전진 B : 한칸 후진 기본 세팅값은 direction = 0, (0,0) 위치이고 G와 B의 이동 수식은 배열을 이용하였다. G기준일 때 방향에 따라 아래와 같이 움직이고, B은 반대이므로 *-1 해주면서 그대로 배열을 사용했다. direction [0] [1] [2] [3] dx = {0, 1, 0, -1} dy = {1, 0, -1, 0} 소스 코드.. 2024. 2. 17.

티스토리툴바