컴린이 탈출기 ٩( ᐛ )و

[Today I Learned] # 이진 탐색 알고리즘 (이분 탐색) - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 시작점, 끝점, 중간점(소수점 이하 제거)을 이용해 탐색 범위 명시 + 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법- 연산 횟수는 log2N에 비례, 시간 복잡도는 O(logN) 보장 # 재귀적 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 if array[mid] == target: return mid elif array[mid] > target: return b..

[Today I Learned] 프로그래머스 고득점 Kit 정렬 문제가 레벨도 낮고 3문제 밖에 안되길래, 쭉 풀어봤다. 그에 앞서 파이썬 sort()와 sorted() 차이를 잘 모르겠어서, 간단히 공부했다. # sort() / sorted() - sorted()는 새롭게 정렬된 리스트를 return, 원래 리스트에는 영향을 주지 않음 -하지만 sort()는 리턴이 따로 없고 입력을 출력으로 덮어씀 - sorted()는 문자열에도 사용가능한것과 달리 sort()는 리스트에만 사용할 수 있음 - 어떤 기준으로 정렬할 것인지 아래와 같이 key 옵션을 지정할 수 있다 # 데이터의 길이를 기준으로 정렬 sorted(data, key=len) # 프로그래머스 - K번째수 문제 설명 배열 array의 i번째 숫..

[Today I Learned] # 프로그래머스 - 타겟 넘버 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 ..

[Today I Learned] # 이코테 - 음료수 얼려 먹기 문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다 입력 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1

[Today I Learned] # 스택 - 선입후출 자료구조 - Python에서는 List로 구현 stack = [ ] stack.append(5) # [5] stack.append(2) # [5,2] stack.pop() # [5] stack.append(1) # [5,1] stack.append(4) # [5,1,4] print(stack[::-1]) # 최상단 원소부터 출력 ; [4,1,5] print(stack) # 최하단 원소부터 출력 ; [5,1,4] # 큐 - 선입선출 자료구조 - Python에서는 Collections.deque(덱)으로 구현 - List로도 구현할 수 있지만 시간 복잡도 이슈. (특정 인덱스의 원소 꺼내는 pop 연산 후에, 전체적으로 인덱스 재조정하는 과정 필요.) f..

[Today I Learned] # 구현 - 풀이를 떠올리는 건 쉽지만 소스코드로 옮기기 어려운 문제들 - 2차원 공간 → 행렬(Matrix) 많이 등장 (파이썬은 2차원 리스트) - 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용됨 # 이코테 - 상하좌우 여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다.가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다.여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가이동할 계획이 적힌 계획서가 놓여 있다 계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D ..

[Today I Learned] # 그리디 알고리즘 (탐욕법) - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 - 일반적인 상황에서는 최적의 해를 보장할 수 없을 때가 많음 - 다만 코딩 테스트에서의 그리디 문제는 대부분 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨 ex. 거스름돈 문제 # 프로그래머스 - 체육복 https://programmers.co.kr/learn/courses/30/lessons/42862 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순..

[주절주절] 오랜만에 쓰는 글... 개강도 하고 부스트캠프 업무도 피크였다보니 그동안 글을 많이 못썼다. 오늘 부스트캠프 슬랙에 한 캠퍼님이 collate_fn의 역할이 무엇인지, 꼭 필요한지 모르겠다는 식의 질문을 남겨주셨는데, 나도 우리 베이스라인 코드를 작성하면서 비슷한 생각을 했었다. 그래서 오늘 조금 여유로운 김에 다른 마스터, 멘토님들이 달아주신 좋은 코멘트, 레퍼런스 참고해서 정리해보고자 한다. [Today I Learned] # Overview # sampler - Dataset은 idx로 데이터를 가져오도록 설계 되었다. 이 때 Sampler는 이 idx 값을 컨트롤하는 방법이다. - 따라서 sampler를 사용할 때는 shuffle 파라미터는 False가 되어야한다. - __len__과..

[주절주절] 주변 사람들한테 자주하던 한탄 중에 하나가 Residual block, Normalization, Pooling 등 몇몇 개념들이 머리로는 어느정도 알겠는데 가슴으로(?) 이해가 안된다는 것이다. 그런데 오늘(8/6) 연구실 스터디 준비하다가 Normalization 이야기가 나왔고, 다시 한 번 가슴으로 이해하는 것에 도전해보고자 대장정(?)을 시작하게 되었다. 오늘은 Batch Normalization으로 시작! [Today I Learned] # Gradient Vanishing / Exploding - Backpropagation : Loss 값을 최소화하는 방향으로 weight를 업데이트하는 방법. 다음과 같이 chain rule을 이용해 gradient를 계산한다. - 그런데, s..

[주절주절] 여름 휴가 후 복귀! 👼 [Today I Learned] # 파이썬 divmod : 매개변수로 숫자 두개를 입력 받아 몫과 나머지를 튜플 형태로 반환하는 함수 a = divmod(10, 3) print(a) >> (3,1) # 스택 - 후입선출(LIFO)로 처리 되는 자료구조 - 파이썬의 리스트가 스택의 모든 연산을 지원한다. - push : 요소를 컬렉션에 추가한다. - pop : 제거되지 않은, 가장 최근에 삽입된 요소를 제거한다. https://comlini8-8.tistory.com/82 ↑이 때도 공부했었다. + 연결리스트를 이용한 스택 ADT 구현 class Node: def __init__(self, item, next): self.item = item self.next = ne..