PS

계단 오르기img계단은 연속해서 세 칸은 오를 수 없고 한 칸이나 두 칸을 오를 수 있다. 따라서 현재 칸에 도달하는 경우는 2칸 이전에서 오거나 한칸 이전에서 온 경우인데 이때 한칸, 한칸, 한칸은 불가능하므로 필히 두칸, 한칸, 한칸으로 이동해야 한다. 이를 통해

문제 코드 접근

오르막 수img이 문제를 보고 나름 자연스럽게 dp로 풀어야겠다고 생각이 들었다. 이전 단계에서 오르막의 규칙이 지켜진다면 앞으로도 지켜질 것이기 때문에 이전 값을 이용할 수 있기 때문이다. 그래서 dp 배열을 사용하였다.만약 마지막 자리가 0이라면 이때 고려해야 하는

트리 순회img이 문제는 left, right child를 나눠서 저장한 것이 핵심이었다. 전위, 중위, 후위 순회를 재귀로 구현하는 것은 큰 문제가 아니었고 오히려 이를 어떻게 저장해서 재귀함수에서 활용할 것인가가 문제였는데 unordered_map을 통해 해결할 수

사회망 서비스img노드마다 유지하는 상태를 0과 1로 구분하였다.만약 현재 노드가 일반인인 경우 모든 자식 노드들이 얼리 어답터야 하므로 자식들의 값을 더해주면 된다. 하지만 현재 노드가 얼리 어답터인 경우 자식노드가 일반인(얼리 어답터)일 때가 최적해라는 것을 보장하

촌수계산img부모-자식 관계이기 때문에 트리 관계라고 생각할 수 있다. 또한 이 트리 안에서 특정 노드를 찾기 위해 아래로, 위로 모두 이동할 수 있어야 한다. 따라서 양방향 연결로 저장하였다. 이를 가지고 재귀함수를 통해 촌수 찾을 다른 하나의 번호를 찾아 나섰고 방

토마토img먼저 익은 토마토가 어디에 있는지 확인하는 것이 중요하다. 이를 위해서 전체를 순회해서 찾을 것인지, 익은 토마토만 따로 관리해 살펴볼 것인지가 시간초과를 나누는 부분인 것 같다. 따라서 큐에 익은 토마토만 넣어서 관리하면서 익어가는 날짜를 저장하고 큐가 빌

최소공배수img최소공배수를 구하기 위해서 최대공약수 gcd를 먼저 구하였다. 이는 유클리드 호제법을 이용하여 재귀함수를 통해 구할 수 있었다. 또한 최대공약수를 아는 상태에서는 최소공배수 lcm는 a\*b/gcd(a,b) 와 같기 때문에 쉽게 구할 수 있었다.https

떡 먹는 호랑이img첫째날의 떡 개수를 a, 둘째날의 떡 개수를 b라고 생각하였다. 이를 바탕으로 각 날짜 별로 주게 되는 떡의 개수를 계산한다면 m\*a + n\*b개가 된다. 따라서 우리가 D일차 떡의 개수를 통해 a, b에 들어갈 수 있는 값을 알기 위해서는 각각

트리와 쿼리img각 노드를 기준으로 그 노드를 루트로 하는 서브 트리에 속한 노드의 개수가 몇 개인지 저장하려고 했다. 이를 위해 주어진 루트노드를 기준으로 dfs를 수행하였고 이때 부모 노드는 개수에 들어가지 않게 하기 위해 visited 배열을 사용하였다. 방향성이

동전 oimg이 문제는 동전의 개수가 무한대이기 때문에 현재 사용할 수 있는 금액의 최대 개수를 사용하면 된다. 따라서 금액을 역순으로 살펴보면서 현재 남은 K보다 작은 경우에 한해 개수를 세고 금액을 감소시키면서 답을 찾으면 된다.

유기농 배추img배추가 있는 부분에 벌레가 최소 하나씩 있으면 된다. 따라서 인접하게 위치하는 배추 군락(?)을 찾아주면 된다. 이를 위해 dfs 탐색을 했다. 방문했던 배추 위치는 다시 방문하지 않기 위해 visited 배열을 사용했고 한 군락을 발견할 때마다 개수를

토마토img1img2기존에 풀었던 토마토 문제에서 한 차원이 늘어난 형태이다. 따라서 인접한 4개의 위치만 살피던 이전 문제와 다르게 위, 아래도 살펴야하는 부분이 달라졌다. 이전 문제를 풀었다면 충분히 풀만한 문제였다고 생각한다.

