"꾸준하게, 지속하자 "

print(" ".join(str(dict[i]) if i in dict else '0' for i in list_nums)) 위의 코드를 보고 설명을 하겠다. 나도 처음에 이런 종류의 코드를 래퍼런스를 찾다가 발견했을때 상당히 당황했지만, list comprehension의 규칙을 안다면 쉽게 해석 할 수 있다. 결론부터 말하자면 이 코드는 파이썬의 리스트 컴프리헨션(list comprehension)과 조건부 표현식(conditional expression)을 사용한 것이다. 1. 리스트 컴프리헨션(list comprehension) : 리스트 컴프리헨션은 리스트를 생성하는 짧고 간결한 방법이다. 일반적인 for-loop보다 코드가 짧고 읽기 쉬우며, 때로는 실행 속도도 빠르다. `for i in l..

매우어려웠다. 무슨소리인지 접근조차 못했다. 그나마 이해한 것은 5원을 만드는 경우의 수= 1,2원을 통해 5원을 만드는 수(dp[5]) + 5원을 통해 5원을 만드는 수(dp[0]=dp[5-0]. 6원을 만드는 경우의 수= 1,2원을 통해 6원을 만드는 수(dp[6]) + 5원을 통해 6원을 만드는 경우의 수(dp[1]=dp[6-5]). 7원을 만드는 경우의 수= 1,2원을 통해 7원을 만드는 수(dp[7]) +5원으로 7원을 만드는 경우의 수(dp[2]=dp[7-5]). 이렇게 된다. ** 여차저차 해서 난 이해했다고 착각했던 거 같다. 위에 밑줄친 부분인 k값(만들려는 값)에서 coin의 값어치를 뺀 값을 만드는 경우의 수를 더해주는 것이 왜 어째서 해당 coin의 경우를 더해주는 것인지 이해가 잘..

우선 어려웠다. 애초에 dp 배열을 1차원으로 구하면 될 줄 알았는데 그게 아니였다. 그리고 배열의 기준을 첫번쨰 자리부터 차근차근 올라가면서 앞 자리수보다 크거나 같은 수를 구하는 방식이 아니라, 미리 맨 마지막 자리에 올 수를 정해놓고, 앞 자리수에 올수 있는 수를 한정해주는 방법을 쓴다. 그래고 매우 어려운 것이, 우선 난 dp문제를 풀때의 철칙이 1. dp[i]=num의 정의, 2. dp[N]과 dp[N-1]의 관계를 파악해서 프로그래밍을 하였는데 그래서 난 계속 1차원 배열로 풀려고 했었다. 그런데 이젠 dp 배열이 2차원으로 푸는 문제인지 아닌지 0순위로 판단후, 파악해야겠다. 우선 이 문제에서 dp[i][j]=num 의 정의는 "i 번째 자리수에서 맨 마지막 자리에 오는 숫자가 j 일때 가능..

우선 또 기뻤다. 내가 C언어로 배우는 자료구조 란 책을 사회복무요원으로 복무하면서 1년 전쯤에 독학했는데, 그때 공부한 내용을 복습없이 한번에 오로지 내 아이디어로만 구현해 내었다. 이 문제의 핵심은 알파벳이 노드를 나타내는 키로서(비유를 하자면 포인터)로서 작용되어야 하고, 각 입력값을 어떤식으로, 서로가 서로의 관계를 연결시키느냐 였다. 처음에는 각 노드의 입력마다 새로이 new 이렇게 새롭게 클래스를 만들어서 연결시켜 주고자 했는데 이러면 그냥 매번 for문에 돌때마다 새롭게 클래스가 생성될뿐 그 클래스와 다른 클래스의 관계를 표현하기엔 어려운 면이 있었다. 그래서 나는 배열에 알파벳 순서대로(유니코드를 이용한 기발한 방법) 저장하고, 배열의 인덱스와 알파벳의 1부터 26까지의 넘버를 매치시켜서 ..

1시간이 걸려서 해결했다. 이 문제의 핵심은 "반복문의 1회 연산시 증가하는 단위값" 을 점차적으로 3을 나누어서 1까지 재귀를 쓴 다음 단위값이 1이면 해당 좌표에 실질적인 별을 찍어주면 된다. 자세한 풀이는 코드에 주석으로 남겼다. import java.util.Scanner; public class Main { static char[][] arr; public static void main(String[] args) { Scanner s = new Scanner(System.in); StringBuilder sb=new StringBuilder(); int N=s.nextInt(); arr=new char[N][N]; for (int i = 0; i < N; i++) { for (int j = 0;..

우선 DP 문제를 많이 연습해서 그런지, 처음보다는 문제 풀이 방법이 비교적 쉽게 떠올랐다. 우선 DP[i]=num 의 의미를 정의하고 시작하면 풀이법이 자연스럽게 떠오르기 마련인데, 난 i개를 뽑을때 최댓값 num이라고 정의했다. 그리고 DP[N]과 DP[N-1] 의 관계를 나타내면 끝인데, 내가 dp[1]부터 해본 결과 dp[n]= 두 수를 더해서 n을 만드는 수를 인덱스를 가지는 dp배열의 두 값의 합들중 가장 큰 값, 입력받은 arr[i]과 비교해서 큰 값이였다. 다시 쉽게 풀면 dp[5]를 구하려면, dp[1]+dp[4], dp[2]+dp[3]중 가장 큰 값과 숫자카드팩의 갯수를 한번에 맞출수 있는 arr[i] 의 값중 큰 것이다. 왜냐하면 내가 dp[i]는 i를 뽑을 때 가장 큰 값으로 정의했..

일단 매우 어려운 문제였다. 백트레킹을 오랜만에 해서 그런지, 아니면 순열, 조합 구하기 같은 기본적인 백트레킹 문제만 풀어봐서 그런지, 알고리즘 큰 틀에서 풀이법은 바로 알았지만, 그걸 구현하지 못하여서 실패했다.. 그나마 이해했는데 마지막에 oper 함수의 값을 다시 올려줘야 하는 이유를 이해하지 못했지만, 내가 기존에 순열 문제를 푼 기억을 되살려 알게 되었다. 풀이는 코드 옆에 주석으로 다 해놨다. 이 문제를 통해 백트레킹의 실제 상황에서의 적용하는 법을 알게 된거 같다. 이 문제의 핵심은 "깊이"우선 탐색을 어떤 식으로 구현할 것인가 인데, 연산자의 인덱스를 연산자 취급을 하고, 연산자의갯수를 한번 쓸떄마다, dfs로 한층 더 깊게 들어가는 구현법이 가장 핵심인거 같다. import java.u..

문제는 우선 처음 아이디어를 내고 DP[i] =num 이 무엇을 의미하는지와, N-1항에서 N항으로 어떻게 갈수 있는지를 파악하기만 하면 쉽게 풀린다. 두가지 풀이법이 있다. 첫번째는 내 풀이법인데 난 이것이 DP[i]의 정의를 더욱 더 직관적으로 이해할수 있는 코드라고 생각한다. 물론 시간초과나서 틀렸지만. 하지만 알고리즘 원리는 똑같으니 같은 해답이다. 나는 DP[i]=num 의 정의를 N부터 시작해서 연산을 통해 i를 만들수 있는 연산의 최솟값 num 으로 정의했고, 다른 좀더 빠른 방식으로는. i를 1로 만들수 있는 최소연산횟수 num으로 정의했다. 내가 한 방법이 조금 더 문제의 조건에 직관적이긴 하지만, 시간초과가 난게 아마 2중 for문으로 현재 인덱스보다 크고 N보다 작은 것중에 2나 3으..

처음에는 2차원 평면상의 이동이 아니라서 DP로 풀어야 하나.. 하고 끙끙댔는데, 알고보니 +1,-1, *2 의 이동가능 범위(계층이동)의 1차원 수직선상의 이동으로 BFS를 이용하면 쉽게 풀리는 문제였다. 큐에 한계층 이동했을때를 현재 좌표에 반영해서 넣기 곤란했는데, 새로 움직인 좌표를 저장하는 nexti[ ]라는 배열을 만들어서 쉽게 해결하였다. 앞으로 좌표를 수직선이나 평면에 표현할 수 있고, 이동함+최솟값 조건의 문제는 DP가 아닌 BFS부터 생각해서 풀어야겠다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[]..

우선 문제 접근은 매우 쉬웠다 결국 틀렸지만ㅋㅋ,, 이전 포스트에서도 설명했듯, DP문제를 풀 때는 맨 마지막 항 N이 어떻게 구성될수 있는지 경우의 수를 나눠서 일반항을 구하는것과 구한 DP배열의 각 항이 무엇을 의미하는것을 정의하는게 제일 핵심이다. 1. 맨 마지막 항 N이 구성될 수 있는 경우는 3가지 이다. 내가 직접 그림을 그렸다. 그런데 매우 특이한 점은, 맨 마지막항을 "무조건" 방문해야 한다는 조건이 없기에, 만약 2번 3번 경우보다 아예 해당 노드를 안방문하는 경우가 더 클 경우, 그냥 바로 전 항의 dp값을 현재의 dp값으로 할 수 있다는 것이다. 여기서 방문(마신다)는 것은 dp[i]의 값에 현재의 인덱스값 arr[i]를 더해주느냐 마느냐로 정할수 있다. dp[i]의 값을 구하는 식에..