본문 바로가기
반응형

알고리즘

2636번 2636번 - 치즈 이번 문제는 DFS를 이용해서 문제를 풀 수 있었다. 기본적인 아이디어는 치즈가 아닌 부분을 DFS로 탐색하면서, 치즈가 아닌 부분의 근처에 있는 치즈만을 2로 변경시켜준다. DFS가 종료된 이후에는, 체크된 2의 값들을 카운트하고, 다시 0으로(치즈가 사라졌으므로) 값을 변경시킨다. 이런식으로 2로 변경된 치즈가 없을 때까지 while문을 진행하면 시간값과 치즈갯수를 구할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include using namespace .. 더보기
12761번 12791번 - 돌다리 간단한 BFS문제 나올 수 있는 8가지 경우를 큐에 포함시켜서 문제를 풀면된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include#includeusing namespace std; int a, b, n, m;int dist[100001];bool check(int now){ return (now = 0 && dist[now]==0);}int main(){ cin >> a >> b >> n >> m; queue q; q.push(n); dist[n] = 0; while (!q.e.. 더보기
15683번 15683번 - 감시 상반기 대기업 SW 역량 평가로 나왔는데, 풀었던 문제였다. 브루트포스로 하나씩 문제를 쪼개면 풀 수 있는 문제였다. 나는 실제 시험장에서 fill_map을 makeMap 함수안에 각각 구현해서 코드가 굉장 히 더러웠었던 기억이 난다ㅋㅋㅋ 일단 모든 CCTV를 90도로 돌려가면서, 최소의 사각지대를 만들어야 한다. 그래서 재귀함수로 모든 케이스를 탐색하도록 구현했다. 근데 일단 조금이라도 속도를 줄이고자, 90도로 돌렸을 때 나올 수 있는 가짓수를 dir_num 배열에 넣어줬다. CCTV 1번은 4방향이 모두 다르다, 하지만 CCTV 2번 같은 경우에는 2가지 경우만 존재하고, 5번 같은 경우에는 1가지 경우만 존재한다. 그리고 이를 통해서 getMIN 함수에서 for문으로 몇가지 .. 더보기
LIS LIS 최대 증가 부분수열(Longest Inceasing Sub-sequence) 문제. 증가하는 부분 수열은 완전 탐색으로 풀 수 있지만, 수열의 길이가 증가할수록 엄청나게 연산 시간이 증가하게 된다. 최대 증가 수열 같은 경우에는 배열에서 계속 오른쪽으로 이동하면서 부분 문제가 줄어든다. 그리고 왼쪽의 배열 값들은 고려할 필요가 없기 때문에, 최적 부분 구조를 이루므로 동적 계획법을 이용한 풀이가 가능하다. cache[X] = X 에서 시작하는 부분 수열의 최대 길이 라는 점화식을 이용하면 결국 각 인덱스에서 구할 수 있는 부분 수열의 최대 길이가 구해지게 된다. for문을 이용해서 X 다음 인덱스인 X+1 부터 돌면서 , Cache[X] 보다 값이 큰 인덱스를 찾아가면서 재귀함수를 수행한다. 그러.. 더보기
TRIANGLEPATH TRIANGLEPATH 기본적인 DP 문제. 시간 복잡도는 한줄 밑으로 내려갈 때마다 2배씩 증가하므로 2^n-1 이 된다. 따라서 n의 최대값이 100이 시간 내에 구할 수 없게 되므로 DP 를 이용해야 한다. cache[x][y] 는 x,y 에서 얻을 수 있는 최대 점수 cache[x][y] = map[x][y] + max(cache[x+1][y] , cache[x+1][y+1]) 현재 자신의 값 + MAX((x+1,y) 에서 얻을 수 있는 최대값 (x+1,y+1)에서 얻을 수 있는 최대값) 가 되므로 이를 재귀 함수를 이용해서 구현할 수 있다. 굳이 cache 값을 -1로 초기화 하지 않은 이유는, 조건에서 map에 들어가는 값은 1이상 이기 때문에 123456789101112131415161718.. 더보기
WILD CARD WILD CARD 헷갈리는 부분이 은근히 많았다... 뭔가 제대로 정리를 하지 않고 풀었다. 종만북에서 DP문제로 정해져있지만, 완전탐색을 이용해도 시간내에 해결할 수 있는 문제이다. 이 문제에서 핵심은 * 를 어떤식으로 해결하느냐이다. 나는 for문을 이용해서 *을 0칸부터 비교할 string의 끝칸까지 돌리는 방법으로 문제를 해결했다. //하나씩 비교 (맨마지막까지) if (wc[wc_idx] == '*') { for (int i = str_idx; i tc; for (int t = 1; t > wc; cin >> n; for (int i = 0; i > str; go(0, 0); if (chk) ans.push_back(str); } sort(ans.begin(), ans.end()); for (i.. 더보기
JUMPGAME(C언어) JUMPGAME 그냥 풀면 시간초과가 발생하기 때문에, DP로 접근해서 문제를 풀어야했다. 계속 문제에서 틀렸던 부분이 있었는데 원래 아래 처럼 작성했을 때에는 계속 오답이 발생했다. *ret = jump(cache,map, x + move, y, n) + jump(cache,map, x, y + move, n); 하지만 아래처럼 바꿀경우 정답이 통과되었는데... 그 이유를 모르겠다. *ret = jump(cache,map, x + move, y, n) || jump(cache,map, x, y + move, n); 원인해결 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455.. 더보기
DICTIONARY DICTIONARY 다시 풀어본 문제, 좀 고민했지만 위상정렬 문제. 옛날 풀이가 위상정렬을 공부하고 풀었기 때문에 더 깔끔하게 푼 것 같다. 아무튼 위상 정렬에는 DFS 로 푸는 방법과 BFS로 푸는 방법이 있는데, 나는 이제 BFS로 익숙해져있다. C언어로도 한번 바꿔봐야 겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511.. 더보기
반응형

티스토리툴바