qwlake's Blog

2019 카카오 겨울 인턴 1번 - 쇠막대기

https://programmers.co.kr/learn/courses/30/lessons/42585 자바스크립트(javascript) 연습겸 풀었던 문제다. 문제 자체는 간단하다. 스택을 사용해서 괄호가 닫히는 경우만 잘 처리 해주면 된다. 괄호가 닫혔을때 취해야 하는 경우의 수는 두 가지인데, 레이저 위치인 경우’()’ ...

Posted by qwlake on May 4, 2020

백준 16323번 - Intergalactic Bidding

https://www.acmicpc.net/problem/16323 영어 번역만 잘 하면 쉬운 문제다. 주어진 입찰 금액을 입찰자들이 제시한 금액으로 채운다. 입찰자들이 제시한 금액을 선택했을때 합이 주어진 입찰 금액과 같아야 한다. 먼저 입찰자들을 제시 금액 내림차순으로 정렬한 후에 남은 입찰 금액보다 i번째 ...

Posted by qwlake on April 16, 2020

백준 17351번 - 3루수는 몰라

https://www.acmicpc.net/problem/17351 문자열 ‘MOLA’를 세는 임시 문자열과 개수가 저장될 DP 배열을 만든다. 문제를 해결하기 위해서는 제공된 입력 문자 N*N을 2중 for문으로 탐색한다. 제공된 입력 문자 한 칸을 탐색할 때마다 DP 배열에서 똑같은 위치에 해당하는 곳에 처음 언급했던 ‘임시 문자열’과 개수를...

Posted by qwlake on April 15, 2020

백준 16637번 - 괄호 추가하기

https://www.acmicpc.net/problem/16637 모든 자리에 괄호를 대입해 완전탐색하여 최대값을 찾아야 한다. 나는 그냥 간단하게 재귀 탐색으로 풀었다. 내가 푼 코드 중에서 다음과 같은 함수가 있는데 1 2 def ev(a,b,c): return eval(str(a)+b+str(c)) 이는 정수 a, c를 b에 ...

Posted by qwlake on April 14, 2020

백준 11727번 - 2xn 타일링 2

https://www.acmicpc.net/problem/11727 DP(동적프로그래밍) 문제이긴 한데, 간단한 규칙을 보인다. 타일이 한 개 있을 때부터 순서대로 1, 3, 5, 11, 21 … 위와 같은 규칙을 보인다. 규칙을 수식으로 표현하면 다음과 같다. 1 a[i] = a[i-1]+a[i-1]*2 전체 코드는 다음과 같다. ...

Posted by qwlake on April 13, 2020

백준 11726번 - 2×n 타일링

일단 이 문제는 피보나치 수열의 패턴을 갖는 문제다. 따라서 다음과 같이 짧은 코드로 풀 수 있다. 파이썬 코드 1 2 3 4 cache = [1 for _ in range(int(input()) + 1)] for i in range(2, len(cache)): cache[i] = cache[i-2] + cache[i-1] print(in...

Posted by qwlake on April 5, 2020

백준 11053번 - 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053 DP(동적 프로그래밍, 다이나믹 프로그래밍) 문제의 기본이다. 응용되는 DP 문제가 많다. 꼭 풀어보길 권하는 문제이다. 앞 부분부터 서서히 부분집합을 늘려간다. 부분집합 안에서 i번째 수보다 i+1번째 수가 클 때, (이전 크기의...

Posted by qwlake on April 4, 2020

백준 10844번 - 쉬운 계단 수

https://www.acmicpc.net/problem/10844 DP(다이나믹 프로그래밍, 동적 프로그래밍) 문제이다. 계단의 길이가 1자리일때에는 다음과 같이 0부터 9까지의 숫자 중 하나만 올 수 있다. 단, 계단 길이가 1자리에서 끝나면 0이 오는 경우는 빼므로 총 9개의 경우가 생긴다. 계단 길이가 2일때는 다음과 같다. 진행 ...

Posted by qwlake on April 3, 2020

백준 9465번 - 스티커

https://www.acmicpc.net/problem/9465 전형적인 DP(다이나믹 프로그래밍, 동적계획법)문제다. 1 2 matrix[0][j] = Math.max(matrix[1][j-1], matrix[1][j-2]) + sticker[0][j-1]; matrix[1][j] = Math.max(matrix[0][j-1], matrix[0...

Posted by qwlake on April 2, 2020

백준 5874번 - 소를 찾아라

https://www.acmicpc.net/problem/5874 풀 때에는 몰랐는데 지금 보니 문제가 좀 이상하다. 힌트도 예제 입력과 다른 것 같고, 출력의 설명도 뭔가 빠져있다. 문제 자체는 간단하다. (( 과 ))을 세어서 나올 수 있는 순서쌍을 구하면 된다. 자세히는 “(“의 개수를 “)”를 찾은 개수만큼 더한다. ( 다음에 오는 “)...

Posted by qwlake on April 1, 2020

qwlake's Blog

2019 카카오 겨울 인턴 1번 - 쇠막대기

백준 16323번 - Intergalactic Bidding

백준 17351번 - 3루수는 몰라

백준 16637번 - 괄호 추가하기

백준 11727번 - 2xn 타일링 2

백준 11726번 - 2×n 타일링

백준 11053번 - 가장 긴 증가하는 부분 수열

백준 10844번 - 쉬운 계단 수

백준 9465번 - 스티커

백준 5874번 - 소를 찾아라

CATEGORY

AWS

Algorithm

CS

Django

Docker

ETC

MSA

Nginx

Spring

FEATURED TAGS