https://www.acmicpc.net/problem/1365 접근 방법 생각을 해보면 꼬이지 않는 가장 긴 사이즈를 전체 사이즈로 빼주면 결과가 나온다. 여기서 꼬이지 않는 가장 긴 사이즈는 증가하는 전봇대의 수열이라고 생각하면 쉽다. 예를 들어서 Input 3 , 1, 4, 5, 8 , 2 라고 하면 꼬이지 않으면서 가장 많은 전깃줄을 만들 수 있는 경우는 { 3, 4 , 5 , 8 } 또는 { 1 , 4, 5 , 8 }이 될 것이다. 즉 수열 중 가장 사이즈가 큰 부분 수열이 된다는 것이다. 또한 내가 놓쳤었던 부분도 알게 되었다. 기존의 나는 LIS를 구할 때 https://dev-room.tistory.com/14?category=792849 의 소스를 들어가보면 ArrayList lis =..

https://www.acmicpc.net/problem/5582 접근 방법 먼저 2개의 문자열에 대해 완전탐색을 하기로 결정함. 하지만 그렇게 하게 되면 N! 이 나오기 때문에 메모이제이션을 하기로 결정했다. 처음에 코드를 구현 할 때 나는 재귀적으로 풀어주려고 했었다. static int recursive(int char1_index,int char2_index ){ if(char1_index >= char1.size() || char2_index >= char2.size()){ return 0; } if(dp[char1_index][char2_index]!=0){ return dp[char1_index][char2_index]; } dp[char1_index][char2_index] = 1; if(..

https://seomal.org?i=WEB2HOME-SERVER Seomal seomal.org 출처 : https://opentutorials.org/course/3265

비트마스크란 무엇인가? 먼저 비트는 이진수를 말하는 것인데, 비트를 활용한 테크닉을 말한다. 비트는 0과 1의 값을 가지고 있고, 문제 풀이를 할 때 보통 true/false | on/off | having/not having 으로 두고 푼다. 비트마스크를 왜 써야할까? 비트마스크를 쓰면 우리에게 이점이 무엇인지 생각을 해보자. 예를 들어보자. 우리는 배열이 3인 집합 { 1 , 2 , 3 } 가 있다고 가정한다. 여기서 몇가지의 요소를 뽑아 어떤 요소를 선택했는지 표현 할 수 있다. 즉, 집합의 어떤 요소를 구성하고 있는지를 나타내는 부분집합을 어떻게 표현할 수 있는가? { { 1 } { 1 , 2 } { 1 , 3 } { 2 } ... } 위와 같은 형태로 이것을 boolean 1차원 배열로 표현 할..

https://www.acmicpc.net/problem/14890 접근 방법 N의 크기가 크지 않아서 그냥 완전 탐색을 하기로 했다. 행 검사 따로 . 열 검사 따로 하기로 했다. 먼저 행을 검사할 때 지금 값과 그 전의 값의 차이가 2라면 그냥 해당 행에 대해 검사하지 않고 Pass if(Math.abs(map[i][k]-map[i][k-1])>1){ flag = false; break; } 지금 값보다 그 전의 값이 크다면 ( F(n-1) > F(n) ) 앞으로의 값들을 체크해줘야한다. 여기서 경사로는 서로 겹치면 안되기 때문에 visit배열에 체크를 해줬다. if(map[i][k-1] - map[i][k] == 1){ if(k+L-1 >= N){ flag = false; break; } for(i..

https://www.acmicpc.net/problem/19236 접근 방법 후.. 너무 힘들었다 3시간은 걸린거 같다. DFS로 구현을 했었다. 무조건 시작은 0,0 으로 시작을 한다. 상어가 0,0을 먹고 시작하니 0,0의 방향을 가지고 먹을 것이 있나 탐색을 한다. 먹을 것이 있으면 이제 재귀로 쭉 들어가본다. 가야할 방향에 먹을 것이 더 이상 없다면 끝을 내고 결과값을 저장한다.(최대로) 주의 사항 같은 맵을 쓰면 안된다. 재귀호출을 한번 다 돌리면 다시 돌려놔줘야한다. 먹을 것이 없다는 것은 같은 방향으로 쭉 갔을 때 더 이상 존재하지 않는 것이다. Need Know DFS 재귀 호출의 이해? 깊은 복사와 얕은 복사의 차이 그냥 시뮬레이션.. 전체 코드 ( Java ) import java.i..