호석이 두 마리 치킨img일단 N의 최대 값이 100 이고 특정 도시를 거쳐 다른 도시로 이동할 때의 최소 값을 구해야 하기 때문에 플로이드-와샬 알고리즘이 떠올랐다. 결과적으로 답은 배열의 맨 앞에 위치하게 된다.

Coinsimg사실 동전 문제의 경우 어느 정도 정형화 된 것 같다.금액 0의 경우 1가지의 경우의 수이므로 arr0 = 1로 초기화를 해주었다. 현재 금액을 기존 금액에서 특정 동전을 추가로 사용했을 때 만들 수 있는지, 그 가짓수를 세주면 되기 때문에 모든 동전에

트리의 부모 찾기img한 노드의 인접한 노드는 자식이거나 부모일 것이다. 트리의 루트는 1로 정해져 있으니 루트부터 bfs탐색을 하면서 나오게 되는 노드들은 현재 노드의 자식일 것이다. 이를 up에 저장하여 노드의 부모를 가리키게 하였다.

가장 긴 감소하는 부분 수열img먼저 dp의 값을 1로 초기화 하고 이전 값들을 살펴보면서 값을 갱신시켜 주었다. 현재 값을 이전 감소 수열에 이을 수 있는지 확인하기 위해 두 값을 비교하고 dp 값을 dpi와 dpj+1 을 비교해서 갱신해준다. 중간에 위치한 값이

현수막img굉장히 전형적인 dfs문제였다고 느꼈다. 다른 점이 있다면 상하좌우 뿐 아니라 대각선까지 총 8방향을 살펴야 했던 점이다. 살펴보면서 dfs로 살핀 영역의 개수를 카운트하면 글자 수가 나오게 된다.

공통 부분 문자열img이 문제는 전형적인 LCS(Longest Common substring) 이다. 진행 과정은 다음과 같다.현재 두 문자가 같을때 두 문자의 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만

스티커img한 스티커를 사용하게 되면 주변 상하좌우의 스티커를 사용하지 못한다는 조건을 더 생각할 필요가 있었다. 2행 n열로 구성되기 때문에 아래와 같은 선택지들만 존재하는 것을 알 수 있다. img2살펴보게 되면 1열의 원소들은 둘 중 하나 반드시 선택하게 되고 이

이진 검색 트리img전위 순회는 루트노드, 왼쪽, 오른쪽으로 순회하는 방식이고, 후위 순회는 왼쪽, 오른쪽, 루트 노드로 순회하는 방식이다. 따라서 전위 순서의 첫번째 원소는 루트 노드인 것을 알 수 있고 BST이기 때문에 왼쪽에는 루트보다 작은 값들만 나오는 것도 알

트리의 지름지름을 구하기 위해서 한 노드에서 리프노드까지 도달하는 값의 합을 모두 살펴보았는데 이런 경우 시간초과가 발생하였다. 그래서 이 문제는 다른 분이 정리한 것을 참고하였다. 트리의 지름을 구하는 문제는 풀이법이 알려진 문제라고 한다. 이 풀이법을 근간으로 코드

트리의 지름img이전에 풀었던 트리의 지름 문제와 유사해서 다시 풀었다. 입력의 형태만 다르고문제 접근이나 코드는 비슷하다.

트리의 순회img솔직히 처음 접하자마자 풀기에 쉽지 않은 문제다. 이전에 리트코드에서 풀었던 기억이 있어 접근하는데 유리했다. 중위, 후위순회의 값을 알고 있기 때문에 우리는 어떤 노드가 루트 노드인지 알 수 있고 중위순회 값과 비교해 왼쪽, 오른쪽을 구별할 수가 있다

숨박꼭질 4img위치를 찾게되는 가장 빠른 시점을 알아야 하기 때문에 bfs를 선택했다. 고민했던 부분은 bfs이지만 지나온 경로를 알아야하기 때문에 이를 어떻게 처리할지 였다. bfs탐색의 경우 이미 방문한 곳은 다시 가지 않아도 되고 때문에 왔던 곳들을 역추적할 수

