[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

[BOJ] 14003 : 가장 긴 증가하는 부분 수열 5(Java)

문제 링크 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 💡 풀이 기존 가장 긴 증가하는 부분 수열 즉, LIS을 응용해야 하는 문제입니다. LIS - DP LIS를 해결하는 가장 간편한 방법은 DP를 이용하는 것입니다. 주어진 숫자 배열에서 인덱스를 한 칸씩 늘려가며 확인하는 방법입니다. 하지만, 이 방법은 2중 반복문을 사용하기 때문에 $O(N^2)$의 시간복잡도를 가집니다. 따라서, 해당 문제는 입력 N의 ..

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

[BOJ] 1509 : 팰린드롬 분할(Java)

문제 링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 💡 풀이 기존 팰린드롬 문제와 다이나믹 프로그래밍을 함께 사용하는 문제입니다. 로직은 다음과 같습니다. 문자열의 i번째까지 탐색했을 때의 분할 개수의 최솟값을 `dp[i]`로 나타내겠습니다. 이 `dp[]` 배열 활용해 다이나믹 프로그래밍을 진행합니다. 맨 오른쪽 즉, 문자열의 i번째 인덱스를 기준으로 1 ~ (i - ..

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