devlog

출처 : 1915번: 가장 큰 정사각형 (acmicpc.net) 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 방법 dp 문제이다 문제를 쪼개는 방법이 중요하다. 쪼갤 때 사각형의 가장 왼쪽 위 배열을 기준으로 그 정사각형의 한 변의 길이를 기록한다. 가장 큰 정사각형의 변의 길이를 제곱하여 넓이를 구한다. 0000 1111 1111 0000 예를 들어 위 경우에서 왼쪽 위 모서리의 배열에 길이를 저장이면 dp[1][0] = 2, dp[1][1] = 2.. 이렇게 되지만 dp[2][0] 은 1이 된다 변의 길이가 2인 정사각형에 포함은 되지만 그 정사각형에서 왼쪽 위의 점..

문제 고급 주택을 청소해주는 프리랜서가 있다. 최대한의 이익을 얻기 위해서 청소 스캐쥴을 짜야한다. 입력으로는 N이 주어지는데 N개의 청소할 수 있는 곳이 나온다 다음 N개의 줄에는 시작일, 마감일, 비용이 나오고 같은 비용일 때는 적은 일을 한 스캐줄이 선택 받는다. 주택을 옮기는데 비용이 들기 때문에 10만원이라는 지출이 발생한다. 일이 1일에서 3일까지 라면 3일 까지 일을 하는 것이기 때문에 3일에 일을 시작 할 순 없다. 해결 방법 dp 문제로 처음에는 일을 시작하는 날을 기준으로 cache의 인덱스를 정했지만 이러면 같은 날 시작하는 일이 2개 있을 경우 먼저 나온 일로 cache에 저장 되기 때문에 해결 할 수 없다. 그래서 일이 입력된 인덱스를 cache의 인덱스로 잡아 해결 하였다. 재귀..

문제 1부터 N까지 정수가 쓰인 N장의 카드 중 1~2장의 카드가 빠졌다 빠진 카드를 찾아라 (단 공간 복잡도는 O(1)의 공간 복잡도를 가져야 한다.) 빠지지 않은 카드의 번호는 무작위로 섞여 하나씩 제공된다. 풀이 방법 만약 카드가 1장 빠졌다면 1부터 N까지의 합(n*(n+1)/2) 에서 제공되는 카드수를 더 한 값을 빼면 빠진 카드의 수를 알 수 있다. 2장인 경우에는 식이 하나 더 필요하다 1부터 N까지의 제곱의 합이 필요하다 (n*(n+1)*(2n+1)/6) 에서 제공되는 카드의 수를 제곱한 것을 빼면 빠진 두 카드의 제곱의 합을 구 할수있다. 여기서 두 수를 더한 수의 제곱에서 두 카드의 제곱의 합을 빼면 수두의 2*곱한 값 을 알 수 있다. 두 수를 더한 값을 A 두수를 곱한 값을 B라고 ..

출처 : 14501번: 퇴사 (acmicpc.net) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 방법 일을 할지 안 할지 선택하면 되는 dp 문제이다 문제의 입력을 받은데로 인덱스가 시작일 이므로 문제는 간단하다 다음 날 일을 시작하면 p[day]+Money(day + t[day]) 그냥 넘기려면 Money(day+1)을 해주어서 둘 중 max를 선택하면 된다. #include #include #include using namespace std; const int MAX = 15 + 1; const int INF = 987654321; int N; int cache[MAX]; int t[MAX]; int p[MAX]; int Money(..

문제 입력으로 첫 째줄에는 입력 단어의 수 N(5 n; for(int i = 0; i > s; words.push_back(s); if( stack.empty() ) stack.push(s); else if( stack.top() != s ) stack.pop(); else stack.push(s); } if( stack.empty() ){ cout

join의 사용 arr = ['H', 'e', 'l', 'l', 'o'] str_arr = ''.join(arr) join을 사용하면 간단하게 해결할 수 있다.

출처 : 17609번: 회문 (acmicpc.net) 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 방법 회문을 판별하는 알고리즘은 쉽게 생각해 낼 수 있다. 하지만 유사회문을 판별을 하는데 조금 생각을 해야 한다. 유사회문은 한 알파벳을 제거했을 때 회문이 되면 유사회문이라고 한다 여기서 유사회문을 판별하는 방법은 문자열을 처음과 끝에서부터 비교해 오면서 다른 문자가 나올 때 앞쪽 문자를 버릴지 뒤쪽 문자열을 버릴지 판별해주면 된다. 앞쪽 문자를 버리는 경우는 앞쪽 인덱스를 한 칸뒤로 보낸 뒤 뒤쪽문자와 같으면 isPalin함수를 ..

enumerate 인덱스의 번호와 배열의 값을 tuple형태로 반환한다 test = [5, 4, 3, 2, 1] for t in enumerate(test): print(t) #출력 (0, 5) (1, 4) (2, 3) (3, 2) (4, 1) tuple 형태로 반환을 하므로 for 문을 통해 인덱스와 배열의 값을 한 번에 들고 올 수 있다 for index, value in enumerate(test): print("index: {0} value: {1}".format(index, value)) #출력 index: 0 value:5 index: 1 value:4 index: 2 value:3 index: 3 value:2 index: 4 value:1

ord(문자) 를 이용해서 문자를 아스키코드로 변경할 수 있다. print(ord('A')) print(ord('B')) #결과 65 66 chr(숫자) 를 이용해 숫자를 아스키코드로 변경할 수 있다 print(chr('45')) print(chr('46')) #결과 A B

출처 : 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1 programmers.co.kr 풀이 방법 lambda 함수를 사용하여 정렬을 하면 간단하게 풀이할 수 있다. 같은 문자가 2개 이상이면 같은 문자를 가지는 단어끼리는 사전 순으로 앞선 문자열이 앞쪽에 위치하도록 해야 하는데 이런 경우를 해결하기 위해 미리 lambda 함수를 사용 전 사전 순으로 정렬을 한 후 lambda ..