N-Queenimg퀸을 놓는 문제는 잘 알려져 있는 것에 비해 처음 풀어보았다. 먼저 든 생각은 먼저 놓은 퀸을 조건에 맞게 놓을 수 있다면 마지막으로 퀸을 두었을 때 그 방법의 수들을 증가시키면 되지 않을까 였다. 이를 위해 해당 열에 위치한 퀸의 행을 표시하는 1차

문자열 폭발img문자열을 첫 원소부터 살펴보면서 answer라는 정답 문자열에 추가한다. 이때 스택처럼 폭탄의 맨 뒤와 answer의 맨 뒤를 비교하면서 같을 경우 answer의 맨 뒤가 폭탄인지 확인한다. 폭탄일 경우 answer에서 pop 해주면 된다. 이때 간단하

피보나치 수 3img문제 해결을 위해 피사노 주기를 이용하였다. 간단하게 말하자면 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것이다. 즉 나머지의 주기를 알 수 있다면 실제 값을 구하여 나누어 값을 계산하지 않고도 원하는 결과를 구할 수 있는 것이다. 따라서

피보나치 수 6img이 문제는 피보나치 수 3와는 다르게 피사노 주기를 이용할 수 없다. 이유는 한 번의 주기까지 구할수가 없기 때문이다. 정수론을 도입해서 구한다면 주기가 2,000,000,016이라고 한다. 이 크기의 배열을 선언할 수도 없고, 반복문으로 돌기에 시

거짓말img알고리즘 문제를 풀면서 union-find 문제는 거의 풀어보지 않았던 터라 풀이의 도움을 받았다. 아래와 같은 과정을 통해 해결하였다. 기본적으로 union-find를 접해보았다면 나름 어렵지 않게 해결할 수 있는 문제 같았다.참고https://9

가장 긴 바이토닉 부분 수열img문제에서 바이토닉 수열의 정의와 예시를 보고 일정하게 증가하거나, 감소하거나, 증가하다가 한번만 감소하는 형태를 이루는 것을 알 수 있었다. 이 부분에서 첫 번째 인덱스와 마지막 인덱스를 기준으로 증가하는 수열의 길이를 저장하고 이를 더

175\. Combine Two Tablesimgaddresss 테이블과 person 테이블을 left join해서 결과를 내었다. 주소가 없는 person의 레코드는 자연스럽게 null이 들어가게 된다.

DATETIME에서 DATE로 형 변환https://programmers.co.kr/learn/courses/30/lessons/59414DATE_FORMAT(DATE, 형식)을 통해 DATE의 형식을 바꿀 수 있다.형식에는 %Y(4자리 연도), %y(2자리

중성화 여부 파악하기https://programmers.co.kr/learn/courses/30/lessons/59409case ~ when ~ then ~ else end 을 사용해야 했다. case 구문은 삼항연산자와 비슷하다. when절에 조건을 넣고 t

있었는데요 없었습니다https://programmers.co.kr/learn/courses/30/lessons/59043

루시와 엘라 찾기 https://programmers.co.kr/learn/courses/30/lessons/59046in 을 사용하면 여러 값을 지정하여 검색할 수 있다.

이름에 el이 들어가는 동물 찾기https://programmers.co.kr/learn/courses/30/lessons/59047특정 문자가 포함되어 있는지 확인하는 것이 필요했는데 이때 LIKE 키워드를 사용했다. %가 붙는 쪽에 다른 값들이 더 들어올

오랜 기간 보호한 동물(2)https://programmers.co.kr/learn/courses/30/lessons/59411DATE 타입 끼리는 기본적인 연산이 가능하므로 ORDER BY 절에서 보시면 B.DATETIME-A.DATETIME을 한 뒤 그 값

오랜 기간 보호한 동물(1)https://programmers.co.kr/learn/courses/30/lessons/59044left join과 where절의 조건으로 ins에는 있지만 outs에는 없는 행들을 찾아내고 들어온 순서로 세 개의 행만 뽑아내었다

보호소에서 중성화한 동물1번2번두 개의 코드이지만 결국 아이디어는 같다. 들어올 때와 나갈 때의 성별이 다르기 때문에 같은지 다른지 비교해서 판단(2번 코드)하거나 직접 확인하는 방법(1번 코드)로 풀어보았다.

우유와 요거트가 담긴 장바구니img우유와 요거트를 가진 각각의 테이블을 뽑아내고 이들을 join 했다. cart_id로 정렬을 안해도 정답처리가 되서 굳이 쓰지는 않았다.

