알고리즘37 [카카오 2018] 방금 그 곡 📌문제 시간과 문자열을 포함하는 배열이 주어진다. 예시 : ["12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"] 배열의 3번째 원소는 해당 곡의 이름, 4번째 원소는 해당 곡의 연주 순서이다. 해당 곡은 12:14 - 12:00 = 14 만큼 반복된다. 반복의 의미는 CDEFGAB CDEFGAB CD 와 같이 총 14번의 loop를 돈다는 의미이다. 해당 배열과 함께 문자열 m이 주어진다. 문자열 m과 일치하는 곡이 어느 곡인지 출력하라. ▸문제 링크 https://programmers.co.kr/learn/courses/30/lessons/17683 📌문제 풀이 해당 문제에서는 C#과 같이 음표가 1음절이 아니라, 2음절이 생길 수 있다. 해당 음표는 .. 2022. 1. 17. [Dijkstra] 파티 📌 문제 문제 링크 : https://www.acmicpc.net/problem/1238 문제 유형 : 다익스트라 문제 난이도 : 골드3 문제 : N개의 마을이 있다. 각 마을에는 1명의 사람이 산다. 마을 한 곳에서 파티를 한다. ( 파티를 하는 곳 : X ) N명의 사람은 X에서 모이고, X에서 다시 각자 집으로 돌아간다. 사람들은 이동시간이 최소로 걸리는 경로로 움직인다. 경로는 모두 단방향으로 주어진다. 이 때, 가장 시간이 오래 걸리는 사람의 값을 출력하라. 📌 문제 풀이 전형적인 다익스트라 문제 길찾기를 두번 한다. 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 예제의 값처럼 마을이 N=4, X=2로 주어졌다고 해보자. 그러면 1->2 2->2.. 2022. 1. 4. [Stack] 표 편집 📌 문제 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/81303 문제 난이도 : level 3 문제 유형 : Double LinkedList, Stack 📌 문제 풀이 - First Try : 틀린풀이 : 배열 이용 ▸ 풀이 과정 문제 지문 자체는 쉬운데, 많이 어렵게 느껴졌던 문제다. 처음에는 순진하게(naive) 생각해서 해당 순서의 값을 배열로 설정했다. 그래서 만약 n=7이라고 하면 아래와 같은 그림을 생각했다. 만약 C 명령어 ( 삭제 ) 가 들어올 경우, 해당 칸의 속성을 false로 만들고, 아래 칸으로 내려가는 로직을 생각했다. 만약 Command가 U/D일 경우, false를 건너뛰고 count를 센다. 위와 같은 풀이로 처음 .. 2021. 12. 23. [Two Pointer] 용액 📌 문제 문제 링크 : https://www.acmicpc.net/problem/2467 문제 유형 : 투 포인터 문제 난이도 : 골드5 📌 문제 풀이 양쪽 끝에서 시작하는 투 포인터를 잡는다. 왼쪽에서 오른쪽으로 가는 것은 증가를 의미, 오른쪽에서 왼쪽으로 가는 것은 감소를 의미한다. 이 때, 왼쪽에서 오른쪽으로 움직이는 증가폭이 0에 더 가깝게 만들어 주는지, 오른쪽에서 왼쪽으로 움직이는 감소폭이 0에 더 가깝게 만들어주는지 알 수 없다. 즉, 증가하는 분과 감소하는 분 중 누가 더 0에 가깝게 만들어주는 지 알 수 없다. 그래서 왼쪽 이동후의 값과 오른쪽 이동후의 값을 비교해서 더 작은 쪽으로 움직인다. ▸ 그림 설명 위의 예에서 현재 arr[left] + arr[right] 의 값은 -8이다. 이.. 2021. 12. 23. [Two Pointer] 수 들의 합2 📌 문제 문제 링크 : https://www.acmicpc.net/problem/2003 문제 유형 : 투 포인터 문제 난이도 : 실버3 문제 요약 구간 합 M을 만족하는 배열의 구간이 몇 개나 있는가? 단 O(n)으로 풀어야 한다. 📌 문제 풀이 간단하게 생각해서는, O(n^2) 으로 풀 수 있다. for loop를 두번 돌려서, 만족하는 구간을 찾아주면 된다. 그러나 해당 문제는 O(n)으로 풀어야 한다. 해당 문제는 투포인터를 이용해서 시간 복잡도를 줄일 수 있다. left 와 right으로 구간을 잡는다. 포인터의 이름대로 범위는 left 2021. 12. 22. [Heap] 디스크 컨트롤러 📌 문제 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42627 문제 난이도 : level 3 문제 유형 : 우선순위 큐 ( PriorityQueue ) 문제 요약 : SJF 알고리즘을 통해 프로세스가 움직인다. 프로세스들의 응답시간의 평균값을 반환하라. 📌 풀이 문제도 직관적이고, 풀이도 쉽게 생각나는 문제이지만 개인적으로는 많이 헤맸다. 풀이는 다음과 같다. pq1 = 시간순으로 먼저 들어온 값이 우선 정렬값을 가진다 int[] 배열의 값으로 queue안에 값이 들어간다. arr[0] = 시작 시간 // arr[1] = 걸리는 시간 pq2 = 걸리는 시간순으로 우선 정렬값을 가진다. ▸ 헷갈렸던 부분 while(pq2.isEmpty()) p.. 2021. 12. 22. 색종이 만들기 문제 문제 유형 : 분할정복 색종이를 절반씩 나누어서, 같은 영역이 될때까지 나눈다. 같은 영역이 됐다면 count+1을 해준다. 문제 풀이 대표적인 분할정복 문제이다. 로직은 다음과 같다. 1. n값과 시작위치를 입력값으로 받는다. 2. 맵이 시작위치부터 n까지 전부 같은 값으로 이루어져있는지 확인한다. 2-1). 만약 전부 같은 값으로 이루어졌다면, 1인지 0인지 확인하고 해당 숫자를 1증가시켜준다. 3. 사방으로 나누어서 함수를 재귀 호출한다. 이 때, 넘기는 n의 값은 n/2이다. → 맵이 전부 같은 지 확인하는 부분을 두 방법으로 풀었다. 1번 방법 ) for(int i=0;i 2021. 12. 16. Climbing Stairs - #dp 📌 문제 1칸 혹은 2칸으로만 위를 올라갈 수 있다. N칸을 갔을 때, N칸을 올라올 수 있는 경우의 수는? https://leetcode.com/problems/climbing-stairs/ 📌 문제 풀이 📌 코드 public class Main { public static void main(String[] args) { Solution solution = new Solution(); int i = solution.climbStairs(45); System.out.println(i); } static class Solution { public int climbStairs(int N) { if(N==1) return 1; if(N==2) return 2; int[] dp = new int[N+1]; dp.. 2021. 12. 3. 이전 1 2 3 4 5 다음
