Dynamic Programming(동적계획법)과 Divide and Conquer(분할 정복)의 차이를 알아보자. 차이를 알아보기에 앞서 동적계획법을 알아보자. Dynamic Programming(동적 계획법) Dynamic Programming은 최적화와 연관이 있어, 'Dynamic Optimization'으로 불리기도 한다. 그러면, Dynamic Programming이 도대체 성능과 어떠한 연관이 있는 것일까? Dynamic Programming 알고리즘은 복잡해 보이는 문제를 하위의 작은 문제들로 쪼개고, 하위 문제들의 결과를 별도의 저장공간에 저장을 한다. 이렇게 함으로써, 동일한 하위 문제가 나왔을 때 중복해서 계산을 할 필요가 없도록 한다. 좀 더 나은 이해는 이전 포스팅인 피보나치 문제..

Stack(스택) Stack은 특정 데이터를 누적해서 쌓아 올린 형태의 구조이다. 스택의 push, pop 스택의 특징 같은 구조, 같은 크기의 자료를 정해진 방향으로만 쌓을 수 있다. top은 가장 위(마지막)에 쌓여있는 데이터를 가리킨다. top을 통해 top위 부분에 삽입하는 연산을 push, top을 삭제하는 연산을 pop이라고 한다. LIFO(Last In First Out), 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조 스택이 비어있을 때 pop연산을 하게되면 stack underflow가 일어난다. 스택이 가득찼을 때 push연산을 하게되면 stack overflow가 일어난다. 구현 class My_stack: # Constructor def __init__(self): self...

Data Structure(자료구조) 컴퓨터 과학에서 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 함 효율적인 자료구조란 프로그램의 실행시간 효율과 저장공간 효율을 의미함 각 자료구조의 장단점을 숙지하고 상황별로 적합한 자료구조를 선택하는 능력이 중요 자료구조의 분류 https://wayhome25.github.io/cs/2017/04/17/cs-18/ 단순구조 : 프로그래밍에서 사용되는 기본 데이터 타입 선형구조 : 저장되는 자료의 전후 관계가 1:1 인 구조 (리스트, 스택, 큐 등) 비선형구조: 데이터 항목 사이의 ..

https://leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly on..

programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 문제 설명 주어지는 자연수 n을 3진법으로 바꾸고 그 3진법을 앞뒤로 뒤집은 후 이를 다시 10진법으로 표현한 수를 구하는 문제. 문제 풀이 3진법으로 바꾼 수를 담는 tmp를 ""로 초기화한다. 주어진 자연수 n을 3으로 나눈 나머지를 문자열로 변환하여 tmp의 뒤에 붙인다. n을 3으로 나눈 몫을 n에 다시 담는다. n이 0이..

추석 트래픽 코딩테스트 연습 - [1차] 추석 트래픽 입력: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748 programmers.co.kr 문제 설명 주어지는 로그 문자열의 구성은 다음과 같다. "2020-09-15 18:03:00.000 2.000s" 날짜 종료 시간 처리 시간" 로그 문자열들을 이용하여 로그들이..

이상한 문자 만들기 코딩테스트 연습 - 이상한 문자 만들기 문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 programmers.co.kr 문제 설명 공백을 기준으로 문자열을 잘라 해당 문자열의 홀수 번째와 짝수 번째를 처리하는 문제. 스플릿으로 공백을 기준으로 문자열을 자르면될 것 같지만, 공백이 2개 이상 들어왔을 때 처리할 수가 없다. 따라서 직접 스플릿을 구현하여 푸는 문제이다. c++은 원래 구현을해야겠지만(split함수가 존재하지 않음) python같은 경우엔 split이 있어도 쓰지 못한다. 문제 풀이 소스코드 : C++ #include #include ..

수박수박수박수박수박수 코딩테스트 연습 - 수박수박수박수박수박수? 길이가 n이고, 수박수박수박수....와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 수박수박을 리턴하고 3이라면 수박수를 리턴하면 됩니다. 제한 조�� programmers.co.kr 문제 설명 간단한 문제. 문제 풀이 소스코드 : C++ #include #include using namespace std; string solution(int n) { string answer = ""; for(int i=0; i