what ryan do

코드만 궁금한 분은 링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 전에 다익스트라 알고리즘을 접해본 적이 있어서, 딱 보자마자 다익스트라구나..햇던 문제이다. 내가 처음 코딩테스트를 준비하면서 샀던 책이 파이썬 알고리즘 인터뷰인데 해당 문제는 41번에 있다. 별개의 이야기이긴 하지만 정말 추천하는 책이기 때문에 코딩테스트를 처음 준비하는 사람들에게 추천한다. 깃허브에 코드가 올라와있어서 해볼 수도 있다. GitHub - onlybooks/algorithm-interview: 95가지 알고리즘 문제 풀이로 완성하는 95가지 알고리즘..

코드만 궁금한 분은 깃허브링크 사실 내가 dp를 잘 하는 편은 아닌데 2293번 어제 푼거를 머릿속에 생각해보면서 푸니까 그래도 다소 어렵지 않게 풀 수 있었다. 문제를 대충 알려주자면, 1, 2, 5 이런식으로 무작위의 숫자들과 다른 숫자 임의의 숫자 하나가(예시를 들기 위해 10으로 한다.) 주어진다. 이 때 앞쪽에 주어진 숫자 1, 2, 5들을 이용해 10을 구성하는데 그 때 가장 적은 수로 숫자들을 이용하는 경우를 반환하면 된다. 말이 좀 이상한데, 간단히 얘기해서 10은 1을 10번 써도 되지만 5를 2번 써도 된다. 그럼 2가 더 작으니까 답은 2가 된다. 문제 풀기 1. 구성해야 하는 숫자 N의 길이만큼의 리스트를 미리 만든다. 2. 앞에 무작위로 주어졌던 숫자들 중 작은 수부터 활용해서, ..

코드만 궁금한 분은 깃허브링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 이해는 쉽다. 10이 있고, 1원 2원 5원짜리 동전이 있으면 그 동전들을 막 조합해서 10을 만들면 되는데, 그렇게 10이 되는 주어진 동전들의 조합의 총 갯수를 반환하면 된다. 간단한 다이나믹 프로그래밍이다. 1부터 10까지 가능한 동전의 조합 수를 dp라고 하자. 우선 위에 내가 서술한 문제로 보면, dp[10]은 dp[9] + dp[8] + dp[5]이다. 왜냐면, 9까지 만든 다음 거기에 1원짜리 동전 하나를 더하고, 8까지 만든다음 거기에 2원..

코드만 궁금한 분은 링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 : 숫자들이 든 격자가 주어진다. 이 때 인접한 요소 두개를 아무거나 바꿀 수 있는데, 이 때 전체 격자에서 일직선으로 인접한 요소들의 숫자가 같은 경우...의 가장 긴 길이를 구하면 된다. 일단 내 풀이는 대충 dfs를 활용한 완전탐색이다. 1. For문으로 각 요소마다, 왼쪽 위 오른쪽 아래 각 방향으로 탐색을 하는데 2. 다음 요소의 값이 현재값(시작값)과 같은 경우 계속 탐색을 한다. 3. 이 때 만약 어떤 값이 시작값과 다르고, 아직 한번도 인접요소와..

코드만 궁금한 분은 링크를 눌러주세용 간선과 정점이 몇개씩 주어지는데 이 때 각 간선에는 가중치가 있다. 이 정점들과 간선들로 트리를 구성할 건데 이 때 간선들의 가중치의 합이 최소인 경우의 트리의 가중치의 합을 반환하면 되는 문제이다. 전에 풀었던 유형이라 나는 그렇게 어렵지 않게 풀긴 했다. 트리이므로 사이클은 만들면 안되고, 아무 정점에서나 시작해서 매번 가장 작은 가중치를 갖는 간선을 선택하는 식으로 모든 정점을 방문하면 된다. 이 때 우연히 더 큰 가중치를 갖는 간선을 택하면 어떻게 되느냐 라고 물을 수도 있지만, 어떤 정점을 방문할 때에는 이전 정점에 연결된 모든 간선을 다 스택에 넣고 힙을 통해서 가중치가 작은 순서로 간선을 빼가는 방식으로 다른 정점을 방문하기 때문에 만약 어떤 정점을 방문..

