분류 전체보기
[26일차] TIL - Dynamic Programming
동적 계획법(Dynamic Programming) 동적계획법이란 복잡한 문제를 간단한 여러개의 문제로 나눠푸는 방법을 말합니다. 이것은 부분 문제반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용합니다. 재귀 알고리즘과 비슷해보이지만 결과를 매번 기록하여 연산을 중복하지 않기에 속도가 더 빠릅니다. 1. 퇴사 https://www.acmicpc.net/problem/14501 """ dp(n번째 날, 여태까지 번 돈) -> 근무를 한다면 dp(n + t, 여태까지번돈, + n번쨰날에 번돈) -> 근무를 안한다면 dp(n + 1, 여태까지번돈) """ n = int(input()) lst = [] for _ in range(n): # 소요일수, 돈 a, ..
[JavaScript] 자바스크립트 배열의 개념과 APIs 총정리 (8)
프로그래밍에서 비슷한 데이터들을 묶어서 보관하는 것을 자료구조 라고 합니다. 오브젝트와 자료구조의 차이는 오브젝트는 서로 연관된 특징과 행동들을 묶어 놓는 것을 말합니다. 비슷한 타입의 오브젝트들을 묶어놓는 것을 자료구조라고 합니다. 하지만 자바스크립트는 다른 타입의 오브젝트를 담을 수 있지만 역시 권장하지 않습니다. 1. Array declaration 배열은 다음처럼 정의할 수 있습니다. const arr1 = new Array(); const arr2 = [1, 2]; 2. Index position 배열은 다음과 같이 접근할 수 있습니다. const fruits = ['사과', '바나나']; console.log(fruits); // ['사과', '바나나'] console.log(fruits.le..
[JavaScript] 클래스와 오브젝트의 차이점, 객체지향 언어 클래스 정리 (6)
class 붕어빵을 만들 수 있는 틀, class로 찍어낸 것이 object입니다. es6 이전에는 class가 없었기 때문에 바로 object를 생성했습니다. 1. Class declaration 클래스를 다음과 같이 선언할 수 있습니다. class Person { // constructor constructor(name, age) { // fields this.name = name; this.age = age; } // methods speak() { console.log(`${this.name}: hello!`); } } Person이라는 클래스를 만들고 construtor 생성자를 이용해서 오브젝트를 만들 때 필요한 데이터를 전달합니다. 전달받은 데이터를 이 클래스에 존재하는 두가지 fields에..
[알고리즘 3주차] WIL - 힙, 정렬(버블, 선택, 삽입, 퀵, 머지, 힙)
Heap 완전이진트리로서 부모노드가 자식노드보다 크거나 작은 순서로 정렬되어있는 자료구조를 말합니다. 부모노드가 자식노드보다 작으면 최소힙이라고 부르고, 크면 최대힙이라고 부릅니다. 여기서 완전이진트리란 트리의 왼쪽부터 봤을 때 노드가 비어있지 않은 구조를 말합니다. 힙은 배열로 표현이 가능한데 루트노드를 1인 인덱스로 가정합니다. 루트노드를 중심으로 왼쪽 자식노드는 2 * 부모인덱스, 오른쪽 자식노드는 (2 * 부모인덱스) + 1 가 됩니다. 힙의 삽입 및 삭제에 대해서 알아보겠습니다. 최소힙을 기준으로 알아보겠습니다. 맨 위 루트 노드는 모든 노드중 가장 작은 노드가 될 것입니다. 삽입 이 트리에 어떠한 값을 append합니다. 그리고 부모노드와 비교해 가면서 자신의 자리를 찾아갑니다. 삭제 삭제는 ..
[23일차] TIL 이진 탐색(Binary Search) - (1)
이진탐색이란 정렬되어있는 배열에서 절반씩 줄여가며 탐색하는 기법입니다. 정렬되어있다는 전제가 필요하며 수행했을 시 1억 개 목록을 탐색한다면 27번 안에 찾을 수 있다. 직접 구현하는 방법도 있지만, 파이썬 내장함수인 bisect_left 를 사용해도 됩니다. bisect_right도 있지만 가장 많이 사용되는 것이 bisect_left 입니다. bisect_left는 target값의 index를 반환하는 반면 bisect_right는 index + 1값을 반환하게 됩니다. 따라서 특별한 경우가 아니라면 bisect_left를 가장 많이 사용하게 될것입니다. 1. leetcode 704 https://leetcode.com/problems/binary-search/ leetcode 704번 문제입니다. ..
[22일차] TIL - Week3 Test
1. H-Index https://programmers.co.kr/learn/courses/30/lessons/42747 처음에 대부분의 테스트를 통과하지 못했었는데 문제를 잘못 이해하고 있었습니다. h의 값이 반드시 citations배열에 존재 하지 않아도 된다는 것을 간과했습니다. 다음은 정답 판정 받은 풀이입니다. def solution(citations): answer = 0 citations.sort(reverse=True) lst = [i for i in range(max(citations))] lst.sort(reverse=True) for h in lst: lg = 0 sm = 0 for num in citations: if h = h: answer = h break return answe..
[알고리즘] 백준 1012 파이썬 풀이
유기농 배추 흔하게 보이는 문제 패턴입니다. 1은 배추가 있는 장소이고 배추가 붙어있다면 배추흰지렁이는 한마리가 필요합니다. 결국, 배추 무더기의 개수를 묻는 문제입니다. 처음 다음과 같이 풀이했습니다. t = int(input()) for _ in range(t): count = 0 m, n, k = map(int, input().split()) graph = [[0] * n for _ in range(m)] for _ in range(k): x, y = map(int, input().split()) graph[x][y] = 1 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] def dfs(x, y): if x = m or y >= n or grap..