알고리즘

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제1~n까지 서로 다른 번호가 매겨진 등대 n개가 존재한다.뱃길은 n-1개 존재하며, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있다.한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져있도록 등대를 켜두어야 한다. - 2 ≤ n ≤ 100,000- lighthouse의 길이 = n – 1- lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대가 뱃길로 연결되어 있다는 의미- 1 ≤ a ≠ b ≤ n- 모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 존재하도록 입력이 주어진다. 풀이 ..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제자연수 x를 y로 변환하려고 한다. 사용할 수 있는 연산은 다음의 3개가 가능하다.- x에 n을 더한다.- x에 2를 곱한다.- x에 3을 곱한다.x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return, 만들 수 없다면 -1 return - 1 ≤ x ≤ 1,000,000- 1 ≤ n  풀이 과정풀이 시간: 15분알고리즘: BFSx와 y를 노드라고 생각한다면 시작 노드에서 도착 노드까지 가는 최단 거리(시간)를 구하는 문제이기 때문에 BFS로 풀이가 가능하다. O(y): 최악의 경우 y개의 모든 노드를 ..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제왼손(4), 오른손(6)위에 두고 타이핑을 시작- 이동하지 않고, 제자리에서 다시 누르는 경우: 가중치 1- 상하좌우 인접한 숫자를 누르는 경우: 가중치 2- 대각선으로 인접한 숫자를 누르는 경우: 가중치 3- 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따른다. 1 ≤ numbers의 길이 ≤ 100,000- numbers는 아라비아 숫자로만 이루어진 문자열 풀이 과정풀이 시간: 2시간 이상 접근하다 포기하고 접근방법 참고알고리즘: DP + BFS1. 초기 설정-..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제정수로 이루어진 배열 numbers모든 원소에 대해 뒷 큰수들을 차례대로 담은 배열을 return(단, 뒷 큰수가 존재하지 않는 원소는 -1을 담는다)- 4 ≤ numbers의 길이 ≤ 1,000,000    - 1 ≤ numbers[i] ≤ 1,000,000 풀이 과정풀이 시간: 25분알고리즘: 자료구조(스택) or 우선순위큐(힙)numbers의 길이가 최대 1,000,000이기 때문에 최악의 경우 O(NlogN)으로 풀이해야 한다. 1. stack을 이용해 O(N)으로 풀이할 경우맨 뒤의 수는 항상 뒷큰수를..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제1억 x 1억 크기의 행렬이 주어진다.s보다 크거나 같고 e보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 한다.만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 한다. - 1 ≤ e ≤ 5,000,000- 1 ≤ starts의 길이 ≤ min {e,100,000}- 1 ≤ starts의 원소 ≤ e- starts에는 중복되는 원소가 존재하지 않는다. 풀이 과정풀이 시간: 2시간 이상알고리즘: 수학, 누적합이 문제의 경우, e가 최대 5,000,000이기 때문에 시간복..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타낸다. - 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룬다.- 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타낸다.지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제n x m 격자 미로 -> 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 한다. 1. 격자의 바깥으로는 나갈 수 없다. 2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 한다. 3. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 된다. 4. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 한다. - 2 ≤ n (= 미로의 세로 길이) ≤ 50 - 2 ≤ m (= 미로의 가로 길이) ≤ 50 - 1 ≤..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제최소한의 객실 만을 사용해 예약 손님을 받는다.한 번 사용한 객실은 '퇴실 시간'을 기준으로 10분 후 다음 손님이 사용 가능-> 코니에게 필요한 최소 객실의 수를 반환 1 ≤ book_time의 길이 ≤ 1,000- book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 [대실 시작 시각, 대실 종료 시각]- "00:00"부터 "23:59"까지로 주어진다. 풀이과정풀이 시간: 20분알고리즘: 그리디1. 시작 시각을 기준으로 오름차순 정렬2. 시각을 하나씩 확인하며 객실 배정- 힙(종료시각)이 비어..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제각 칸은 '통로' or '벽'('벽'으로는 지나갈 수 없고, '통로'로만 이동 가능)- '문': 미로를 빠져나가는 문- '레버': '통로'들 중 한 칸1. 출발점에서 '레버'가 있는 칸으로 이동2. '문'이 있는 칸으로 이동- 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있다.- 5 ≤ maps의 길이 ≤ 100    - 5 ≤ maps[i]의 길이 ≤ 100- maps[i]는 다음 5개의 문자들로만 이루어져 있다.    - S : 시작 지점    - E : 출구    - L : 레버    - O : ..