35\. Search Insert Positionimg입력이 정렬된 배열이고 시간 복잡도 O(log N) 으로 해결하라고 해서 자연스럽게 이진탐색이 떠올랐다. 기본적으로 이진탐색을 따르면서 target이 있는지 찾고, 있다면 그 인덱스를 반환한다. 없다면 들어갈 곳을

797\. All Paths From Source to Targetimg기본적으로 그래프라고 생각해서 dfs로 풀릴 것 같다는 생각이 들었다. 0 ~ n-1까지 가는 것이기 때문에 먼저 0번은 방문처리해주고 dfs를 시작했다. n-1 까지 도달한다면 경로를 answer

238\. Product of Array Except Selfimg자기 자신을 제외한 모든 원소들의 곱을 구해야 하기 때문에 누적 곱을 유지해야할 것 같았다. 따라서 자기 이전까지의 곱을 유지하는 left라는 벡터를 유지했다. 이후 역순으로 살펴보면서 자기 오른쪽 값들

721\. Accounts Mergeimg같은 이메일을 사용할 경우 두 계정이 같은 사람에게 속하기 때문에 모든 메일들을 살펴보면서 메일 간의 관계를 확인해주었다. 이를 기반으로 같은 메일들을 dfs로 찾아서 추가해 줄 수 있었고 set을 이용해서 이미 확인한 메일도

85\. Maximal Rectangleimg2차원 배열이 주어지지만 이를 row마다 하나의 히스토그램으로 볼 수 있다. row가 증가하는 방향으로 값을 0 혹은 누적하다 보면 히스토그램의 높이와 같아지게 된다. 따라서 한 줄을 기준으로 최대 넓이를 구하다 보면 전체

84\. Largest Rectangle in Histogramimg원소들을 하나씩 살펴보면서 스택에 원소들을 집어넣는데 조건은 스택이 비어있거나 현재 보는 원소가 가장 최근에 들어간 원소보다 큰 경우이다. 반대로 말하면, 현재 원소가 더 작다면 스택에 들어갈 수 없고

198\. House Robberimg서로 이웃한 집은 털 수가 없기 때문에 현재 방문한 집을 털 것인지 안털 것인지에 대한 구분이 필요하다고 생각했다. 그래서 i번째 집을 털기 위해서 실제로 include에 더해주고 다음 집으로 이동하면서 include 와 not_i

328\. Odd Even Linked Listimg홀수, 짝수 인덱스의 노드들을 연결시키고 마지막에 홀수 묶음 뒤에 짝수 묶음을 이어야겠다고 생각했다. 이를 위해서 temp 변수를 추가사용하였고 while 문에서 두 칸씩 넘어가면서 연결하였다. 기본적으로 ~->nex

181\. Employees Earning More Than Their Managers img한 테이블 안에 직원과 매니저 정보가 모두 존재해서 join을 해야겠다고 생각했다. join은 직원의 managerId와 매니저의 id가 동일한지를 기준으로 진행하였고 그 중

182\. Duplicate Emailsimg중복된 아이디를 찾는 것이다 보니 아이디 별로 모아서 개수를 확인할 수 있으면 되지 않을까 생각했다. 따라서 group by로 email을 모아서 개수를 count하기 위해 having 절을 사용하였다.GROUP BY와 DI

152\. Maximum Product Subarrayimg배열에 들어있는 값이 음수도 있고 최대 값이 음수가 없으리란 보장이 없다. 따라서 현재 보는 원소가 음수인지 양수인지 나누어야한다고 생각했다. 또한 음수가 나온 경우 최소 값과 곱하여 최대가 될 수 있기 때문에

337\. House Robber IIIimg먼저 트리를 사용하고 순회해야하기 때문에 dfs를 떠올렸다. dfs의 반환 값으로는 크기가 2인 벡터를 가진다. 0번째에는 현재 node를 털었을 때의 최대 값, 1번째에는 털지 않았을 때의 최대 값을 가진다. 따라서 0번째

1217\. Minimum Cost to Move Chips to The Same Positionimg2칸을 움직일 때는 cost가 0, 1칸을 움직일 때는 cost가 1이다. 따라서 홀수칸 끼리, 짝수칸 끼리 움직임은 cost에 영향을 주지 않는다. 결과적으로 한 곳

183\. Customers Who Never Orderimg단순히 주문 테이블의 customerId가 고객 테이블의 id에 존재하지 않는다면 이는 주문하지 않은 것을 의미하므로 서브쿼리와 not in 을 이용해서 처리했다.

