알고리즘 문제풀이
1.[코테] 스택 - 올바른 괄호(문자열 문제)
문제:괄호가 주어질 때, 올바른 괄호면 'True'를 아니면 'False'를 반환하는 함수 작성.입력 예:s - answer"()()" - true"(())()" - true")()(" - false"(()(" - false풀이:stack 자료구조 사용여는 괄호 '(
2.[코테] 주식가격[프로그래머스]
입출력prices : 1, 2, 3, 2, 3return : 4, 3, 1, 1, 0'시작' ~ 'len(prices)-1' 탐색하며 시작 지점보다 작을 때까지 반복문을 진행한다.작은 부분이 나오면 반복문의 길이만큼 answer에 append하고 반복문을 빠져나온다.제
3.[코테] 투 포인터 - 연속된 부분 수열의 합
문제 설명비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.부분 수열의 합은 k입니다.합이 k인 부분 수열이 여러 개인 경우 길이가
4.[코테] 피보나치 수열
문제 설명피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.예를들어F(2) = F(0) + F(1) = 0 + 1 = 1F(3) = F(1) + F(2) = 1 + 1 = 2F
5.[코테] 스택 - 괄호 회전하기
문제: 출처: 프로그래머스 - 괄호 회전하기 문제 설명 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다. (), [], {} 는 모두 올바른 괄호 문자열입니다. 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입
6.[코테] 큐, 리스트(문자열) - 연속 부분 수열 합의 개수
문제 설명:철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다.
7.[코테] DFS - 타겟 넘버[프로그래머스]
문제설명:n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 1, 1, 1, 1, 1로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.\-1+1+1+1+1 = 3\+1-1+1+1+1
8.[코테] BFS - 게임 맵 최단거리[프로그래머스]
문제: 출처: 프로그래머스 - 게임 맵 최단거리 >## 풀이: >## 코드:
9.[코테] 순열 - 줄 서는 방법[프로그래머스]
1번과 같이 풀이를 진행할 시 모든 순열을 모두 확인하며 진행하기에 시간 초과가 난다. 순열의 경우의 수는 n! (factorial:순열의 경우의 수)는 'n! = n × (n-1) × (n-2) ×....3 × 2 × 1'으로써 길이가 20이라면 다음과 같은 경우의
10.[코테] 탐색구현 - 삼각 달팽이[프로그래머스]
탐색의 순서를 구현할 수 있는지 묻는 문제다.제일 위부터 아래까지 문제에서 제시하는 순서대로 수를 채웠을 경우에 다른 특정한 규칙이 보이지 않는다. 다시 말해서 문제에서 제시하는 순서대로 수를 채워넣을 수 있는 구현을 할 수 있는지 묻는 문제다.문제에서의 그림과 같이
11.[코테] BFS - 안전영역[백준 / 2468]
BFS 넓이 우선탐색 문제다.물에 잠기지 않은 안정영역을 찾는 BFS 문제의 조건에서 높이 h에 따른 영역의 개수까지 구해야 하는 조건이 추가되었다. 안전영역의 높이는 1부터 주어지므로 높이는 안전영역 1이 잠기지 않는 구간인 0부터 시작해서 100사이의 높이를 1씩
12.[코테] BFS - 토마토[백준 / 7576]
BFS 넓이 우선탐색 문제다.1\. BFS는 큐 자료형을 쓰는 것이 일반적이므로 큐를 불러온다. 그리고 상하좌우 탐색을 위해 좌표를 생성하고, 문제에서 제시하는 대로 가로, 세로의 길이만큼의 토마토 창고를 2차원 배열을 만든다. 그리고 토마토 창고와 같은 크기의 토마토
13.[코테] DP(Knapsack) - 평범한 배낭[백준 / 12865]
DP(Dynamic Programming) Knapsack(냅색) 문제다.냅색 문제는 2개의 짝을 이루는 값이 주어지는데 '무게, 가치', '시간, 가치', '넓이, 가치' 등이다. 이렇게 짝을 이룬 값이 주어질 때 이 값이 중복으로 사용할 수 있느냐 없느냐로 풀이가
14.[코테] 수학 - 점프와 순간 이동[프로그래머스]
출처: 프로그래머스 - 점프와 순간 이동점프와 순간 이동0에서 출발하여 도착지점까지 최소한의 건전지를 사용하며 순간 이동으로 도착할 수 있는지 묻는 문제다.0에서 출발하는 것을 계산하게 되면 많은 경우의 수가 생기기에, 역으로 도착지점부터 반씩(나누기 2)를 하여 순간
15.[코테] 그래프(우선순위 큐) - 배달[프로그래머스]
일명 '그래프' 문제라고 불린다. 주어진 문제의 제시처럼 그래프를 만든 후 '1'번 노드부터 시작해서 다음 노드들을 방문할 때 가중치의 합이 K를 넘지않는 노드의 개수를 찾는 문제다.시작 노드가 1이기 때문에 1에서 출발을 할 수 있도록 하며, 연결이 되어 있지 않을
16.[코테] 스택/큐 - 기능개발[프로그래머스]
제일 앞 인덱스를 계속 확인하면서 진행해야 하기에 자료구조 큐를 활용한다.progresses 제일 앞 인덱스의 값을 확인하면서 100 이상이 되면 숫자를 세어주고, 아니면 progresses에 speeds값을 각 인덱스에 맞춰 한 번씩 더해준다. 제일 인덱스 0의 값을
17.[코테] 문자열 - 문자열 압축[프로그래머스]
문자를 압축할 때 문자를 1개 단위부터 문자열 전체의 반까지 압축할 수 있는 경우의 수를 모두 탐색하여 가장 짧은 문자열을 반환하면 된다.2중 반복문을 이용하여 문자길이 1부터 문자 전체길이의 반까지 바깥 반복문을 통해 문자의 길이를 정하고, 안쪽 반복문은 문자의 길이
18.[코테] 해쉬(Hash) - 할인 행사[프로그래머스]
자료구조 해쉬(딕셔너리)와 모듈 collections의 Counter을 활용하여 간단히 해결할 수 있다.Counter 참조해쉬 참조딕셔너리 자료구조를 하나 생성하여 정현이가 원하는 품목을 key로 수량을 value로 생성한다.discount 날짜는 정현이가 원하는 최소
19.[코테] DP - 멀리 뛰기[프로그래머스]
DP를 해결할 때 크게 Botton-up 방식과 Top-down 방식이 있다.해당 문제는 Top-Down으로 해결하기에는 1 혹은 2로만 움직이기에 2000까지는 너무 깊게 내려가야 하기에 재귀를 쓰게 된다면 시간 초과에 걸릴 확률이 높다. 2칸을 기준으로 잡더라도 깊
20.[코테] 탐색 - 피로도[프로그래머스]
주어진 던전들의 모든 순서들을 나열하는 경우의 수인 수열을 모두 구한 뒤, 수열을 처음부터 탐색하며 던전을 돌 수 있는 수를 세고 그 중 가장 큰 수를 반환하면 된다.던전의 순서는 임의로 입장가능하며 입장 순서에 따라서 클리어가 가능한 던전의 개수가 달라지기 때문에 모
21.[코테] 큐 - 스킬트리[프로그래머스]
skill_trees를 반복문으로 순회하면서 스킬트리를 하나씩 꺼내와서 skill과 비교한다.비교할 때는 deque를 사용하여 큐 자료구조를 만들어 제일 앞의 문자를 비교한다. 리스트는 순서가 있는 배열이기에 제일 앞의 것을 빼내게 되면 재정렬을 하는 연산을 하기에 상
22.[코테] 해쉬 - 영어 끝말잇기[프로그래머스]
끝말잇기 문제는 문제에서 제시하는 것을 그대로 구현할 수 있는지 묻는 구현 문제에 가깝다.해쉬의 set 자료구조가 아닌, 단순히 중복을 체크하는 것이기에 list 자료구조를 만들어서 확인해도 문제가 없지만 set 자료구조를 일단 사용했다.단어를 확인하면서 첫 글자와 마
23.[코테] BFS - 미로 탈출[프로그래머스]
BFS 최단거리 탐색 문제다.1\. 시작지점에서 출발하여 반드시 레버를 당긴 후에 탈출 지점으로 이동해야 한다. 그러므로 출발 -> 레버, 레버 -> 탈출 경로로 2번의 BFS를 시행하여 두 번의 이동 경로의 합을 구하면 된다.2\. 2번의 BFS를 시행할 때, BFS
24.[코테] 그리디(Greedy) - 구명보트[프로그래머스]
출처: 프로그래머스 - 구명보트주어진 people에서 1명 혹은 2명으로 묶어서 그 길이를 구할 수도 있지만,간단히 구명보트에 1명씩 태우는 경우를 default로 잡고 2명이 탈 수 있다면 전체 길이 default 값에서 -1씩 차감하여 구하여도 된다.그리디 문제는
25.[코테] 해쉬 - 귤 고르기[프로그래머스]
set 자료구조와 라이브러리 collections에서 defaultdict 혹은 Counter를 사용하면 쉽게 해결할 수 있는 해쉬 문제다.참조 : 자주 쓰는 라이브러리defaultdict 혹은 Counter를 사용하여 크기별로 갯수를 만든다. 크기의 종류가 최소가 되
26.[코테] 큐와 스택 - 택배상자[프로그래머스]
1번부터 증가하는 상자가 컨테이너에서 순서대로 흘러올 때, 'order'의 번호와 같을 때 트럭에 실으면 된다.순서가 같지 않으면 임시 컨테이너에 집어넣는데, 그 컨테이너는 스택과 같이 후입선출만 가능하다.그래서 일단 임시 컨테이너에 집어넣고, 제일 마지막에 집어넣은
27.[코테] 스택 - 짝지어 제거하기[프로그래머스]
s의 길이가 최대 1백만이기에 탐색을 위해 반복문을 2번 이상 반복하게 되면 시간초과가 된다. 1번의 탐색으로 result의 결과를 확인할 수 있어야 한다.연속으로 같은 문자가 2개 붙어 있을 때 제거를 해주는 방법으로 s를 순차적으로 반복문을 진행하면서 stack 자
28.[코테] 큐 - 프로세스[프로그래머스]
location은 priorities의 인덱스 번호다.즉 priorities 리스트가 주어질 때 가장 높은 순서대로 프로세스가 작동할 때, priorities의 인덱스인 location이 몇 번째로 작동하는지 반환하는 문제다.문제의 제시에서 priorities는 길이가