김쿠쿠:커밋은했니!

1. 문제 n X m 배열의 [0, 0] 셀에서 출발하여 1부터 nm 사이의 정수를 “나선형” 순서로 채우는 알고리즘 spiral(n, m)을 작성하라. 전제: 1 ≤ n, m ≤ 100 실행예: n, m 값을 입력받아 spiral 알고리즘을 이용하여 초기화된 배열을 출력하는 프로그램을 작성하라 예: 4 X 5 배열 A 2. 풀이 나선형은 네가지로 나눌 수 있다. 또한 나선형은 반복되며 나선원의 반경이 점점 작아진다. 왼쪽->오른쪽 왼쪽에서 오른쪽으로 x축으로 index가 증가한다. y축은 항상 가장 높은 곳으로 고정이다. 위 -> 아래 위쪽에서 아래쪽으로 y축으로 index가 증가한다. x축은 항상 가장 오른쪽으로 고정이다. 오른쪽 -> 왼쪽 오른쪽에서 왼쪽으로 x축으로 index가 감소한다. y축은 ..

1. 문제 www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 2. 풀이 초기 세팅이 많이 필요해서 헛갈릴 수 있지만 결국은 피보나치와 같은 원리이다 삼각형의 변은 3개이기 때문에 항상 직전 것과 3개 전것의 합으로 다음 삼각형의 변이 결정된다. 각도를 생각하면 이해하기 쉽다. 즉 이전의 값으로 다음의 변수가 결정되므로 이전의 값을 저장해두어야 하는 DP (Dynamic Programing)문제이다. 3. 코드 #include #include using namespa..

1. 문제 www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 2. 풀이 왼쪽에서 오른쪽으로만 갈 수 있으므로 눈앞에 닥친것부터 해결해야하는 전형적인 그리디 알고리즘 문제이다. 따라서 나는 temp에 첫번째 원소를 두고 만약 temp보다 새로나온 원소가 작다면 temp를 업그레이드 시킨 후 temp에 거리를 계속 곱했다. 예를들어 거리 5 3 1 기름값 3 5 2 2 일때, 1. temp = 3으로 둔 뒤 ans += temp * 5 2. temp..

1. 문제 www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 2. 필요한 개념 문제의 핵심은 +과 -만 존재한다는 것이다. 즉 식의 우선순위가 없으므로 괄호 내부에서도 앞에서부터 식이 진행된다. 따라서 - 뒤에 괄호를 시작해서 그 다음 -앞에서 괄호를 닫아주면 된다. 예를 들면 50 + 20 + 30 - 49 +66 - 80 식이 있다 하면 50 + 20 +30 - (49 +66)- 80 이렇게 바꿀 수 있다는 것이고 이는 50 + 20 + 30 -49 ..

1. 문제 www.acmicpc.net/problem/11399 2. 필요한 개념 이득이 되는 것부터 해치워나가는(?) Greedy Algorithm 문제이다. 3. 해결 방법 숫자 크기가 작은것부터 sorting 한 후, 각 숫자가 나온 횟수 만큼 곱한다. 4. 코드 github.com/gimkuku/Algorithm/blob/master/11399.cpp gimkuku/Algorithm Contribute to gimkuku/Algorithm development by creating an account on GitHub. github.com 오늘은 첫날이니 쉬운 것부터! 1일 1알고리즘 화이팅

1. 문제 문제 요악 하면 - 수열은 수열인데 - 앞의 어떤 수와도 등차수열이 아닌!! - 즉, 앞의 어느 수와도 A[i] - A[i-k] != A[i-k] - A[i-2k]를 만족하지 않는 - 근데 그 중에서 가장 작은 수를 원소로 가지는 - 수열을 찾아라 2. 필요한 배경지식 + 풀이 방법 - 요즘 다이나믹 프로그래밍을 많이해서 그런가 DP라고 생각을 해서 앞의 차를 다 cache로 가지고 있으려고 했는데 - 어차피 가장 작은수를 찾는 거여서 수가 그렇게 커지지 않아 - 하나하나 조건에 일치하는지 따져보는 것으로 전략을 바꾸었다. 3. 풀이 #include #include using namespace std; //지금 오는 숫자가 앞에, 앞에 나왔었던 숫자가 뒤에 //자기 고유의 숫자 cache[in..

1. 문제 algospot.com/judge/problem/read/DRAGON 2. 필요한 개념 - 동적계획법 : 동적 계획법이란 앞의 사건이 뒤의사건에 영향을 미쳐 앞의 것을 저장해놓고 뒤에 사건을 계산할 때 꺼내 쓰는 것이다 . 이 문제에서는 앞의 X 가 뒤의 X+YF 가 되고 앞의 Y 가 뒤의 FX -Y 가 된다. 따라서 앞의 사건이 규칙적으로 이루어지며 뒤의 사건에 영향을 주기때문에 다이나믹 프로그래밍으로 풀어야 된다. 3. 내 전략 우선 처음에는 쉽게 생각했다ㅎㅎ /... P가 1,000,000,000개까지 인것을 보기 전까지... 그냥 단순하게 규칙을 보니 FX와 YF 만 달라지고 중간에 +- 만 계속 달라지길래 +-를 STRING에 저장하는 전략을 사용하였다. 두번째로 앞의 사건이 그대로 ..

1. 필요한 개념 - dfs 란(뇌피셜 정리.. ) : 재귀를 통해 전체 경우를 다 보는 탐색을 말한다 > 이때 전체 경우를 다보는 경우도 있고, 경우를 찾으면 멈추는 경우도 있음! - 백트래킹 백트래킹이란 dfs에서 뒤에서부터 모든 순열을 다 조합하는 것이다. (주로 내가 이럴 때 쓰는데 정의가 이것은 아니다..) 2. 문제 3. 풀이 부분 수열이란 한 수열에서 특정 숫자를 골라서 만든 수열이다. 즉 특정 숫자가 들어가고/안 들어가고 두 가지의 경우로 나뉜다. (고등학교 때 부분수열의 개수가 공집합 포함해서 2^N개인 거 배웠죠,, 그런 개념) 그래서 나는 dfs(int 인덱스, int 합)인 함수를 만들고 - 해당 인덱스의 숫자가 들어가는 경우 : sum = sum + arr [i] // arr은 원..

1. 필요한 개념 - 동적계획법(뇌피셜로 작성하였음.. ) 동적계획법은 뒤의 사건이 앞의 사건에 영향을 받을때 이용된다 그래서 동적계획법 문제는 점화식으로 풀리는 문제가 많다.. 2. 문제 3. 풀이 문제가 복잡해 보이지만 따지고 보면 1. 앞에서부터 봤을때 증가하는 수열 + 2. 뒤에서부터 봤을때 증가하는 수열 ---------------------------------------- =앞에서부터는 증가하고 뒤로는 감소하는 수열 을 찾을 수 있는 원리이다. 그래서 나는 앞에서 부터 증가하는 수열을 Icache에 담고 뒤에서부터 증가하는 수열을 Dcache에 담은 후 각 인덱스 마다 Answer = Max(Icache + Dcache)를 했다. 4. 코드 #include #include #include u..