1290\. Convert Binary Number in a Linked List to Integerimg전체 연결리스트를 살펴보지 않는 이상 2진수를 알 수 없다. 따라서 연결리스트를 다 살펴보면서 2진수를 알아내고 이를 다시 10진수로 바꾸는 과정이 필요하다고 생각

197\. Rising Temperatureimg날짜가 하루 차이나는 것을 구하는 것이 가장 큰 문제였다. 검색해보니 datediff()라는 것이 있어서 이를 사용했다. 날짜가 하루 차이나면서 온도가 높은 것을 조건으로 join을 진행했다.

627\. Swap Salaryimg현재 있는 테이블의 특정 컬럼 값만 바꾸는 문제였다. 따라서 update를 해야할 것 같다고 생각했고 조건을 걸 수 있는 방법을 찾아보았다. 첫 번째 코드처럼 삼항연산처럼 해결할 수도 있고 두 번째 코드처럼 when을 사용할 수도 있

563\. Binary Tree Tiltimg현재 노드의 left, right 자식들의 각 합을 알 필요가 있기 때문에 bottom-up 방식으로 해결해야겠다고 생각했다. 따라서 현재 노드의 부모가 알 수 있도록 left+right+node->val을 반환 하였고 그

1306\. Jump Game IIIimg한 index에서 움직일 수 있는 위치가 두 개이고 가능한 최소의 경로가 아닌 가능한지에 대한 문제이기 때문에 모든 경우를 살펴보는 것이 좋다고 생각했다. 따라서 재귀로 탐색을 했고 살피려는 인덱스가 배열을 넘어갈 수 있기 때문

416\. Partition Equal Subset Sumimg먼저 두 subset의 합이 동일해야 하기 때문에 총합이 짝수여야 한다는 점을 떠올렸다. 또한 해당 원소를 가지는 경우와 아닌 경우 모두를 살펴보면 답이 나오겠거니 생각했고 실제로 답은 구할 수 있었다. 하

문제 310. Minimum Height Trees img 코드 접근 MHT의 루트를 찾는다는 것은 결국 가장 긴 길이의 경로의 중간 노드를 찾는 것과 마찬가지다. 이를 찾기 위해 직접 만들면서 찾는 것이 아닌 간선이 하나밖에 없는 leaf node들을 제거해

221\. Maximal Squareimg먼저 단순하게 생각했다. 실제로 matrix를 순회하면서 1인 칸에서 한 변의 길이가 1,2,3 ... 이 될 수 있는지 확인하는 것이다. 금방 알 수 있겠지만 이 방법은 답은 구할 수 있지만 굉장히 시간이 많이 걸리게 된다.

문제 1010. Pairs of Songs With Total Durations Divisible by 60 img 코드 접근

1009\. Complement of Base 10 Integerimg단순하게 직접 2진수로 바꾸고 이를 다시 10진수로 바꾸는 과정을 구현하였다. 어려움은 딱히 없었지만 디스커션에서 발견한 두번째 코드가 신박하여 가져와 보았다. 구현한 것처럼 직접 2진수를 compl

131\. Palindrome Partitioningimg먼저 주어진 문자열이 palindrome인지 아닌지 판단해야하기 때문에 이를 판단하는 메소드를 작성했다. 전체적인 접근은 문자열과 현재 substring들을 모아둔 배열을 유지하다가 해당 문자열이 빈 문자열인 경

1022\. Sum of Root To Leaf Binary Numbersimg루트 노드부터 리프 노드까지 가서야 어떤 이진수 인지 확인할 수가 있다. 따라서 리프 노드에 도달 했을 때의 값을 반환해야 한다고 생각했고 이에 따라 그때까지 값을 유지해야 한다고 생각했다.

문제 1094. Car Pooling img 코드 접근 trips의 값을 기준으로 from과 to의 위치에서 각각 승객의 수를 더하고 빼주었다. 후에 값을 저장한 벡터를 앞에서부터 순차적으로 살펴보게 되면 어느 순간 capacity이상의 승객이 타있는 경우를

647\. Palindromic Substringsimg오랜만에 문제를 푸는 것이라 이전에 풀었던 것을 python으로 다시 풀어보게 되었다. 접근 자체는 brute force 하게 접근하면 되겠다는 생각이 들었고 이를 위해 dfs를 이용하였다. palindrome이라