MuviSsum

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제: 수열이 주어지면 가장 긴 증가하는 부분 수열의 크기를 찾아라. 문제 이해하기!..

백준 문제 주소: www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 : 파이프를 주어진 NxN배열에서 (0,0) -> (N-1,N-1) 까지 옮길 수 있는 방법의 수를 구하라. DP를 사용해서 푸는 문제였습니다. 처음엔 DFS로 풀었다가 14x14 배열까지는 답이 정상적으로 나오는데, 15x15 배열부터는 시간이 오래걸려서 시간초과가 뜹니다. 각 배열에 3차원의 DP를 사용하면 시간을 매우 단축하여 풀 수 있습니다. ※ dpdp(..

백준 문제 주소: www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제가 귀여워서 시작했습니다. ㅎㅎ 푼 방법은!!! 아기상어의 위치는 움직이므로 처음 시작점을 9 -> 0으로 만듭니다. BFS를 이용하여 가장 가까우면서 먹을 수 있는 물고기를 찾아 잡아먹고! visited 배열을 만들어 자기 자신이 갔던 곳을 체크하면 됩니다. 한 번 잡아 먹을 때마다 계속 visited 초기화와 지난 시간을 체크하고, BFS 큐를 초기화하여 잡아 먹은 지점에서 ..

백준 문제 주소 : www.acmicpc.net/problem/2064 2064번: IP 주소 네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워� www.acmicpc.net 비트마스크로 풀려다가 포기하고 문자열로 푼 다음, 다시 비트마스크로 풀은 문제입니다... 돌돌 비트마스크 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그래서 오늘 올릴 코드는 2개입니다! 문자열 코드와 비트마스크 코드!! ** 푼 방법 1. 일단 네트워크 마스크를 구한다. 2. 아무 IP에 네트워크 마스크를 &연산하면 네트워크 주소가 나온다. 끝. 하기엔 뭔가 아쉬우니까? 네트워크 마스크는 XOR연산과 NOT연산..

백준 문제 주소 : www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net DFS, BFS의 머나먼 조상님 미로 문제에 조건 한 가지를 추가한 문제였습니다. 미로에서 단 한번!!! 벽을 부술 수 있다는 건데요. 하 ㅠㅠ 너무 힘들었어요 보이나요 제 노력... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 처음은 그냥 itertools 라이브러리의 combinations을 사용해서 1이 하나씩 사라진 모든 2차원 배열을 만들었습니다. 바로 메모리초과~~^^ 그래..

백준 문제 주소 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백준알고리즘을 시작한지 이제 한달이 되어가네요. 기본적인 문제들을 풀면서 이제 실력이 좀 늘은 것 같아요 ㅎㅎ 그래서 괜찮았던 문제 하나씩 블로그에 올려보려 합니다! 이번 문제는 Gold-5 문제인 N-Queen 문제인데요! N*N 체스판에 N개의 퀸을 넣고 퀸이 서로 공격을 못 하게 해야합니다. 역시 처음에는 2차원 배열로 해결해야죠!! True와 False를 사용하여 2차원 배열을 써본결과..