김쿠쿠:커밋은했니!

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. 문제 programmers.co.kr/learn/courses/30/lessons/17680 캐시 미스 -> answer += 5 Pangyo : 캐시에 없음 -> 캐시 미스 -> answer += 5 Seoul : 캐시에 없음 -> 캐시 미스 -> answer += 5 Jeju Pangyo Seoul cache full 2. NewYork : 캐시에 없음 -> 캐시 미스 - > answer += 5 캐시가 꽉참 -> 제일 먼저 사용했었던 (= 제일 최근에 사용하지 않았던) Jeju 제거 캐시 앞으로 당긴 후 제일 뒤에 NewYork push Pangyo Seoul Newyork 이런 식으로 반복 즉 알고리즘을 4개로 나눌 수 있다. cache full cache full X cache miss 맨..

1. 문제 programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 2. 풀이 문제는 크게 3가지로 나눌 수 있다. step 1. 오른쪽 / 아래 / 대각선아래가 같은지 확인 step 2. 같은 것 표시 step 3. 같은 것 제거 후 아래로 내리기 step 4. 반복 따라서 나는 step1. 이중 for문을 이용하여 보드의 모든 원소 오른쪽/아래/대각선아래 확인 step2. 같은 게 있다면 또다른 room ..

1. 문제 programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 2. 풀이 영어를 스트링으로 비교하려다가 어떻게 비교하는지 모르겠어서 아스키코드로 다 숫자로 바꿨다. 영어가 두글자길래 앞에 두글자 뒤에 두글자가 오도록 앞에 영어에는 100을 곱했다. 예를들어 ac라면 아스키 코드로 a= 97 c= 99이므로 숫자 9799로 바꾼 것이다. 이렇게 숫자 배열을 2개 만든 뒤, 순서대로 비교하고, 같은 것을 발견..

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에 저장하는 전략을 사용하였다. 두번째로 앞의 사건이 그대로 ..