[Algorithm] Lower Bound & Upper Bound

이진탐색을 이용해 주어진 target 값을 찾을 때, 만약 target이 배열에 여러 개 있다면, 어떤 위치가 나올지 모르게 됩니다. 이때, Lower Bound를 사용할 수 있습니다.Lower BoundLower Bound는원하는 값 target 이상의 값이 최초로 나오는 위치를 의미합니다.즉, target보다 같거나 큰 원소의 위치들 중 가장 작은 값을 출력해야 한다는 것을 말합니다.코드로 나타내면 다음과 같습니다.int lowerBound(int target) { int left = 0; // 첫 번째 원소의 위치로 설정합니다. int right = n - 1; // 마지막 원소의 위치로 설정합니다. i..

• format_list_bulleted 알고리즘/알고리즘
• · 2024. 12. 17.
• textsms

[Algorithm] 트리의 지름

트리의 특징트리에서는 어떠한 두 정점을 고르더라도 두 정점 사이를 연결하는 경로는 유일하게 결정된다는 특징이 있습니다. 또한, 트리의 모든 정점은 트리의 root 역할을 수행할 수 있습니다. 각 간선에 가중치가 있는 트리 정보가 주어졌을 때, 트리의 지름이란모든 정점 쌍에 대한 거리 중 가장 긴 경로의 길이를 말합니다.트리의 지름을 찾는 알고리즘트리의 지름을 가장 쉽게 구하는 방법은 다음과 같습니다.아무 정점이나 잡고 시작해 DFS를 이용해 시작점으로부터 가장 먼 정점을 구합니다. 거리가 동일한 정점이 여러 개라면 아무 정점이나 골라도 상관없습니다. DFS를 통해 동일한 방식으로 위에서 구한 정점을 시작점으로 하였을 때, 가장 먼 정점을 구합니다.이때 구해진 거리가 트리의 지름이 됩니다.예로 아래 그림에..

• format_list_bulleted 알고리즘/알고리즘
• · 2024. 12. 6.
• textsms

[Programmers] Level 3 : 셔틀버스

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/17678 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr💡 풀이콘이 정류장에 도착 가능한 제일 늦은 시각을 구하는 문제이기 때문에, 셔틀의 막차 시간을 이용해 풀이할 수 있습니다. 다음과 같은 과정으로 풀이할 수 있습니다. 우선 모든 시간을 분 단위로 계산합니다. 계산된 `timetable`을 오름차순으로 정렬합니다. → 여기서 저는 우선순위 큐를 사용했습니다.첫 셔틀부터 막차 전 버스까지 셔틀의 도착 시간으로 반복문을 진행합니다. 이때, 셔틀의..

• format_list_bulleted 알고리즘/프로그래머스
• · 2024. 9. 22.
• textsms

[Programmers] Level 3 : 길 찾기 게임

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr💡 풀이주어진 데이터를 토대로 이진 트리를 만들고, 전위 순회, 후위 순회를 구현하면 되는 자료구조 문제입니다. 데이터 처리우선, 각 노드를 저장할 클래스를 만들어 줍니다. Nodeclass Node { int index; int x, y; Node left, right; Node(int index, int x, int y) { this.index = ind..

• format_list_bulleted 알고리즘/프로그래머스
• · 2024. 6. 10.
• textsms

[Programmers] Level 3 : 단어 변환(Java)

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 단어를 변환하며 begin에서 시작해 target까지 도달할 수 있는 최단 거리를 구하는 문제입니다. 따라서, 다음과 같은 단계를 통해 문제를 해결했습니다. 단어들이 있는 `words` 배열을 탐색하며 서로 변환 가능한 단어들 연결하기 이때, 단어 변환이 가능한 경우는 1 글자만 다른 경우입니다. 이 조건을 이용해 서로 변환이 가능한지 확인한 뒤, 가능하다면 인덱스 번호로 단어..

• format_list_bulleted 알고리즘/프로그래머스
• · 2024. 4. 2.
• textsms

[BOJ] 17387 : 선분 교차 2(Java)

문제 링크 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 💡 풀이 해당 문제는 CCW라는 기하 알고리즘을 사용합니다. CCW CCW는 Counter-ClockWise의 약어로 평면 위에 놓여진 세 점의 방향관계를 구하는 알고리즘 입니다. 즉, CCW는 점 A, B, C를 순서대로 봤을 때, 부호에 따라 위치관계를 파악할 수 있습니다. CCW 0 := 반시계 방향 CCW는 외적을 이용해서 계산합니다. 하지만, 여기서 CCW에 대해 자세하게 다루..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 2. 27.
• textsms