매일 알고리즘 2문제 썸네일형 리스트형 11053 가장 긴 증가하는 부분 수열 이 문제는 가장 긴 증가하는 or 감소하는 부분 수열 문제로 시리즈가 여러개 존재한다. 그만큼 우리가 확인해야하는 규칙성이 있다는 것인데, 알고리즘으로 LIS 알고리즘 (Longest Increase Sequence) 라고 한다. 11053 번 문제의 경우 N의 범위가 크지 않아 O(N^2) 으로 구현 가능하지만, 불가능한 경우 O(NlogN) 방식으로 구할 수 있다. 우선 이 문제는 완전탐색의 경우, 즉 O(N^2) 으로 풀이해두었다. #include int N, A[1001], dp[1001], minn, maxx; int main() { scanf("%d", &N); for (int i = 1; i 더보기 10026 적록색약 문제를 읽고난 후, '탐색' 을 가장먼저 생각했다면 올바르게 접근한 것이다. 이 문제는 DFS 또는 BFS 로 접근가능하고 필자의 경우 BFS 로 풀이해보았다. '기본 알고리즘' 카테고리에 추가로 DFS와 BFS 의 대략적인 개념을 올려두었다. 접근은 우선 1) 적록색약이 아닌 사람은 R,G,B 각각의 부분에 대해 count 할 것. 2) 적록색약의 경우 R와 G 중 R을 G로 바꾸어 부분을 구하거나, 또는 G를 R로 바꾸어 계산한다. 라는 기본적인 구현에 대한 생각을 염두에 두어야 한다. BFS와 DFS에 관한 기본 개념을 알고 있을 것이라 가정하고, 소스코드를 아래 첨부해 두었다. 최적화된 것은 아니기에, 더 짧거나 혹은 더 메모리를 적게 소모하는 코드에 대해서는 백준 10026문제 맞은사람을 확인해.. 더보기 1016 제곱ㄴㄴ수 드디어 해결하지 못했던 문제를 풀었다! 범위가 커서, 에라토스테네스의 체를 이용하여 계산하려고 하였는데 이경우 중복되는 숫자(예를들어서 4 9 는 36이 중복된다든지....등등) 를 고려해야 하기에 소수 만을 이용하여 배수가 되는 수를 제거해주는 꼴로 계산하였다! 범위의 경우 HINT가 될 수 있는것은 min ~ max 차이가 1,000,000 이라는것! (시간초과가 나려면 1억정도는 되어야 시간초과!) 따라서 기존 에라토스테네스 식에서, 1) 범위를 max까지 2) 방문한것에 대해서는 visit 배열을 통해 확인! 이미 제곱의 배수가 되는 수에 대해서는 더이상 고려하지 않을것!! 3) 처음 min의 숫자가 제곱인 수에 포함되는지 예외처리! 4) 방문하지 않은, 즉 제곱 ㄴㄴ수에 대해서 bool 변수를 .. 더보기 2789 유학 금지 이 문제는 옆에 기본알고리즘에 올려놓은 '아스키코드표' 를 활용하기 위한 문제이다. 물론 무조건 이를 이용하라는 것은 아니지만, 이용하면 효율적으로 코드를 작성할 수 있다. 알파벳 A~Z 까지 65~ 90 까지 진행되므로 아래와 같이 소스코드를 작성가능하다. (CAMBRIDGE를 전처리 후 visit 배열로 확인하며 출력) #include #include using namespace std; char A[101],B[10]; bool visit[27]; int main() { scanf("%s", A); strcpy(B, "CAMBRIDGE"); for (int i = 0; i < strlen(B); i++) visit[(int)B[i] - 65] = true; for (int i = 0; i < str.. 더보기 3163 떨어지는 개미 이번 3163 떨어지는 개미는, 처음에 물리적 충돌을 고려하다보니 시간초과가 났고, 질문검색을 통해 힌트를 얻어 풀게되었다.충돌을 생각하지 않고, 현재위치에 있는 개미가 계속 진행하는 형태로(통과한다고 생각) 문제를 풀어나가면된다.고려해야할 사항은1) 현재위치, 현재 향하고 있는 방향으로의 거리가 얼마나 되는지2) 가장 바깥쪽에 있는 개미의 ID가 무엇인지2가지를 고려한채 거리순으로 정렬 후 현재 향하고 있는 방향의 가장 끝쪽의 개미를 떨어뜨리면 되는 방식이다.첫번째 테스트케이스의 예제를 아래와 같이 그림으로 표현해보았다.더 자세한 설명을 위해 소스코드를 아래 올려두었다. #include #include #include #include using namespace std; int T,N,L,k,cnt,a.. 더보기 2960 에라토스테네스의 체 기본 알고리즘을 통해 확인할 수 있듯, 이번 문제는 에라토스테네스의 체를 이용하여 풀 수 있는 문제이다. 한가지 유의할 점은 이번 문제에서는 2와 3과 같은 출발(?) 하는 소수 또한 포함되어 계산한다는 점! 간단한 문제이므로 소스코드만 첨부하여 오늘의 알고리즘 풀이는 마친다. #include int N, K,cnt; bool visit[1001],flag; int main() { scanf("%d %d", &N, &K); for (int i = 2; i 더보기 11758 CCW 다시 마음을 가다듬고, 2월 1일 다시 알고리즘 2문제 시작! 그동안 까먹어서인지, 다시 CCW 알고리즘부터 시작한다. CCW 알고리즘은 Counter-Clock Wise 즉 반시계방향을 의미한다. 세가지의 케이스로 생각해보면 좋은데, 첫번째 경우, 아래와 같이 시계방향으로 진행할 때, 두번째 경우, 아래와 같이 반시계방향, 세번째 경우 일직선으로 이동 세가지 경우 모두 세개의 점으로 구성된 예시를 보여주고 있는데, 이와 같이 세점으로 이루어진 삼각형 면적을 구하는 방법은 (x1, y1) , (x2, y2), (x3, y3) 로 이루어진 3점을 통해 위와 같은 식으로 계산가능하다. 부호에 따라 첫번째 그림과 같은 시계방향일 경우 0보다 큰 수, 두번째 그림과 같은 반시계방향의 경우 0보다 작은 음수, 세.. 더보기 [Day 1] 이동하기 우연히도 같은날 랜덤으로 뽑은 문제가, DP 였다. 이번에는 1차원 배열속에서가 아닌 2차원배열속에서의 DP를 구하는 문제이다. 백준 11048 문제이고, N * M 배열에서 (1,1)에서 출발하여 (N,M)에 도착할때까지 사탕의 개수가 최대로 출력되야한다. 그림으로 그려보면 방향은 (1,1) 에서 세방향으로 이동할 수 있으며, 이동하기 전에 현재위치에 올 값을 현재위치 x,y 좌표에 대해 둘다 바로 직전값, 각각의 x,y 좌표에 대해 직전값에 대해 생각해볼 수 있다. 따라서 위의 미로에서의 최대 값이 나오기 위해서는 경로가 아래와 같이 이동해야한다. #include #include using namespace std; int dp[1001][1001],N,M,num[1001][1001]; int mai.. 더보기 [Day 1] 연속합 DP란 Dynamic Programming 을 축약한 단어로, 동적 프로그래밍이라 부른다. 이러한 DP를 푸는 방법은, 아직까지 경험에 의하면 1. 재귀적 호출 2. 점화식 이 두가지의 경우가 대부분인 것 같다. 재귀적 호출은 반복문을 통해서도 해결할 수 있는데, 재귀적 호출의 경우 끝나야 하는 조건이 명확해야 재귀식안에서 탈출 가능하기 때문에 이와 같은 조건이 명확하게 떠오르지않는다면 반복문을 통해서 일부 확인하는 것도 좋은 방법이다. 위의 문제는 백준 1912 연속합 문제이다. Num 배열은 입력받는 배열의 값을, DP배열은 현재위치까지의 최대합을 나타낸다. 이전의 합과 현재 자신의 위치 입력값을 비교하여 Max 값을 현재의 DP 배열안에 저장하도록 하고, 최종적으로 12, 21 즉 33이 최종 답이.. 더보기 이전 1 2 다음
