Dynamic Programming(동적계획법) vs Divide and Conquer(분할 정복)
·
Algorithm/Theory
Dynamic Programming(동적계획법)과 Divide and Conquer(분할 정복)의 차이를 알아보자. 차이를 알아보기에 앞서 동적계획법을 알아보자. Dynamic Programming(동적 계획법) Dynamic Programming은 최적화와 연관이 있어, 'Dynamic Optimization'으로 불리기도 한다. 그러면, Dynamic Programming이 도대체 성능과 어떠한 연관이 있는 것일까? Dynamic Programming 알고리즘은 복잡해 보이는 문제를 하위의 작은 문제들로 쪼개고, 하위 문제들의 결과를 별도의 저장공간에 저장을 한다. 이렇게 함으로써, 동일한 하위 문제가 나왔을 때 중복해서 계산을 할 필요가 없도록 한다. 좀 더 나은 이해는 이전 포스팅인 피보나치 문제..
[DataStructure] Stack(스택)
·
Algorithm/DataStructure
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(자료구조)와 Algorithm(알고리즘)
·
Algorithm/Theory
Data Structure(자료구조) 컴퓨터 과학에서 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 함 효율적인 자료구조란 프로그램의 실행시간 효율과 저장공간 효율을 의미함 각 자료구조의 장단점을 숙지하고 상황별로 적합한 자료구조를 선택하는 능력이 중요 자료구조의 분류 https://wayhome25.github.io/cs/2017/04/17/cs-18/ 단순구조 : 프로그래밍에서 사용되는 기본 데이터 타입 선형구조 : 저장되는 자료의 전후 관계가 1:1 인 구조 (리스트, 스택, 큐 등) 비선형구조: 데이터 항목 사이의 ..
[Leetcode] 1. Two Sum - Top Interview Questions
·
Algorithm/Leetcode
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 - lv01] 3진법 뒤집기(Python)
·
Algorithm/Programmers
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이..
[Cub3D] DDA 알고리즘 vs Bresenham 알고리즘
·
42Seoul/Cub3D
DDA (Digital Differential Analyzer) 알고리즘 DDA는 컴퓨터 그래픽에서 직선, 삼각형 또는 다각형을 형성하기 위해 직선을 그리는 데 사용된다. DDA는 한 좌표의 일정한 간격으로 라인을 따라 샘플을 정수로 분석하고 다른 좌표에 대해서는 라인에 가장 가까운 정수를 반올림한다. 따라서 선이 진행됨에 따라 첫 번째 정수 좌표를 스캔하고 두 번째 정수를 가장 가까운 정수로 반올림한다. 따라서 x 좌표에 DDA를 사용하여 그린 선은 x0 ~ x1이지만 y 좌표의 경우 y = ax + b가되고 함수를 그리려면 Fn (x, y 반올림)이된다. Bresenham 알고리즘 Bresenham Algorithm은 1962 년 J.E. Bresenham에 의해 개발되었으며 DDA보다 훨씬 정확하고..
[Programmers - Lv03] 추석 트래픽(C++ / Python)
·
카테고리 없음
추석 트래픽 코딩테스트 연습 - [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" 날짜 종료 시간 처리 시간" 로그 문자열들을 이용하여 로그들이..
[Programmers - lv04] 가사 검색 (C++/Python)
·
Algorithm/Programmers
가사 검색 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제 설명 주어지는 words의 단어들을 quries로 찾아내는 문제. quries에는 '?'라는 와일드 카드가 존재하고 ?는 모든 문자에 해당한다. 입출력 예 문제를 보자마자 Trie로 풀어야겠다는 생각에 예전 기억을 떠올리며 Trie 자료 구조를 이용하여 문제를 풀었지만, 효율성 테스트에서 막혔다. 가사검색 풀었던 친구에게 물어보니 reverse trie를 만들어서 해결하라는 말을 듣고, 문제를 통과했다. 문제 풀이 소스코드 : C++ Trie 를 이용한 풀이 #include #include #include #include using namespace std; int cnt; class Trie{ public: Trie *chi..
WONILLISM
'알고리즘' 태그의 글 목록