분류 전체보기

[Python split] split 함수로 문자열 쪼개기

파이썬은 모든 입력을 문자열(string)로 받기 때문에 문자열을 나누거나 합치는 함수를 알아두면 편리하다. 함수 형태 str = input('문자열을 입력하시오: ') # string 형식으로 입력받기 s1 = str.split() # 기본적인 split함수: 공백을 기준으로 나눔 s2 = str.split('/') # 구분자 지정: 구분자 기준으로 나눔 'home/user/user' -> 'home', 'user', 'user' s3 = str.split('.') # 다른 형태의 구분자 s4 = str.split(',', maxsplit=3) # 구분자와 최대로 나눌 횟수 지정 s5 = str.split(',', 3) # 파라미터명 생략 기본적인 형태는 위와 같다. 가장 정확한 형태는 문자열.spli..

[C++ vector] 사용법

vector container란? vector는 C++에서 자주 사용하는 STL의 연속 컨테이너이다. 그럼 vector는 무엇일까? 간단하게 말하면 vector는 자동으로 메모리가 할당되는 배열이다. 배열처럼 쓰지만 array처럼 최대 크기가 정해져 있는 것이 아닌, 필요에 따라 유동적으로 확장되는 배열이다. 가능한 최대 경우에 맞추어 크기를 할당해야 하는 배열에 비해 메모리를 효율적으로 쓸 수 있다. 모든 STL 컨테이너가 그렇듯 템플릿이기 때문에 '모든' 형식으로 데이터를 넣을 수 있다. 예를 들어 int, float, char 등의 타입은 당연하고, struct까지 가능하다. 이제 vector container의 구조를 알아보자. vector container 구조 기본적으로 배열과 비슷한 형태이다..

[C++ STL] STL이란?

STL이란? 코딩을 배울 때 C로 시작한 사람들은 대개 기초가 잡히면 C++로 넘어온다. 이때 C와는 다른 새로운 것이 많이 추가되어 있는 것을 볼 수 있는데, 그중 하나가 STL이다. 그럼 STL은 무엇일까? STL은 Standard Template Library의 약자이다. 간단하게 설명하자면 여러 자료 구조, 함수, 알고리즘 등을 쓰기 쉽게 정형화해서 라이브러리화 해둔 것이다. 여기서 라이브러리란? 프로그램에서 사용할 수 있도록 미리 만들어져 있는 함수와 변수들의 모음집이다. 예를 들면 C에서 지겹도록 쓴 라이브러리에는 printf, scanf등 표준 입출력 함수에 대한 것들이 담겨있다. 다른 라이브러리로는 , , 등이 있고, clang 컴파일러에는 기본적으로 포함이 안되어있지만 GNU 컴파일러에 ..

[메모이제이션 - Memoization] 메모이제이션이란?

메모이제이션이란? 메모이제이션이란 입력값에 대한 결괏값을 저장해둠으로써 같은 입력값에 따른 함수의 실행이 중복해서 일어나지 않도록 해주는 기법이다. DP로 문제를 풀 때 자주 등장하며, 함수의 중복 호출을 방지해 효율을 높여준다. 왜 쓰는가? 첫 번째와 두 번째가 1인 피보나치 수를 예로 들어보자. 피보나치 수를 재귀적으로 구한다면 위에서 볼 수 있듯이 fib(3), fib(4)등 앞선 피보나치 수가 여러 번 호출된다. 이때 fib(3), fib(4)이 각각 2, 3인 것을 저장해 두지 않는다면, fib(5), fib(6)이 무엇인지 구하기 위해 fib(3), fib(4)를 다시 구해야 한다. 이때 배열을 하나 만들어 이미 구해진 피보나치 수를 저장해둔다면 이 수고를 덜을 수 있다. 구하려는 수가 작다면..

[동적 계획법 - Dynamic Programing] DP란?

DP란? DP, Dynamic Programming(동적 계획법)은 무엇일까? DP란, 하나의 큰 문제를 작은 문제로 나누어 해결하는 기법을 의미한다. 특정한 알고리즘을 지칭하는 것이 아니라, 기법 그 자체를 의미한다. 같은 DP로 문제를 풀어도 다른 알고리즘을 이용할 수도 있다는 것이다. DP가 무엇인지 처음 듣는 사람은 문제를 작은 문제로 나누어 해결하는 기법이 왜 Dynamic Programming이라 불리는 것일까, 하고 궁금증을 가질 수도 있다. 이에 대한 대답은 그저 '멋있어서'이다. Dynamic Programming이란 명칭을 고안한 Richard Bellman에 따르면 말이다. DP는 왜 중요할까? 백준, 코드포스 등 PS(Problem Solving) 사이트에서 문제를 풀다 보면 DP로..

[BOJ 백준 1937번 - 욕심쟁이 판다] 해설

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 설명 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 이 판다의 ..

[BOJ 백준 1300번 - K번째 수] 해설

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 설명 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 접근법 이 문제는 브루트 포스로 접근하면 O(n^2)으로 시간초과가 일어난다. 그래서 다른 방법이 필요하..

[BOJ 백준 1328번 - 고층 빌딩] 해설

https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 문제 설명 상근이가 살고 있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다. 상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤..