1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net N*M 행렬에서 (0,0)에서 출발하여 (n-1,m-1)로 이동하는 최단 거리를 구하는 문제지만, 벽으로 표현되는 1을 뚫고 지나가서 거리가 줄어든다면 단 1번만 허용할때, 최단거리를 구한다면..? 2. 풀이 bfs로 벽이 있더라도, 단 1번도 뚫지 않았다면 1번만 뚫고 1번 뚫었다면 그 뒤로는 벽을 지나가지 않도록 bfs 탐색하면 될것 같았는데 2차원 배열로 ..
1. 문제1 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 나이트가 최소 몇번 이동하면 주어진 칸으로 이동할 수 있는지 구하는 문제 어렵게 생각할 필요 전혀 없이, 문제에서 주어지는 1번에 이동할 수 있는 경우를 모두 델타배열에 저장하여, 그것을 순회하면 된다 2. 풀이 어렵게 생각할 필요 전혀 없고 일반적인 bfs 흐름으로 가다가 상하좌우 델타배열 [[0,1],[1,0],[0,-1],[-1,0]]을 나이트가 이동할 수 있는 칸으로 바꾼 델타배..
1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net 주어진 n개의 임의의 수열에서 1개 이상의 연속된 부분 수열을 선택할 때, 가장 큰 합을 출력 2. 나의 풀이 단순한 규칙, 점화식으로는 풀기 어렵다 메모리, 시간제한 문제로 $O(N^2)$으로도 통과하기 어렵다 처음에 i번째부터 j번째까지 수열의 합을 dp[i][j]에 저장해서 테이블을 완성하려고 했는데 n의 최대가 100000이라 10만*10만 만들자 마자 메모리 초과 from sys impor..
1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1이상의 정수 x가 주어질때, 1) x가 3으로 나누어 떨어지면 3으로 나눈다 2) x가 2로 나누어 떨어지면 2로 나눈다 3) x에서 1을 뺀다 3가지 연산을 적절히 사용해서 1을 만들고 싶다 연산을 사용한 횟수의 최솟값을 출력한다면? 2. 나의 풀이 다이나믹 프로그래밍 연습문제니까 다이나믹 프로그래밍을 써야겠지 기본이 바텀업이고 반복문 구현이라고 배웠으니까 이에 따라보자 작은 문제부터 구해놓고, 이들을 이용해서 반복문을 구현한다면.. 1이상이니까 dp[0] = 0, 1은 연산을 안해도 1이니까 d..
1. 문제 https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 좌표평면 안에서 개미가 대각선 방향으로 움직이는데, 벽면에 부딪힐 경우, 반사되어 움직인다. 일정한 속력으로 움직일 때, 평면의 크기, 처음 좌표가 주어지고 시간 t가 주어질때, t시간 후에 개미의 위치를 구해본다면..? 2. 풀이 시간 t의 범위가 2억이나 되니까, 일반적인 1칸씩 가는 반복연산으로는 도저히 0.15초만에는 불가능 그렇다고 벽면까지 한번에 가는 방법으..
1. 분할정복 문제를 더 이상 나눌 수 없을 때까지 더 작은 문제로 나누면서 이 작은 문제들을 각각 풀면서, 병합하여 전체 문제의 답을 구하는 알고리즘 divide - conquer - combine 방식으로 설계한다. 문제가 분할이 가능하면 2개 이상의 작은 문제로 나눈다(divide) 나누어진 문제가 분할이 가능하면, 또 다시 문제를 분할하고 그렇지 않으면 문제를 푼다(conquer) 푼 문제들을 통합하여 전체 문제의 답을 구한다(combine) 당연하지만 divide를 잘 하면 나누어진 문제를 푸는 것은 매우 쉬우므로 divide를 잘 하는 것이 중요하다 재귀알고리즘을 많이 사용하게 되는데, 이 때문에 오히려 효율적이지 못할 수 있다. 2. 응용 - 거듭제곱 n번의 거듭제곱은 자신을 n번 곱하므로 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