코드만 궁금한 분은 링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 임의의 숫자가 하나 주어진다. 이 숫자를 임의의 자연수들의 합으로 나타낼 때 각각 다른 최대 몇개의 자연수들의 합으로 이 수를 나타낼 수 있을까? 어..어..어떻게풀지..! 라는 생각을 처음에 잠깐 할지 모르지만 조금만 생각해보면 쉬운 문제이다. 3을 생각해보자. 1+2 이렇게 두개로 나타낼 수 있다. 5를 생각해보자. 2+3으로 나타낼 수 있다. 이는 1+2+3에서 앞의 1을 뺀 값이다. 8을 생각해보자. 1+2+3+4는 10이라, 2가 더 크다. 그럼 여기에서 ..

코드만 궁금한 분은 링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 숫자로 이루어진 리스트가 주어지고 임의의 숫자가 주어진다. 그 리스트 안에서 연속된 숫자들의 합으로 임의의 숫자와 같거나 큰 수를 만들 수 있는데 그 연속된 숫자열들 중 가장 길이가 짧은 것의 길이를 반환해야 한다. 문제 풀이 전형적인 투포인터문제이다. 1. 리스트의 왼쪽 끝 부분과 오른쪽 끝 부분을 가리키는 포인터를 만든다. 2. for문이나 while문을 사용해서 왼쪽끝~오른쪽끝까지의 합을 계산한다. 3. 계산된 값이 조건으로 주어진 값보다 크면 길이..

코드만 궁금한 분은 링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제는 간단하다. N크기의 리스트가 있고 거기에 주어진 순서대로 숫자들을 넣으면 된다. 당연히, 이 때 이미 리스트 안에 있는 숫자는 순번을 pass하면 되고 그렇지 않은 경우는 안쪽의 수를 꺼내고 지금의 숫자를 리스트 안에 넣어야 한다. 문제에서 요구하는 답은, 이 때 리스트 안의 수를 제거하는 횟수의 최솟값이다. 이 때 최소한으로 리스트 안의 값을 제거하려면 다음과 같은 로직이 필요하다. 1. 이후에 다시 등장하지 않는 수를 제거하는게 최선 2. 가장 멀리 떨어..

코드만 궁금한 분은 링크 대충 문제 읽고 간단한 스택문제일 줄 알았는데 결코 그렇지 않았다. ((()))[][] 이런식으로 괄호가 입력되면 ()는 2점, []는 3점을 더하고 만약 중복된 괄호가 있을 경우 값을 곱하면 된다. 따라서 여기에는, 일반 괄호 문제처럼 (, [인 경우에는 스택에 넣고 ), ] 인 경우에는 스택에서 빼는 것에서 추가해 - 아직 남은 괄호가 있는지에 따라 계산 방식이 달라지는 경우를 추가해야한다. 사실 그냥 스택이 뭔지 알면 무조건 스택문제구나- 하고 누구나 알 수 있는 문제이고, 그 이후는 그냥 구현문제라 딱히 쓸 말이 별로 없다. 나도 한시간 반정도 미묘한..조건설정에서 헤매다 아래 블로그의 풀이를 참고해서 다시 풀었다. 코드를 보면 알겠지만 아래와 거의 같은데 다만 나는 (랑..

코드만 궁금한 분은 링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명은 스킵하고.. 문제를 풀 수 있는 두가지 방법이 있다. 첫번째는 dfs이다. 모든 문자열의 조합을 다 확인해봐야하기때문에 dfs로 그걸 구현하면서.. k개만큼의 조합을 만들었을때마다 - 입력받은 문자열 중 k개 조합만으로 구성이 되는지 확인해서 가장 많은 조합일 때의 갯수를 저장한다. 그리고 이 때 숫자조합에 맞춰 알파벳을 확인해야하기 때문에 ord함수를 써서 문자를 아스키코드로 변환한다. 어차피 순서가 중요한거라 -ord(‘a’)를 활용해서 a부터 z까..