알고리즘 분류에는 깊이 우선 탐색이 나와 있었는데 나는 이 방법보다는 너비 우선 탐색이 더 수월하다고 판단하여 BFS를 이용해서 코드를 작성했다. 큐로 구현해보면 시간초과(TLE)가 발생하는데 집합으로 구현해보면 시간초과가 발생하지 않는다.자료구조에 대한 시간복잡도를

💡문제접근 > * 전에 시도했다가 틀렸던 문제여서 다시 풀어보기 위해 도전했다. > * 첫 번째 단어에서 한 문자를 더하거나, 빼거나 하나의 문자를 다른 문자로 바꾸어 나머지 입력받은 단어와 구성을 같게 하는 경우 비슷한 단어라고 한다. 💡코드(메모리 : 3125

이전에 포스팅했던 \[백준 9019번 DSLR]과 거의 비슷한 유형의 문제였다.N은 20000보다 작거나 같은 자연수이므로 방문 여부 배열의 크기를 20,000으로 잡아준다.큐에 현재 숫자, 만들어진 숫자(문자열 형태) 형태로 넣어주면서 0 혹은 1을 하나씩 붙여나가면

윈도우의 크기 변경키 이벤트 사용마우스 이벤트 사용트랙바 이벤트 사용마우스 + 트랙바 이벤트 사용직선 & 사각형 그리기

간단한 소수 판정 문제라고 생각하고 무리없이 코드를 작성하고 제출했는데 25%에서 WA를 받았다.코드에 어떤 문제가 있는지 보아하니 중복을 고려하지 않았고 숫자의 맨 앞자리가 0인 경우를 제대로 체크하지못했다. 중복을 제거하기 위해서 set을 이용해 중복을 제거해주었고

정수 N을 정수 D로 나눴을 때 몫을 Q, 나머지를 R이라고 하고 나머지 정리에 의해 식을 세워보면 N = Q × D + R을 만족하게 된다. 모든 정수를 한 정수 D로 나눴을 때 나머지가 같아지는 가장 큰 D를 구하는 문제인데 결국 구하고자 하는 D는 최대공약수와 관

처음엔 문제를 잘 이해하지 못해서 시간이 좀 오래 걸렸다.통신연구소의 레이저 송신기에서 보내는 레이저의 방향은 오른쪽에서 왼쪽이다.테스트케이스를 예제로 설명하면 다음과 같다.첫 번째 탑의 높이인 6은 수신받을 탑이 존재하지 않으므로 0이 된다.두 번째 탑의 높이인 9에

되게 간단한 문제라고 생각했는데 규칙을 파악하고 이를 코드로 옮기는 과정에서 많은 시간이 걸렸다. 장치의 가동 횟수가 최소가 되게끔 하도록 이동한다면 아래와 같은 규칙이 나오게 되고 거리의 제곱근을 기준으로 계산하면 문제를 해결할 수 있다.1 + 2 + ... + (n

이전에 포스팅했던 \[백준 2293번 동전 1]의 문제와는 다른 문제였다. 이 문제는 k원의 가치를 만드는데 필요한 동전의 개수가 최소가 되게끔 하는 문제였다.💡소요시간 : 24m

테스트케이스를 예제로 점화식을 세워보았다.1원을 이용해서 1 ~ 10원을 만드는 방법의 수는 모두 1가지가 나온다.1, 2원을 이용해서 1 ~ 10원을 만드는 방법의 수를 단계적으로 살펴보자.1) 1원을 만들 수 있는 경우의 수 : 02) 2원을 만들 수 있는 경우의

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제였다. 이 문제는 2차원 배열을 이용한 다이나믹 프로그래밍의 문제였다.이 문제를 풀면서 어떤 방식으로 접근을 해야하는지는 이해를 했지만 한 가지 의문점이 들었다. 만약에 최장 공통 부분

LIS(Longest Increasing Subsequence)란, 가장 긴 증가하는 부분 수열을 말한다.Q. 리스트 6, 2, 5, 1, 7, 4, 8, 3이라는 배열이 존재한다. 이 배열의 LIS를 구해라.A. 2, 5, 7, 8Code위의 알고리즘의 시간복잡도는

2중 for문을 통해서 가장 긴 증가하는 부분 수열을 구하는 문제가 아니라 이분 탐색으로 탐색의 범위를 좁히는 방법으로 작성해야한다. 이분 탐색은 정렬이 된 데이터에 대해서만 수행이 가능하다고 알고 있었는데 이걸 어떻게 적용해야할지 몰라서 막막하다가 최장 증가 부분 수

이전에 포스팅했던 \[백준 11053번 가장 긴 증가하는 부분 수열]과 \[백준 가장 큰 증가하는 부분 수열] 문제를 이미 경험해봐서 그런지 접근하는 부분에 있어서는 엄청 헤매지 않았던 것 같다. 다이나믹 프로그래밍에 대한 문제를 더 풀어보면서 감을 익히고 그 개념이

종이에 그려가면서 어떤 동작을 취해줘야하는지 일일이 체크해주면서 정확하게 코드를 작성했다.💡소요시간 : 7m

소스 코드의 함수를 그대로 구현하면 간단하지만 a, b, c의 값이 큰 값일 경우 값을 계산하는데 매우 오랜 시간이 걸린다. 따라서 dp배열을 이용해서 만약 값이 존재한다면 함수를 호출하지말고 그대로 그 값을 반환해주는 방식으로 코드를 작성했다.💡소요시간 : 20m

종이에 표를 그려가면서 각각의 경우에 대한 답을 찾아서 해결할 수 있었다.💡소요시간 : 27m

1부터 N까지의 합을 구하는 문제였다. 다이나믹 프로그래밍을 이용해서 점화식을 구하는 방식으로 코드를 작성했는데 메모리 초과가 나와서 결국 1부터 N까지의 합을 구하는 식을 그대로 작성했다.💡소요시간 : 10m

다이나믹 프로그래밍을 이용한 피보나치 수의 개수를 구하는 문제였다.주의해야 할 점이 있다면 dp\[1] = 1, dp\[2] = 2라는 점이다.💡소요시간 : 18m

Python Python Dynamic Programming Implementation question list가장 기본적인 DP문제 리스트(꼭 본인 힘으로 해결해보고 코드 리뷰 진행할 것)평범한 배낭(백준 12865번)가장 긴 증가하는 부분 수열(백준 11053번)L