짱아의 개발 기록장

치즈 내부에 있는 공간을 표시해주어서 외부 공기와 구분해주는 작업이 가장 중요한 것 같다. 어차피 테두리에는 치즈가 없다는 조건이 있기 때문에 (0, 0)에서 BFS를 시작해서 인접한 모든 외부 공기들의 isInside값을 false로 해주었다. 따라서, isInside가 true인 공기(내부 공기)와 인접한 것은 외부공기와 접하지 않았다고 간주했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70..

DP...역시 쉽지 않다. 예전에 풀었던 동전 문제와 유사해서 점화식을 비교적 쉽게 세울 수 있었다. DP[선택한 수의 개수][총 합]이라고 가정했을 때 DP[k][n]을 만들기 위해서 맨 마지막에 뽑은 수가 L이라고 한다면, DP[K][N] = Σ(DP[K-1][N-L]) L => 0 n>>k; // 1개 선택했을 때 for(int i=0; i

백트래킹 하면 가장 많이 떠올리는 문제이다. 근데 이 문제는 시간초과때문에 고생할 수가 있기 때문에 효율적인 최적화 작업을 해주어야 한다. 사실 글쓴이의 풀이보다 1차원 배열을 통해서 더 최적화해서 시간을 줄일 수 있는 풀이방법이 있는 것으로 알고 있다. 따라서, 코드는 참고만 해두시면 좋을 것 같다. (그닥 좋은 풀이는 아닌 것 같다... 시간이 오래 걸림;;) 아무래도 2차원 배열을 활용했고 더 가지치기를 할 수 있는데 적당히만 가지를 쳐서 시간이 오래걸리는 것 같다,,, 나중에 더 최적화를 해보는 걸로... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ..

위상정렬을 이론으로는 알고 있었지만 직접적으로 활용해서 푸는 문제는 처음 접했다. 요즘 라인, 네이버 등 it회사에서 자주 출제되는 경향이 있어서 연습삼아 풀어보았다. 위상정렬에 대한 이론 정리는 아래 블로그에서 아주 잘 정리해놓아서 참고하시면 될 것이다. gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html [알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 이 문제는 우선순위큐를 사용해서 위상정렬을 그대로 구현한 문제이기 때문에 코드를 참고하시는게 좋을 것 같습니다. 1 2 3 4 5 6 7 8 9..

그리디 문제이다. 가스관에서 빵집으로 가는 특정 경로를 완성하게 되면 그것과 전혀 겹치지 않는 경로를 또 만들어야 하기 때문에 한 번 빵집에 도착했으면, 맨 처음 가스관으로 돌아가서 새로운 경로를 찾아가는 것이 핵심이다. 그래서 dfs에서 빵집에 도착하면 true를 리턴해주어서 계속 처음으로 돌아가게 해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 // 빵집 #include using namespace std; int r, c; string s; char map[10001][501]; i..

중위순위의 특징?을 통해서 풀 수 있는 문제이다. 중위순회의 특징은 Start~End의 범위를 가지고 있는 배열에서 Mid = (Start+End)/2;의 값이 루트가 된다는 것이다. 그렇게 계속 재귀를 돌면, level별로 노드를 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546// 완전이진트리#include #include using namespace std; int k, node;vector height[11];int arr[1100] = {0, }; void dfs(int Start, int End, int level){ int mid = (Start+End)/2; height[le..

방문처리가 핵심인 BFS문제였다. 그냥 (x, y)로만 방문처리를 해주면, 더 빠른 길인데도 불구하고 누락되는 경우가 생긴다. 따라서, 말로 몇 번 이동했는지를 인자값으로 하나 더 넣어주었다. => visited[x좌표][y좌표][말 이동 횟수] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 // 말이 되고픈 원숭이 #include #include #include using namespace st..

서버 템플릿 엔지과 머스테치 소개 템플릿 엔진 템플릿 엔진이란, 지정된 템플릿 양식과 데이터가 합쳐저 html 문서를 출력하는 소프트웨어를 의미한다. 아래의 코드르 보자. 1 2 3 4 5 6 7 8 9 $(document).ready(function(){ if(a=="1"){ } }); cs 서버 템플릿 엔진 종류 - JSP, Freemarker 역할 - 서버 템플릿 엔진은 서버에서 구동된다. 서버 템플릿 엔진을 이용한 화면 생성은 서버에서 Java코드로 문자열을 만든뒤, 이 문자열을 html로 변환하여 브라우저로 전달한다. 즉, 브라우저에서는 화면에 띄우기만 하면 된다. 클라이언트 템플릿 엔진 종류 - React, Vue 역할 - 반면, 자바스크립트는 브라우저 위에서 작동한다. 앞에서 작성된 자바 스..