목록2024/03 (15)
Seung's Learning Record
코딩 테스트 종류Implementation : 제시된 흐름에 따라 실행하는 코드를 만들도록 요구Algorithm comprehension : 문제의 효과적/효율적 해법을 찾아내도록 요구Competency test : 특정한 자료구조와 알고리즘을 착안하여 제한시간 내에 풀도록 요구etc : 특정한 언어 구문을 활용할 수 있는지를 테스트 (SQL)어떤 대비가 필요할까?구현 능력 갖추기 : 아주 당연한 얘기지만 그만큼 필수적이기도 하다. 적어도 하나의 프로그래밍 언어에 능숙해져야한다.기본적인 자료구조 이해 : Array, Stack/Queue, Hash, Tree, Graph,... 등등 여러 자료구조 익숙해지기기초 알고리즘 및 시간/공간 복잡도에 대한 이해 : 문제를 읽고 어떤 접근방법을 택할지 선정하는것이..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/ex5DSM/btsGazn8f7u/DZNEcrpNLW8mEp0jqdknr0/img.png)
사용한 풀이법 : heap 풀이 과정 최소값과 그 다음값을 탐색, 계산 후 다시 삽입 => 해당 연산이 조건을 충족할 때 까지 반복되어야 함. 이를 위한 자료구조가 바로 최소힙! 1. heapify 메서드를 통해 scoville 리스트를 최소힙으로 초기화 2. 항상 최소값을 뽑아내는 heappop 연산을 통해 min1, min2를 설정 이때, min1이 k이상이거나, 더 이상 뽑아낼 원소가 없을때는 반복문 종료 3. 삽입할 원소를 계산 후, 힙에 push 4. 연산이 완료 될 때마다 +1한 answer를 리턴 풀이 코드 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) while True: min1 = heapq.heap..
≣ 목차 PEP8 스타일 PEP 8 PEP8 : 파이썬 개선 제안서, 파이썬 코드를 어떻게 구상할 지 알려주는 스타일 가이드 PEP8 전체 가이드 다른 사람과 원활하게 협업하려면 공통된 스타일 공유가 필요 일관성 있는 스타일은 나중에 수정하기도 쉽다. whitespace 한 줄의 문자 길이가 79자 이하여야 한다. 함수와 클래스는 빈 줄 두개로 구분한다. 클래스에서 메서드는 빈 줄 하나로 구분한다. 변수 할당 앞 뒤에 스페이스를 하나만 사용한다. 리스트 인덱스, 함수 홏ㄹ, 키워드 인수 할당에는 스페이스를 사용하지 않는다. naming 함수, 변수, 속성 : lowercase_underscore 보호(protected) 인스턴스 속성 : _leading_underscore 비공개(private) 인스턴스..
≣ 목차 큐 큐 자료를 보관할 수 있는 선형 구조로 push(enqueue)와 pop(dequeue)이 반대에서 이루어지기 때문에 선입선출(FIFO)방식을 채택한 자료구조이다. 큐는 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어날 때 사용된다. 또한 자료 생성이 여러 곳에서 발생하거나, 자료 이용이 여러 곳에서 발생할 때 사용된다. 스택과 마찬가지로 큐 역시 배열(리스트)과 연결 리스트(이중 연결 리스트)를 이용하여 구현가능하다. 연산 종류 설명 배열 시간 복잡도 연결 리스트 시간 복잡도 size() 현재 큐에 들어 있는 데이터 원소 수 반환 O(1) O(1) isEmpty() 현재 큐가 비어 있는지 판단 O(1) O(1) enqueue() 원소 x를 큐에 push O(1) O(1)..
≣ 목차 리스트 파이썬에는 다른 언어들에서 다뤄지는 배열과 유사한 성질의 리스트(list)라는 자료구조가 존재한다. 동일한 자료형만 가질 수 있는 배열과는 달리, 리스트는 다양한 자료형을 하나의 리스트 안에 담을 수 있다. 선언 방법 a = [1,2,'a','b',"xyz"] b = [] c = list() d = [0]*10 #[0,0,0,0,0,0,0,0,0,0] e = [i*2 for i in range(5)] #[0,2,4,6,8] 리스트는 위와 같은 다양한 방법을 통해 선언이 가능하다. 연산 a = [1,2,3] b = ['a','b','c'] c = a+b #[1,2,3,'a','b','c'] d = a*3 #[1,2,3,1,2,3,1,2,3] e = a*0 #[] 이처럼 리스트 사이의 덧셈이..
≣ 목차 해시(Hash) 해시 개념 해시란 해시 테이블에 Key와 Value를 매핑해서 데이터를 저장하는 자료구조이다. 주로 데이터 탐색, 삽입, 집계등의 연산을 할때 유용하며, 인덱스 값이 숫자가 아닌 문자열이나 튜플을 때도 유용하다. 하지만 최댓값과 최솟값을 찾는 문제는 자료구조 전체를 탐색해야 하기 때문에 효율성이 떨어진다는 단점이 있다. 해시 (Hash) : 임의 값을 고정 길이로 변환하는 것 해시 테이블 (Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수 (Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해시 값 (Hash Value) 또는 해시 주소 (Hash Address) : Key를 해싱 함수로..
≣ 목차 트리 트리 정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조로, 순환하는 길이 없는 그래프라고 말할 수 있다. 루트 노드 (root node) : 트리의 최상단 노드 리프 노드 (leaf nodes) : 트리의 최하단 노드 내부 노드 (internal nodes) : 루트와 리프 사이에 위치한 노드 부모 (parent) 노드와 자식 (child) 노드 : 정점의 바로 위 노드가 부모 노드, 바로 아래 노드가 자식 노드 (부모의 부모는 조상노드, 자식의 자식은 후손 노드) 노드의 수준 (level) : root로 부터 각각의 노드까지 도달하기 위해 거쳐야하는 간선의 수 (root = level 0) 노드의 차수 (degree) : 자식 노드의 수 트리의 높이 (..
≣ 목차 연결 리스트 연속된 공간에 데이터를 저장하는 방식인 리스트와는 다르게 연결 리스트(linked list)는 연속적이지 않는 공간에 데이터를 줄줄이 엮어서 저장한다. 연결 리스트는 일반적인 리스트보다 특정 원소의 삽입/ 삭제가 수월하다는 장점이 있지만, 특정 원소를 탐색하는 시간이 길고 요구되는 메모리 공간이 더 크다는 단점이 있다. 따라서 각각의 상황이 요구하는 자료구조를 제대로 파악해서 적절하게 사용하는 능력을 키우는것이 중요하다. 연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다. 단일 연결 리스트 - 각 원소가 자신의 다음 원소 주소를 들고 있는 구조 이중 연결 리스트 - 각 원소가 자신의 이전, 다음 원소 주소를 들고 있는 구조 c++에서 제공하는 ST..
≣ 목차 알고리즘 시간 복잡도 알고리즘을 풀때는 제한 시간내에 코드가 실행 완료되는것이 중요하다. 이를 위해 우리는 알고리즘의 시간복잡도와 공간 복잡도가 어떠한가를 미리 파악한 후 이에 맞는 문제 풀이 방법을 생각해내야 한다.이러한 복잡도를 표현하는 방법 중 가장 흔히 사용되는 방법은 빅오 표기법(big-O notation)이다. 이에 관한 설명은 아래 링크에 자세히 작성되어 있다. https://seung2344.tistory.com/22 리스트 파이썬에는 다른 언어들에서 다뤄지는 배열과 유사한 성질의 리스트(list)라는 자료구조가 존재한다. 동일한 자료형만 가질 수 있는 배열과는 달리, 리스트는 다양한 자료형을 하나의 리스트 안에 담을 수 있다. 선언 방법 a = [1,2,'a','b',"xyz"]..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/djMyEi/btsFKN0ssDY/kXvkgRwLp2kZVCkWDJWKq1/img.png)
난이도 : 실버2 소요시간 : 27m 사용한 풀이법 : DP 풀이 과정 입력받은 문자열을 정수형 리스트 arr[]로 변환 dp[]에는 해당 인덱스에서 가질 수 있는 최대값을 넣는다 dp[i-1]+arr[i]가 음수일 경우 최대값 생성에 방해가 되므로 해당 dp값은 0으로 초기화 원래는 여기서 풀이를 끝낼라했는데 모두 음수일 경우를 고려안하게 생각나서 dp첫번째 조건문 뒤에 arr값을 dp값으로 초기화 해주는 코드 추가 ⇒ 내가 생각해도 좀 후진 코드..ㅎ 원래는 max(dp)를 하려했으나 위 코드 추가되면서 max(arr)로 변경 다른 풀이 입력받은 문자열을 정수형 리스트 arr[]로 변환 현재합과 최대합 연산용 변수 선언 arr을 돌면서 해당 인덱스와 해당 인덱스에 현재합을 더한 것중 max를 현재합에..