Cooper's devlog

[문제 처음 접할 때] 간단히 문제를 설명하자면 성적순으로 이름을 정렬했을 때 범위 안에 들어가고 이름 길이가 같은 친구을 찾는 문제 입니다. 성적과 이름이 같다는 것으로 친구을 찾는 과정이 슬프지만 일단 문제를 한번 보겠습니다. 문제 풀이 수가 많은 문제가 일반적인 문제라고 생각해서 해당 문제를 선정했습니다. 문제 풀이에 앞서 투포인터에 대해 한마디로 정의하자면 두 개의 포인터를 사용한 방법으로 필요한 범위만 연산하고자 하는 방법에서 고안되었습니다. 기본적인 투포인터 문제는 좌우 인덱스를 선언해서 범위를 선정하는 방법으로 접근했지만 해결하지 못했고 이름의 길이를 담은 Queue를 생성한 접근 방법으로 문제를 해결했습니다다. [문제 접근 방법] 1. 이름 인덱스를 담는 Queue를 원소로 하는 배열을 생..

[문제를 처음 접했을 때] 이번 문제는 '합이 0인 네 정수 문제' 입니다. 문제를 간단히 설명드리면 말그대로 합이 0일 때 a,b,c,d의 조합 갯수를 구하는 문제 입니다. 처음 문제를 보고 생각한 접근 방법은 반복문을 이용한 완전탐색(Brute Force)를 생각했습니다.하지만, 입력의 크기가 4000이므로 시간 복잡도가 O(N^4)인 비효율적인 시간 복잡도가 발생합니다. 다른 접근법을 생각해야 합니다. 이 정도 연산은 컴퓨터에겐 괜찮지만 문제를 해결 못하는 답답함에 고통 받습니다;; 이를 개선하기 위해서는 투포인터(Two Pointer)을 이용해야 합니다. 투포인터(Two Pointer)은 아래 블로그에 잘 정리되어 있기 때문에 하단에 링크를 들어가셔서 내용 보시는 것을 추천하고 밑에 단계별 코드 ..

1. 문제 링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고 www.acmicpc.net 2. 문제 설명 3. 문제 접근 1. 배열 값을 좌우/상하 변경 2. check(가능한 캔디 길이를 확인) 3. 데이터 원상 복귀 check method 설명 1. 행 탐색 : 좌우 값이 일치 시 -> count++ 2. 열 탐색 : 상하 값이 일치 시 -> count++ 3. count < ans라면, ans = count 4. 문제 풀이 1 2 3 4 5 6 7 8..

1. 강의 링크 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 2. 문제 설명 3. 문제 접근 1. 배열의 모든 합을 구한다. 2. 두 배열을 선정 후, 합과 두 배열이 차가 100인지 확인한다. 3. 일치하는 경우가 발생 시, 두 배열 값을 -1로 설정한다. 4. 배열 출력(만약, 0과 -1이 아닐 때) 4. 문제 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

1.문제 링크 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 2. 문제 설명 3. 문제 접근 과정 요약 1. arr[idx]값을 dp[idx]에 추가한다. (dp[idx] = arr[idx]) 2. dp 값이 다음 조건이 일치할 경우에 변경한다. (1) arr[left] < arr[right] (2) dp[right] < dp[left] + arr[right] 두 조건 만족 시, d..