오뚝이개발자

문제 programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 DP를 사용해 푸는 문제이다. 문제에서 이동은 오른쪽과 아래쪽으로만 가능하다고 했으니, 한 지점까지 올 수 있는 가능한 경로는 그 지점의 위와 왼쪽칸으로부터이다. 따라서 각 칸마다 그 칸까지 도달가능한 경로의 수를 저장하면 된다. grid라는 n x m 2차원 리스트를 만들어 (0,0)에 1을 넣고, puddle에는 -1을 넣는다. 그 후, 이중for문으..

문제 programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 풀이 처음엔 이분탐색을 사용하지 않고 time stamp를 찍어 반복문을 돌 때마다 시간이 1씩 경과하도록 구현하였다. 그런데 역시나 시간초과에 걸렸다. 어려웠던 부분이 어떠한 기준으로 이분탐색을 하고, 어떤 값을 탐색으로 찾아야 하는지를 정하는 것이었다. 결국 다른 블로그를 참고해서 구현하였다. 먼저 이분 탐색으로 찾아야 하는 값은 "return해야 하는 최소 소요 ..

문제 programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 풀이 처음엔 단순한 문제인줄 알고 DFS를 사용하지 않고 풀어보려 했다. 내가 생각한 방식은 이러했다. 출발점이 ICN인 것들 추출해서 도착점 알파벳 순으로 앞서는 것은 선택한다. 1에서 선택한 경로의 도착점이 출발점인 것을 골라 알파벳순으로 비교하고 선택하는 과정을 반복한다. 그런데 문제는 위와 같은 방법으로 풀이했을 때 반례가 존재한다는 것이다. [["ICN","JFK"],["ICN","..

문제 문제가 조금 복잡해서 링크를 첨부하겠다. programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 풀이 전공자거나 운영체제의 스케쥴링 부분을 공부한 사람이라면 소요시간이 작은 작업을 우선적으로 처리하는 것이 최적의 경우라는 것을 알 것이다. 우선순위큐를 이용하면 되는데 약간은 복잡한 조건을 고려해주어야 한다. 그러나 단순히 소요시간 기준으로 정렬해 처리하면 다른 조건들을 고려하지 못한다. 생각의 순서는 다음과 같다. ..

문제설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 입출력 예에 대..

문제설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다...

문제설명 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다. 제한사항 문자열 s의 길이 : 2,500 이하의 자연수 문자열 s는 알파벳 소문자로만 구성 입출력 예 입출력 예에 대한 설명 입출력 예 #1 4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다. 입출력 예 #2 2번째자리 'b'를 기준으로 aba가 팰린드롬이 되므로 3을 return합니다. 풀이 주어진 문자열 s의 부분 문자열들을 모두 검..

문제설명 제한사항 operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다. operations의 원소는 큐가 수행할 연산을 나타냅니다. 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다. 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다. 입출력 예 입출력 예에 대한 설명 16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다. 7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다. 풀이 굳이 힙을 사용하지 않고도 풀 수 있다. 구현이 중심인 문제이기에 문제의 조건에 따라 if문을 적절히 사용하여 구현하면 된다. def solut..