Problem Solving에 대한 기록입니다.
Problem Solving에 대한 기록입니다.
실버1 : 동적 계획법 문제이다. 생각 전형적인 dp 문제이다. 다만 이 문제는, 경로를 추적해야 한다는 점에서 조금 다르다. 경로를 추적하는 방법으로는 dp를 미리 구해놓고, 이것을 역으로 추적하여 구하는 방법이 가장 간단하다.
실버5 : 동적 계획법 문제이다. 생각 생각 보다 힘들게 푼 문제이다. n이 50000이고, 시간 제한이 0.5초이기 때문에 완전탐색으로 풀면 힘들 것이라 생각했다. 그래서 동적 계획법 방법으로 풀이를 채택했다. 이 문제는 동전 문제와 비슷하게 생각해야 한다.
골드4 : 이분 탐색 문제이다. 생각 어려웠다. 여러가지 배열이 섞이고, 계산하는 방법을 생각하지 못했다. 이 문제를 풀면서 배운 것은, 정말 컴퓨터처럼(센다..) 생각해야 된다는 것.
골드5 : 동적계획법 문제이다.
실버1 : 동적계획법 문제이다. 생각 동적 계획법하면 유명한 문제이다. 나는 동적 계획법을 풀 때 보통 두가지 방법을 많이 사용한다. 상태에 대한 정의와 점화식을 직관으로 때린다. (감..) 순차적으로 완전 탐색 방법으로 그려본다.
브론즈1 : 구현 문제이다. 풀이 단순한 문제이다. 앞뒤에 어떠한 문자를 넣을 수 있으니, 현재 가지고 있는 ROT13만 가지고서 부분적으로 보았을 때, 가장 작은 차이를 가지고 있는 지점만 알면된다. 이후는 맞춰서 끼워넣으면 되니까.
골드5 : 구현 문제이다.
실버2 : 동적 계획법 문제이다. 생각 dp의 정의는 간단하게 생각할 수 있다.
골드3 : 동적 계획법 문제이다. 생각 dp의 정의는 간단하게 생각할 수 있다. 이 문제는 가장 긴 감소하는 부분 수열, 가장 긴 증가하는 부분 수열을 합한 문제이다.
골드2 : 이분 탐색 문제이다. 생각 기존에 dp로 풀었던 문제가 데이터의 개수만 달라져 새로운 문제가 되었다. 이번 문제는 풀이를 좀 참고하였으며 새로운 공부를 할 수 있었다. 이 문제는 먼저, 일반적인 dp문제로 풀수가 없다.
골드4 : 동적 계획법 문제이다. 생각 전형적인 dp 문제이다. 다만 이 문제는, 경로를 추적해야 한다는 점에서 조금 다르다. 경로를 추적하는 방법으로는 dp를 미리 구해놓고, 이것을 역으로 추적하여 구하는 방법이 가장 간단하다.
실버2 : 동적계획법 문제이다.
실버2 : 동적계획법 문제이다. 풀이 그냥 합을 구하는 문제이다.
실버1 : DFS 문제이다. 풀이 DFS와 동적계획법이 섞인 문제이다. 일단, 특정 위치까지 갈 수 있는 모든 경우의 수를 구해야 하는데, 그냥 방문할 때마다 count를 늘려준다면, 중복해서 방문하는 곳이 너무 많아 비효율 적이다.
실버1 : 최단거리 문제이다. 생각 모든 경로에 대한 최단 거리를 구해야 한다. 가중치는 양수이자 동일 정점 개수 100개 모든 경로에 대해 최단 거리를 구해야 한다는 점에서 플루이드를 사용할 것이고, O(V^3) 알고리즘에도 통과한 노드 개수이므로 진행한다.
실버1 : 수학 문제이다. 생각 소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다. 이 때, 시간제한 때문에 구한 소수를 담아두는 것이 좋다.
실버2 : 파라메트릭 서치 문제이다. 생각 파라메트릭 서치 문제이다. 일단 완전 탐색이 불가하고, 답을 제시했을 때 분기를 만들 수 있다는 점에서 바로 접근했다. 인접한 집간의 최대 거리를 제시한다.
골드2 : 유니언 파인드 문제이다. 생각 이런 문제는 정말 비행기가 온다고 생각하고 푸는 것이 가장 좋은 것 같다. 그러니까 모든 문제는 시뮬레이션을 제대로 하는 것이 중요. 총 5개의 게이트가 있다고 하자. 그 때, 4번으로 비행기가 들어온다.
실버4 : 스택 문제이다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
플래티넘5 : 세그먼트 트리 문제이다. 생각 전형적인 세그먼트 트리 문제이다. 구간에 대한 합을 연속된 쿼리로 물어보는 경우인데, 이런 경우 단순하게 짜면 그냥 펑!이다.
실버1 : 이분 탐색, Parametric Search 문제이다. 생각 처음에 이 문제를 풀 때, 세그먼트 트리로 풀려고 했다. 그런데, 문제가 생겼다.
실버2 : BFS 문제이다.
골드4 : dp & DFS 문제이다. 풀이 이게. 접근 방식을 약간 반대로해서 오래걸렸다. 바텀 업 방식으로 사고를 하여, 마지막 지점까지 가는데 있어 4방향의 경로를 더해주어야 한다고 생각했다. 그런데 그렇게 생각을 하니 쉽게 점화식이 떠오르지 않았다.
실버4 : 메모이제이션 문제이다. 생각 고등학교 때 많이 풀어본 함수의 개수 구하는 문제와 같다. 결국은 공역단에서 N개의 site를 고르게 되면 자동으로 순서가 결정되기 때문이다.
실버1 : DFS 문제이다.
실버5 : 브루트포스 문제이다.
실버1 : 동적 계획법 문제이다. 생각 다이나믹의 유형 중 중요한 유형이다. 대부분의 동전 문제의 방식과 비슷하다. 1차원 다이나믹이지만 2개의 반복문을 통해 2차원 처럼 생각하는 것이 필요하다.
실버1 : 동적 계획법 문제이다. 생각 다이나믹의 유형 중 중요한 유형이다. 대부분의 동전 문제의 방식과 비슷하다. 1차원 다이나믹이지만 2개의 반복문을 통해 2차원 처럼 생각하는 것이 필요하다.
플레티넘1 : 동적 계획법, Convex Hull 문제이다. 생각 일단 완전 탐색을 생각해 본다. 음. 말도 안된다. 몇개를 겹쳐서 만드는지 완전탐색을 한다면 시간 복잡도가 O(n!) 이다. 이 문제는 그냥 직관적으로 동적 계획법 냄새가 난다.
실버3 : 이분 탐색 문제이다. 생각 이분 탐색 문제이다. 이전의 문제들과 마찬가지로, 값을 제시하고 그에 대한 분기를 만드는 것이 중요하다. 이 때, 어느 영역에서 답이 나오는지를 잘 체크하고, 답의 후보를 기록해두는 행위가 중요하다.
실버2 : 조합 문제이다. 풀이1 기본적인 조합 문제이다.
골드3 : 그래프 문제이다. 생각 현재 시작 위치에서 다음 쓰레기를 치우고, 그 위치에서 다시 다음 경로를 탐색하는 과정으로 문제를 풀려 했다. 하지만 코드를 짜면서도 탐색과정이 계속하여 중복되서 어떻게 풀어야 할지 고민을 많이했다.
실버4 : 그리디 문제이다. 풀이 단순한 문제이다. 앞뒤에 어떠한 문자를 넣을 수 있으니, 현재 가지고 있는 문자열만 가지고서 부분적으로 보았을 때, 가장 작은 차이를 가지고 있는 지점만 알면된다. 이후는 맞춰서 끼워넣으면 되니까.
골드1 : 동적 계획법 문제이다. 생각 dp의 정의는 간단하게 생각할 수 있다. 특정한 상태의 발전소로 오는 방법은 몇가지로 정해지기 때문이다. 그래서 정의를 잡으면 다음과 같다.
골드2 : 그리디, 정렬 문제이다. 생각 실제로 운송물을 움직인다고 생각해보자. 그렇다면 가장 무거운 하중을 움직일 수 있는 크레인이 가장 많이 움직여야 최단 시간에 짐을 움직일 수 있다. 이부분이 핵심이다.
실버1 : 구현 문제이다. 너무 짜증난다. 문제 제대로 읽어. 제발제발젭라. 뱀이 지나가는 경로를 잡아줄 자료구조 map에 표시해서 갈 수 있는지 없는지 알아야 한다. tail의 위치를 tracking할 수 있어야 한다.
실버2 : 수학 문제이다. 생각 소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.
골드4 : bfs 문제이다. 풀이 bfs는 가중치가 없는 그래프의 최단 거리 문제를 풀 때 사용하는 방법이다. 이 문제는 최단 거리 문제이므로 이 풀이를 선택하는 것은 맞다.
골드1 : 기하 문제이다. 생각 볼록 껍질, Convex Hull이라 한다. 이 알고리즘에서 유명한 것을 그라함 스캔 알고리즘인데, 해당 동영상을 봐보자. 이것과 같은 알고리즘을 구현하기 위해서는 다음과 같은 절차를 거쳐야 한다. 가장 y가 작은 점을 구한다.
실버1 : 그리디 문제이다. 풀이 처음에 부르트 포스로 접근했다가, 시간초과가 났다. 그래서 그리디로 방향을 전향했다. >가 나왔을 때, 가장 큰 숫자를 설정해두고, 이하 부터 순서대로 이숫자를 채우는 것으로 해당 조건을 만족시킬 수 있다.
브론즈2 : 브루트포스 문제이다.
골드4 : bfs 문제이다. 생각 단순한 구현 문제이다. 이 때, 순서를 잘 파악하는 것이 중요하다. 먼저, 불을 번지게 한 상태에서, 사람의 현재 위치로 부터 어디로 가는 것이 좋은지를 판단해야 한다.
브론즈2 : 브루트포스 문제이다.
골드4 : union find 문제이다. 풀이 기본적인 union find 문제. 코드를 기억하자.
실버2 : 동적계획법 문제이다. 풀이 기본적인 동적계획법 문제이다.
실버3 : 분할정복 문제이다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
골드3 : 완전탐색 문제이다. 삼성 A형 기출이다. 생각 시간이 1초라, 제한 시간에 들어올 수 있는지 시간 복잡도 계산부터 진행했다. 최악의 경우 100개의 공간에 모두 1이 차있는 경우 한 개의 공간에서 색종이를 5번 검사해야 한다.
실버2 : DFS 문제이다. 풀이 그냥 구현하라는 대로 탐색해서 answer를 늘려주면 된다.
골드5 : bfs 문제이다. 생각 최소 경로를 묻는 문제로써, 완전 탐색으로 풀이할 수 있다. 이 때, 중요한 점은, 한번의 스텝을 넘어감에 있어서 소수여야 한다는 것, 그리고 불가능하다는 것을 알려주기 위한 visited를 만드는 것이다.
실버2 : 수학 문제이다. 생각 소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.
실버4 : 수학 문제이다. 생각 소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.
실버1 : 수학 문제이다. 풀이 에라토스 테네스를 적용한 수를 가져오고, 이를 기반으로 상근수 로직을 적용하여 답을 계산한다. Code // // main.swift // CodingTest // // Created by 최완식 on 2021/08/15.
골드4 : 구현 문제이다. 상당히 갑갑했다. 일단 무한개의 소용돌이가 생길 수 있다는 점에서 기존의 달팽이 문제처럼 생각하면 안된다라는 판단이 들었다. 발생하는 모든 숫자를 저장한다면 메모리 초과가 날 것이 분명했기 때문이다.
실버5 : 정렬 문제이다. 생각 정렬 문제이다. merge sort(합병 정렬)을 구현해보고자 시도했다. 알고리즘 기본적인 병합 정렬의 알고리즘은 다음과 같다. 위키 백과 - 합병 정렬 좀 더 자세한 설명 partition 나누는 방법은 간단하다.
실버2 : two pointer 문제이다. 풀이 투포인터는 i이상 j미만으로 짠다. 같을 경우는 i를 늘려서 파악한다.
골드4 : 수학 문제이다. 생각 문제 이름 부터 뭔가 마음에 들지 않았다. 풀이 방법은 바로 떠올랐는데 왜 요즘 이런게 구현이 안되는지… score가 최대공약수를 구하는 것이기 때문에 소인수 분해를 떠올릴 수 있고, 그러기 위해서는 소수를 구해야 한다.
풀이1 실버1 : BFS 문제이다.
골드5 : BFS 문제이다.
골드5 : BFS 문제이다. 풀이 cost에 따라 탐색하지 않을 노드를 분명히 정해야 한다.
골드4 : BFS 문제이다. 풀이 아니 풀이방법을 아는데 왜 코드가 안돌아가는지 모르겠다. 계속해서 메모리 초과가 뜨는데 어떤 부분이 문제인지 아직도 못찾았다.
풀이1 실버4 : 이분 탐색 문제이다. 생각 특정 숫자가 등장하는 lowerBound와 UpperBound를 잡아내면 끝나는 문제이다.
실버1 : 동적계획법 문제이다.
실버3 : dfs 문제이다. 생각 기본적인 dfs 문제이다. 반으로 나눈 팀에 대한 점수를 더하는 것이므로, true false를 통해 구현할 수 있다.
실버3 : 정렬 문제이다. 생각 문제에서 하라는 대로 비교만 하면 된다.
실버2 : 동적계획법 문제이다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
실버1 : BFS 문제이다. 풀이 물의 높이를 존재하는 min값에서 max로 잡아줬었는데, 이렇게 하지않고 0부터 하니 통과했다. 국어문제인듯한데. 아무래도 비가 안오는 것부터 체크해주는게 보다 맞는 것 같긴하다.
골드4 : 완전 탐색 문제이다. 풀이 이게 전날에 급하게 짜다가 조건을 놓친 문제인데, 오늘의 첫문제로 도전해보았다. 난 BFS로 문제 풀이방향을 정했는데, 문제가 방문이 중복으로 일어난다는 것이다.
골드3 : 동적 계획법 문제이다. 생각 이 문제는, BOJ - 평범한 배낭(12865)과 매우 비슷하다. 한번 푸는 것이 좋다. 이 문제는 memory의 범위가 매우 크기 때문에, 이 것을 기준으로 로직을 짜면 메모리가 터진다.
골드4 : 유니온 파인드 문제이다. 생각 이 문제의 핵심은 갈 수 있는지 없는지를 판단하는 것이다. 처음에 그래프라고 생각하고 접근하니, dfs를 수행할 때 depth가 너무 깊어져 터질 것 같아 다른 방법으로 진행했다.
실버1 : 완전 탐색 문제이다. 풀이 그냥 가능성을 다 구한다. 그런데 시간 초과가 날수도 있다. 왜냐하면 +-*/가 중복될 수 있으니까 그래서 set으로 이런 중복을 제거한후 주르륵 계산해서 답.
실버2 : 완전 탐색 문제이다. 풀이 기존 것에 비해 연산자 개수가 늘어난 문제. 단순한 순열로 풀면 44P10의 연산 결과라 못푼다. 그냥 완전탐색으로 풀면되긴한데, 백준에서 pypy로 제출했더니 틀렸다고 해서 당황했다.
실버1 : DFS 문제이다. 풀이 기본적인 DFS 문제이다. DFS를 사용할 때는 dp적 사고를 기반으로 코드를 짜는 것이 좋다. 즉, 현재 상태는 다음 상태들의 연산으로 구해진다는 것.
실버5 : 브루트포스 문제이다. 풀이 String으로 변환해서 판단하려고 했는데, 생성시간이 꽤나 오래걸리나보다.
실버3 : 이진 탐색 문제이다. 풀이 예산 금액은 최대예산과 아예 안주는(0원) 방법이 있다. 따라서 0과 max금액을 양 끝으로 잡는다.
실버1: 동적 계획 법을 사용하는 문제이다. 대표적인 동적계획법 문제이다. 기초적인 동적 계획법 문제를 풀 때에는 펜을 갖고 쓰는 것이 중요해보인다. 기본적으로 점화식을 갖고 해결하는 방식이기 때문에, 수열 문제를 푸는 것도 같은 사고로 접근해야 한다.
골드1 : stack 문제이다. 생각 아, 어려웠다. 처음에 dp로 풀생각을 했더니, O(n^2) 이라 500,000인 input에 맞지 않는다. 또한 그 과정에서 세그먼트 트리 혹은 우선 순위 큐를 사용하려 했지만 구현 난이도가 올라가 고민했다.
골드4 : stack 문제이다. 풀이 아, 정말 아쉬운 문제였다. 하지만 배운 것이 있었다. Stack을 기본적으로 사용하는 이유은 어떤 복잡도 문제를 해결하기 위함이다. 이 부분은 뒤에 다시 살펴보도록 하자.
골드3 : dp? 문제이다. 풀이 음..풀이를 이상하게 했는지는 모르겠지만 일단 맞았다. 다른 사람들을 보니, 각각의 시작 위치에서 dfs를 돌려서 최대 거리를 구한뒤 max 를 취하는 방법을 사용한 것 같았다. 이렇게 풀었어도 될 걸 이상하게 풀었다.
실버1 : dfs를 사용하는 기초적인 문제이다. 이런 문제를 풀 때, 생각보다 실수를 많이하는 부분은, testcase가 있을 때, 초기화를 하지 않는 것이다. 항상 testcase가 있는 문제는, 이 부분을 유념해야 한다.
실버1 : 동적 계획법 문제이다. 생각 DFS나 BFS로는 depth가 깊어져 시간초과가 난다. 이 문제는 동적계획법으로 풀어야 한다. 그저 최대 사탕의 개수만 출력하면 되기 때문이다.
DFS graph 골드4 : 그래프 문제이다. 생각 이분 그래프란 무엇인가? 문제를 읽고는 파악하는 게 힘들었다. 차라리 그림으로 보는 것이 좋다. {:.center-text} 왼쪽과 같은 그래프가 있을 이걸 오른쪽 그림처럼 바꿀 수 있느냐의 문제이다.
실버3 : 동적계획법 문제이다. 생각 이 문제의 핵심은, 최고자리 숫자가 0 또는 1일 때의 상황을 분리해서 생각해보는 것이다. 이유는 나열하면 금방 알아차릴 수 있다.
골드3 : 최단 경로 문제이다. 풀이 이전에 풀었던 문제와 매우 비슷한데 음,.., 아 분명히 풀었다. 아마 프로그래머스 문제였던 것 같다. 연결되어 있는지 모두 파악하는 문제였다.
실버1 : 동적계획법 문제이다. max_element 최대한 쓰지 말자. 그리고 sizeof는 바이트수를 리턴해준다.
실버2 : 동적 계획법 문제이다. 생각 앞으로 보내는 dp문제이다. 정의 이 문제는 위치에 따라 개수가 결정되므로 dp의 인자를 좌표의 위치로 잡는 것이 수월하다.
실버2 : 파라메트릭 서치 문제이다. Root 찾기 처음에 또다시 해시로 풀려고 하다가, 중간에 입력값의 범위가 후덜덜한 것을 보고 풀이 방법을 바꾸었다. 이 문제를 그냥 linear하게 풀려고 하면 100000번을 linear하게 탐색해야 하기 때문에 터져버린다.
골드5 : 구현 문제이다. 풀이 문제 똑바로 읽자. 조건하나 안봐서 틀렸네.
골드4 : 유니온 파인드 문제이다. 생각 문제를 이해해보자. 먼저 처음에 아무일도 하지 않을 경우에 입력된 n에 대해서 0 ~ n까지의 바구니가 생긴다. 그 다음, m개의 명령이 들어온다.
실버2 : 순열 문제이다.
풀이1 실버5 : 브루트포스 문제이다. Code // // main.swift // CodingTest // // Created by 최완식 on 2021/08/15.
실버2 : 유니온파인드 문제이다. 풀이 유니온 파인드로 같은 집합인지 아닌지를 검증하고, 같은 집합이라면 촌수를 계산한다! 이 때 pypy로 하지말고 python3로 할 것.
플래티넘5 : 세그먼트 트리 문제이다. 생각 01234564175298 입력값이 이렇게 주어진다고 생각해보자. 이 상태에서 3~6까지의 최소값을 구하는 것은, 단순한 방법으로 구해도 O(n^2)으로 풀 수 있다.
플래티넘5 : 슬라이딩 윈도우 문제이다. 생각 N이 500만이라 세그먼트 트리로 풀면 터진다.
골드5 : 구현 문제이다. 풀이 컨디션이 안좋아서 그냥 풀었다.
골드2 : union find 문제이다. 풀이 으으 너무 아쉽다. 잘해놓고 같은 친구가 들어올 경우에 계산이 중복된다는 것을 체크하지 못했다. 그리고 지나고 보니 코드가 더러워서 다시짰다.
실버1 : 분할정복 문제이다. 처음에 너무 삽질했다. 그냥 구조적으로 부족한 것 같다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
골드1 : 구현, 시뮬레이션 문제이다.
골드5 : 스택 문제이다. 풀이 비슷한 문제를 한 3번 봤다. 근데 그 때는 heap을 사용해서 뒤에서 가장 큰 문자를 계속해서 뽑는 것으로 문제를 해결했다. 풍선 터트리기 그런 방식으로 해당 문제를 다시 풀려했으나, 밑에 알고리즘 분류를 봤는데 stack…이더라.
실버1 : 완전 탐색 문제이다. 풀이 매우 막 푼 풀이. 좋지 않다.
실버1 : 구현 문제이다. 생각 단순 구현 문제이다. 비트마스크 연습을 위해 비트마스크로 풀었다. 해당 과정을 하는 동안에 인접행렬 같은 matrix를 만들어 무언가를 해보려 했지만 좋지 못했다. 구현 문제는 노가다로 적어주는게 정신 건강에 이롭다.
실버4 : 정렬 생각 최빈값 구할 때, 머리를 좀 써야한다. map구조를 잘 써볼 것. 그리고 정렬하는 방법도 고민해볼 것. Code // // main.cpp // test2 // // Created by 최완식 on 2021/03/29.
골드2 : 트리, 유니온파인드 문제이다. Root 찾기 흠. 입력으로 들어오는 node들이 순차적이지 않다는 점을 알아야 한다.이거 때매 시간 엄청 날렸다 즉, 랜덤으로 들어오는 그래프 정보를 가지고, 어떤 녀석이 tree의 root가 될 것인지 알아내야 한다.
골드3 : dfs 문제이다. 풀이 트리 = 사이클이 없는 무방향 그래프. 어떠한 두 노드를 선택해도 경로는 하나이다. 즉 무조건 연결되어 있다. 쉽게 생각하기 위해서 이미 두 지름인 점을 알고 있다고 가정하자.
실버3 : 수학 문제이다. 생각 일단 코드가 처음보는 거라 유심히 보았다. 결국 이런 것을 묻는 문제였다. 가장 큰 약수가 뒤에서 부터 몇번째에 나오니? 그렇다면 가장 큰 약수를 구해야 하는데, 가장 큰 약수는 사실 \sqrt{n} 까지만 조사해도 풀 수 있다.
골드5 : 동적 계획법 문제이다. 생각 결국 무게 제약이 있는 문제이다. 나는 이 문제를 풀 때 감을 잡기 참어려웠는데, 무게에 제약이 있다는 점을 갖고 완전 탐색을 한다는 아이디어를 가지고 생각했다.
실버1 : 동적계획법 문제이다. 생각 dp[i] : i번째 포도주의 위치에서 마실 수 있는 최대 포도주 양 i번째 포도주의 포도주 양은 세가지 경로에서 답을 찾을 수 있다.
실버1 : 최단경로 문제이다.
실버3 : 동적 계획법을 사용하는 문제이다.
골드5 : 동적계획법 문제이다. 풀이 잘 접근했다고 생각했는데, 점화식을 잘 못 구했다.
실버1 : 분할 정복 문제이다. 생각 특정 행렬을 10번 곱하라는 의미는, 곧 이렇게 해석 된다.
실버5 : 해쉬 문제이다.
실버2 : 그래프 문제이다. 생각 아. 정말 쉽겠지 했는데, 되지도 않는 시간 복잡도 줄여보겠다고 확인 되지 않는 것 썼다가 하루 다 날린 문제이다. 문제는 상당히 간단하게 DFS로 풀 수 있다.
실버? : stack 문제이다. 풀이 처음에 op과 ()를 담는걸 별도로 생각했다가 낭패를 보았다. 생각하다보니 이 두개가 엮인다는 것을 알았고, 쉽게 규칙을 파악해서 풀 수 있었다.
level2 : 구현, 또는 동적 계획법을 사용하는 문제이다. 처음 풀이로는 빠르게 풀기 위해서 그냥 단순히 구현을 했다. 입력이 1000 x 1000 이라, 완전 탐색을 수행하더라도 로직을 최대한 덜 쓰도록 짜야된다는 생각을 하면서 짰다.
풀이 하라는 대로 구현했다. 이거 부캠 시험에서 나온것 같은 기분이.
level2 : SQL 사용 생각 간단하다. 예시를 보고 외우던가 나중에 찾아보자.
풀이 실패했다. 뭔가 감은 오는데 기존의 dp처럼 풀려고 하니 문제가 안잡히는 기분. 일단 접근 방법은 맞으니, 엑셀처럼 나열하면서 규칙을 찾는 것이 좋다.
풀이 문자열 정렬의 아이디어는 항상 갖고 있는게 좋을 것 같다. 약간 스킬 적인 측면으로 작용하는데(~~~이거 버그아닌데 스끼린데~~~) 음 일단 보자. 이 문제는 보면 특징이 있다. 일단 다 만드는 것은 잘못된 방법이다.
풀이 아. 시도를 총 세번했다. 해시맵으로 발생할 수 있는 모든 구간에서 시청하고 있는 사람을 저장 아이디어는 좋았으나, 실제 계산할 때 n^2을 피할 수 없음.
풀이 구현 문제라 풀만하긴 한데, 코드가 깔끔히 짠다그래도 아직 부족하다. 다시한번 꼭 짜보자. 리팩토링 연습이다.
풀이 트리 구현을 한번도 안해보다가 처음으로 했다. 첫 시도에서는 바로 구현을 못하고 다른 코드를 참고 했다. 반복적으로 연습하면서 체득을 해야 겠다.
풀이 정말 미쳐버리겠다. 왜 구현을 못하지. 왜 while문으로 구현을 못하는 걸까. 푸는 방법 다 알아놓고. 미쳐버리겠다.
풀이 시뮬레이션 문제이다. 시뮬레이션 문제는 순서를 명확하게 이해하고 이를 지켜주는 것이 매우 중요하다.
풀이 일단 DFS로 풀었다. 근데 풀이를 보니 다 BFS로 풀었더라. 그래서 다음날 다시 도전할 거다.
풀이 가장 최소인 녀석을 계속해서 뽑아야 하기 때문에 heap 구조를 사용했다. 이 때 python으로 코딩을 하려한다면 무조건적으로 heapq를 사용할 것. priorityQueue는 속도가 너무 느려서 효율성 통과를 하지 못한다.
풀이 deque, heap을 통해서 구할 생각을 했다. 그런데 구현을 하는 점에 있어서 어떠한 요소가 필요하겠다고 생각하는 능력이 좀 떨어진다. 몇개의 변수를 사용하면 쉽게 구할 수 있다와 같은 판단을 하는 것이 모자라다.
풀이 좀 어려울 수 있지만, 시간 초과가 나면 무언가 규칙이 있다는 생각을 해보자. 일단 찾을 수 있는 규칙은 다음과 같다. 최소공배수로 나눈 작은 모양이 반복되어 발생한다.
풀이 처음에는 각각의 order의 메뉴와 다음 메뉴와의 교집합을 사용해서 풀려고 했으나 문제는, 결국 몇번 시켰는지 알아내야 한다는 점에서 막혔다.
풀이 아니, 갑자기 딕셔너리 소트 안되는게 말이냐구. 왜 다 풀줄 아는데 꼭 저런거 때매 문제일까. 더 많이 풀어서 오류를 판단하는 눈을 길러야 한다. Code def solution(genres, plays): # 속한 노래가 많이 재생된 장르를 먼저 수록.
풀이 순열로 해결했다. n이 작아서 가능했다. 순열로 가능한 순서의 모든 banned를 나열하고, 각각에 대해 가능한지 확인하여 문제를 해결했다.
풀이 그냥 풀었다.
풀이 어떻게 해야 이런 문제를 풀 수 있을까. 일단 조합과 같은 생각은 n이 작을 때 한다. 완전 탐색 방법을 먼저 생각한다.
풀이 일단, 200,000이라서 n^2은 안된다. 그러면 한번에 가야하는데, 이 때, 잘 살펴보면, 해당 스테이지에서의 실패율은 stage잔존 수/stage 통과수로 정의된다.
level3 : join을 사용하는 문제이다. 생각 이 문제를 풀기 위해서는, join이라는 쿼리가 어떻게 돌아가는 지 알아야 한다. right join, left join등 다양한 join의 방법이 있지만, 일단 기본적으로 join을 하면 그냥 합쳐진다.
풀이 BFS로 풀었는데, 배열이 reference로 전달되어 애먹었다.
풀이 아무 생각 없이 재귀로 풀었다. 그냥 어느 위치에 있는지에 따라 값이 변하길래. 아마 최근에 정렬문제를 많이 푼 탓인가보다. 그래서 풀고나서 다른 분 코드를 보고 규칙을 나도 파악해 보기로 했다. 일단 사실 문제를 안읽었다.
level2 : limit을 사용하는 문제이다. 생각 가져온 table에 대해 제한을 걸어, 그 만큼의 행만 가져오게 하는 문제이다.
level3 : join을 사용하는 문제이다. 생각 이 문제를 풀기 위해서는, join이라는 쿼리가 어떻게 돌아가는 지 알아야 한다. right join, left join등 다양한 join의 방법이 있지만, 일단 기본적으로 join을 하면 그냥 합쳐진다.
level4 : table을 분리하는 방법을 사용해보자. 생각 문제가 잘 안풀리면, 제공해주는 table을 분리하고, 그 분리한 table로 부터 원하는 결과를 도출해보자. 즉 sub query를 사용해서 임의로 table을 만드는 것.
풀이 쉬워서 패스. 해시사용 문제이다.
풀이 일단 input보고 항상 판단하는 것이 중요하다. 방향만 잘 잡으면 어느정도 풀 수 있다. 이제. 이분 탐색의 핵심은 결국 값을 제안하고, 그 값이 맞는지 틀린지를 검증하는 로직을 찾을 수 있냐는 것이다.
level4 : 변수를 사용하는 문제이다. 생각 이 문제는 group by를 사용할 수 없다는 것이 핵심이다. group by 는 있는 값을 DISTINCT하게 판단하여 집합을 구성해주는 쿼리이다.
풀이1 이게 보면, 전화번호 개수가 백만개라 단순히 비교로 풀면 n^2이라 박살난다. 그렇기 떄문에 다른 방법을 고민해야한다. 이 문제의 핵심은 결국 특정 단어가 접두어로 있는지에 대한 문제이다. 그렇기 때문에 startswith를 생각하는 것이 편하다.
풀이 prices의 길이가 100,000이라 n^2으로 짜면 터질 것 같아 stack으로 구현했다. 그런데 이때, 특정 원소가 조사해야 하는 부분은 i+1부터 끝까지의 요소이다. 그 과정에서 중복이 발생하기 때문에 반대로 정렬한뒤 값을 구해주었다.
level2 : case when을 사용하는 문제이다. 생각 쿼리로 가져온 table에 대해서 추출을 진행할 때, 사용할 수 있는 테크닉이다. 이건 예제로 보는 것이 정확하다.
풀이 하라는 대로 구현했다. 일단, board에서는 빈칸을 찾아야 하고, table에서는 채워진 조각을 찾아야 한다. 각각에서 그 빈 구석을 모두 도려낸 뒤에, 그 조각들이 맞는지를 완전탐색했다.
level3 : join을 사용하는 문제이다. 생각 이 문제를 풀기 위해서는, join이라는 쿼리가 어떻게 돌아가는 지 알아야 한다. right join, left join등 다양한 join의 방법이 있지만, 일단 기본적으로 join을 하면 그냥 합쳐진다.
풀이 그냥 막 풀었다. 컨디션이 좋지 않다.
풀이 다익스트라로 한번에 성공했다. 그래도 발전이 있나보네. 스위프트로 플루이드 워셜로 다시 풀었다. Code # AB가 함께 모든 노드까지 가는데 걸리는 최단 거리를 구한다. # 그리고 그 거리 각각에서 출발하여 # 1.
풀이 그냥 막 풀었다. 컨디션이 좋지 않다. 이전에 풀었던게 더 깔끔하더라. 그리고 같은 부분에서 틀렸다. 멍청해.