![]()
정의 연결되어 있는 객체 간의 관계를 표현하는 비선형 자료구조 가장 일반적인 자료구조의 형태로, tree도 그래프의 특수한 경우이다. 예를 들면, 전기회로의 소자 간 연결 상태나 혹은 운영체제의 프로세스와 자원 관계 또한 그래프로 표현이 가능하다. 그래프의 종류 1) 무향 그래프 (undirected graph) : 무향 에지는 양방향의 의미임. 예컨대 조합(combination)처럼 (A,B) = (B,A)로 순서에 의미가 없다는 것. 2) 방향 그래프 (directed graph) : 에지를 통해서 한쪽 방향으로만 갈 수 있다는 특징. 즉, ≠ 라는 특성을 보임. cf.) 가중치 그래프: 각 간선에 가중치를 부여한 형태의 그래프. 예를 들면 edge에 비용을 부과하는 형식으로 가중치가 부과될 수 있음..
정의 및 특징 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다. 떠오른 풀이방법을 구현하기 위해서는 프로그래밍언어의 문법을 알아야며 요구사항에 맞게 실수없이 코드를 작성하여야한다. 구현은 흔히 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다. 문자열을 파싱하여 처리하는 문제, 코드가 길어지는 문제, 사소한 설정이 많은 문제 등이 구현문제의 예이다. 크게 완전탐색,시물레이션 문제가 코딩테스트에 자주 출제된다. 구현문제의 경우 문자열처리가 쉽고 기본적으로 메소드를 많이 지원해주는 파이썬이 유리할 수 있다. API개발문제 또..
정의 및 장단점 가장 나중에 넣은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조로 Last In First Out(LIFO) 방식이다. 프링글스나 쌓아놓은 책과 같다 구현방법 리스트를 이용하면 된다. 리스트 맨 뒤에서의 작업은 시간복잡도가 낮기 때문에 따로 스택라이브러리가 필요하지 않다. #a_list.append(1) : 괄호 안의 요소를 리스트 맨 뒤에 넣음 a_list = [1,2,3] a_list.append(1) => [1,2,3,1] #a_list.pop() : 리스트의 맨 뒤에 요소를 꺼내고 리스트에서 삭제함 a_list = [1,2,3] a_list.pop() => [1,2] print(a_list.pop()) 출력: 2 a_list : [1]
우선순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조입니다. 이 말은 내부적으로 데이터를 정렬된 상태로 보관하는 메커니즘이 있다는 뜻이고, 좀 더 구체적으로 얘기하면 heapq 모듈을 통해 구현되어 있습니다. 내부적으로 heap 모듈을 사용하는 PriorityQueue 클래스의 put(), get() 함수는 O(log n)의 시간 복잡도를 가집니다. 코드예시 from queue import PriorityQueue que = PriorityQueue() # que = PriorityQueue(maxsize=8) 디폴트사이즈는 무한대이..
정의 및 장단점 큐는 선입선출,FIFO(First In First Out)의 방식이다. 가정 먼저 들어온 데이터가 가장 먼저 나간다. 제일 먼저 들어온 데이터를 HEAD, 맨 뒤의 데이터를 TAIL이라고 한다. 구현방법 파이썬에서는 리스트방식 또는 라이브러리를 이용한 방식으로 나뉜다. 리스트방식: pop(0) 또는 insert(0,x)등의 방법은 복잡도가 O(n)이므로 아래의 다른 방법보다 불리하다. 리스트의 마지막 원소의 삭제는 O(1)이지만, 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)입니다. 자료구조 뒤에서 추가/삭제는 덱과 리스트는 속도 차이가 없지만, 첫번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생합니다. 데이터가 커지고 데이터의 양끝에서 ..
정의 및 장단점 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 현재 상황에서 지금 당장 좋은 것을 고르는 방법을 의미한다. 그리디 문제는 매우 다양한 문제가 있으며 미리 유형을 외우고 있지 않아도 알고리즘 문제를 풀 가능성이 높다. 그렇지만 많은 문제를 풀어보는 연습이 필요하다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 구현방법 보통 while문이나 조건문을 통해 구현이 된다. 문제 예시 그리디 문제의 대표적인 예시로 거스름돈 문제가 있다. 예를 들어 3800원을 거슬러줄 때 최소 지폐,동전수를 구하여라 등의 문제이다. n =1260 count = 0 coin_types = [..
https://happy-coding-day.tistory.com/entry/Template-Pattern템플릿-패턴-VS-Strategy-Pattern전략-패턴 Template Pattern(템플릿 패턴) VS Strategy Pattern(전략 패턴) Photo by Mike Meyers on Unsplash 들어가기 대부분의 디자인 패턴 책에서는 이 두가지를 비교해서 설명합니다. 왜 일까요? 이 두가지 패턴은 데이터를 은닉화 시켜 구현될 수 있도록 도와주는 패턴입니 happy-coding-day.tistory.com https://lion-king.tistory.com/entry/Spring-Design-pattern-Template-Strategy (Spring / Design pattern ) ..
트랜잭션이란? 트랜잭션(Transaction 이하 트랜잭션)이란, 데이터베이스의 상태를 변화시키기 해서 수행하는 작업의 단위를 뜻한다. 데이터베이스의 상태를 변화시킨다는 것은 무얼 의미하는 것일까? 간단하게 말해서 아래의 질의어(SQL)를 이용하여 데이터베이스를 접근 하는 것을 의미한다. SELECT INSERT DELETE UPDATE 착각하지 말아야 할 것은, 작업의 단위는 질의어 한문장이 아니라는 점이다. 작업단위는 많은 질의어 명령문들을 사람이 정하는 기준에 따라 정하는 것을 의미한다. 게시판을 예로 들어보자. 게시판 사용자는 게시글을 작성하고, 올리기 버튼을 누른다. 그 후에 다시 게시판에 돌아왔을때, 게시판은 자신의 글이 포함된 업데이트된 게시판을 보게 된다. 이러한 상황을 데이터베이스 작업으..
