본문 바로가기

알고리즘 문제 풀이207

9205번: 맥주 마시면서 걸어가기 제한사항 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50) 각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100). 다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767) 송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리) 문제 정리 출발점에서 편의점을 들려서 도착점으로 가거나, 출발점에서 바로 도착점으로 간다. 접근 방법 출발점에서 도착점에 도달 가능한 경우가 무엇일까요? 딱 밑에 두 가지 경우입니다. 출발지에서 도착점까지 거리가 1000.. 2023. 12. 12.
1309번: 동물원(Kotlin, C++) 제한사항 1 ≤ N ≤ 100,000 첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라. 문제 정리 사자는 자신의 주위(사방면)에 다른 사자가 있으면 안된다. 사자를 둘 수 있는 방법을 모두 구하시오. 접근 방법 DP라고는 생각했는데 제한 시간 내에 못 풀어서 다른 사람 답안 봤습니다. 핵심은 위에 사자가 있는 경우와 위에 왼쪽에 사자가 있는 경우 위에 오른쪽에 사자가 있는 경우를 생각해서 풉니다. case1) 현재 블록에 사자를 안 두는 경우 이 경우에는 위에 사자가 어디 있든 지 상관 없습니다. 따라서, 아래 세 가지 수의 합이 사자를 안 두는 경우입니다. 위에 사자가 없는 경우(dp[n-1][0]) 위에 왼쪽에 사자가 있는 경우(dp[n-1][1]) 위에 오른쪽에 사자가 있.. 2023. 12. 10.
70. Climbing Stairs 문제 출처 : https://leetcode.com/problems/climbing-stairs/description/ [문제 설명] 계단을 1걸음, 2걸음 오를 수 있을 때 n번째 계단까지 오를 수 있는 방법은? [접근 방법] 전형적인 dp 연습문제. n번째 계단에 올라가는 방법은 n-1번째 계단에서 1걸음 올라가기 + n-2번째 계단에서 2걸음 올라가기 점화식 : dp[n] = dp[n - 1] + dp[n - 2] 굳이 배열을 사용하지 않고 변수만 두고도 풀 수 있는 문제지만 n의 최대 크기가 45밖에 되지 않으므로 배열을 사용하여 풀었다. class Solution { public: int climbStairs(int n) { if (n 2023. 7. 25.
2349. Design a Number Container System 문제 출처 : https://leetcode.com/problems/design-a-number-container-system/ [문제 설명] insert, find 함수를 구현하시오. insert(int index, int number) : 해당하는 인덱스의 number 값을 대입한다. find(int number) : number를 가지는 인덱스 중에서 최솟값을 반환하라. 단, number에 해당하는 값이 없으면 -1을 리턴 [접근 방법] 1. 인덱스와 값을 구현하기 위해서 단순 배열을 사용하면 어떨까 생각 2. 그러나, 주어진 number의 최댓값이 10^9이므로 단순 배열 생성에만 10^9가 필요함. 3. map을 통해 key를 인덱스 value를 숫자로 하는 맵과 key를 숫자 value를 인덱.. 2023. 7. 25.
[LeetCode] - 35. Search Insert Position 문제 출처 : https://leetcode.com/problems/search-insert-position/description/ [문제 설명] The array is sorted. so you can use a binary search algorithm, not a linear search. the time complexity of a linear search is O(N) but a binary search is O(logN). (N is the size of the array) The given array has consisted of distinct integers. So if you find a target's index then you should return the index. if you.. 2023. 7. 5.
프로그래머스 - 미로 탈출(Kotlin) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. https://github.com/ROUTINE-STUDY/Algorithm 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능 초보 알고리즘 스터디 / 누구나 참여 가능 :runner:. Contribute to ROUTINE-STUDY/Algorithm development by creating an account on GitHub. github.com 문의는 댓글 바람. 문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/159993.. 2023. 3. 13.