BOJ 썸네일형 리스트형 백준 11053 / 가장 긴 증가하는 부분 수열 이거 꽤 중요하다고 한다. LIS (Longest Increasing Subsequence)라고 따로 명칭이 있는 알고리즘이다. 풀이법은 입력된 수열에서의 비교와 새로운 배열을 하나 생성해 그 수가 몇번 째에 놓일 수 있는지, 두가지 비교를 하는 것이다. ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 예를들어 2, 1, 2 이렇게 3개의 수가 있다고 가정하면 첫번쨰 수 2는 생성될 부분 수열의 첫번째에 놓일수 있으니 D[0] = 1이다. 두번째 수 1 또한 생성될 부분 수열의 첫번쨰에 놓일수 있으니 D[1] = 1이다. 그리고 첫번쨰 수 2의 뒤에 놓일 수 없기떄문에 그래로 1. 세번 쨰 수 2는 우선, 생성될 부분 수열의 첫번째에 놓일 수 있으니 D[2]=1이다. 또한 두번째 수인 1의 뒤에 놓일 수 있으니 D[1.. 백준 15990 / 1,2,3 더하기 5 다이나믹 프로그래밍 연습문제 다이나믹 프로그램은 점화식 짜는 게 우선적으로 중요하기 때문에 좀 더 머리를 써야할 거 같다. n을 완성하는 수식 중 i로 끝나는 식을 ans[n][i]라 하면 1,2,3 더하기의 점화식은 ans[i][1] = ans[i - 1][2] + ans[i - 1][3]ans[i][2] = ans[i - 2][1] + ans[i - 2][3]ans[i][3] = ans[i - 3][1] + ans[i - 3][2] 소스코드는 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include using namespace std; long long.. 백준 1463 / 1로 만들기 다이내믹 프로그래밍 연습 문제 해설을 듣기 전에 풀어보려고 시도했을 때 처음 했던 생각은 N에서 1을 구하는 거보다 1에서 N을 구하는 연산이 더 쉽지 않을까해서 재귀로 짜봤는데 시간 초과가 떴다. N의 범위가 꽤 크기 때문인 듯 다이내믹 프로그래밍 문제를 풀려면 우선 점화식을 짜야된다. 1로 만들기 문제의 점화석은 D[N] = D[N/3] +1 (나누기 3이 가능할때) = D[N/2] +1 (나누기 2가 가능할때) = D[N-1] + 1 고로 D[N] = min(D[N/3]+1, D[N/2]+1, D[N-1]+1) 이다. 피보나치랑 비슷하다.(?) 코드는 12345678910111213141516171819202122232425262728293031323334353637383940414243#inclu.. 백준 3055 / 탈출 BFS 연습문제 어렵다. 문제를 풀기 전 캐치해야될 것 고슴도치가 움직이기 전 물이 먼저 움직여야한다. (물의 4방향 탐색이 끝나야한다) 그래서 풀어봤더니 런타임 에러.. 비주얼 스튜디오에선 잘만 돌아가는데 백준에선 런타임 에러가 났다. 그 이유를 검색해보니 [원인] 배열에 할당된 크기를 넘어서 접근했을 때 전역 배열의 크기가 메모리 제한을 초과할 때 지역 배열의 크기가 스택 크기 제한을 넘어갈 때 0으로 나눌 때 라이브러리에서 예외를 발생시켰을 때 재귀 호출이 너무 깊어질 때 이미 해제된 메모리를 또 참조할 때 이 7가지 일이 발생했을 때 런타임 에러가 난다고 한다. 내 코드의 경우는 QUEUE가 비어있는데 계속 POP이나 FRONT 등 접근을 시도한 경우인 듯. 123456789101112131415.. 백준 14502 / 연구소 BFS+재귀 연습문제 맵이 최대 8X8이기 때문에 맵에 벽 3개를 세운 모든 경우를 따져보면 쉽게 풀 수 있다. 이때 삼중for문보다 재귀를 사용해서 풀면 뭔가 있어보이지ㅎ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361.. 백준 2206 / 벽 부수고 이동하기 BFS 연습문제. 처음엔 맵에 존재하는 벽을 하나 부순 모든 경우를 계산하여 최소값을 구해봤는데, 시간 초과에 걸렸다.N, M이 1000인걸 확인하지 않고 풀었던 것 같다.(맵 사이즈 체크부터 해보자) 벽을 부수었는지, 벽을 부수지 않았는지에 따라 노드 값이 다르기 때문에 현재 좌표와 함께 벽을 부수었는지에 대한 카운트 값을 담아야한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include#include#include#include#in.. 이전 1 ··· 7 8 9 10 다음
