[BOJ] 백준 10815 숫자 카드 / 이분탐색

💭 문제 이해 사실 이분탐색 문제인데, set 자료구조를 사용해서 in 연산자를 쓰면 원소를 찾는데 O(1) 밖에 안걸린다는 점이 너무나 매력적이다. 구현도 엄청 간단하게 하면서 시간도 겁나 빠르다니... 그래서 이번에도 set과 in 연산자를 이용해서 풀었다:) 구현 언어: Python import sys r = sys.stdin.readline def solve(my_cards: set, num_list: list) -> list: result = [] for num in num_list: result.append(1 if num in my_cards else 0) return result n, my_cards = int(r()), set(map(int, r().split())) m, num_list..

→2021.02.09

[BOJ] 백준 2805 나무 자르기 / 이분탐색

💭 문제 이해 자를 수 있는 최소 높이인 1 부터 max(나무의 높이 배열) 사이에서 최소 m미터 길이의 나무를 가져가기 위해 이분탐색을 진행하며 m을 찾아나가는 문제이다. 자른 나무 길이의 합을 구하기 위해 최악의 경우 100만 번의 sum 연산이 log(109) 만큼 반복된다. 이 풀이도 시간 초과가 발생하지는 않지만 Counter를 사용해서 100만 번의 연산을 감소시켜 시간을 줄이는 풀이를 찾게 되었다. 구현 언어: Python 1. 내 풀이 import sys r = sys.stdin.readline def binary_search(m, trees): answer = 0 left = 1 right = max(trees) while left = mid else 0, trees)) if total_..

→2021.02.09

[BOJ] 백준 1920 수 찾기 / 이분탐색

💭 문제 이해 두 개의 정수 리스트 a, b가 주어지고, b의 모든 원소를 비교하며 a에 존재하는 지 여부를 1과 0으로 출력하는 문제이다. 문제 자체는 간단하지만 완전탐색을 수행하면 105 * 105 = 1010 으로 시간 초과가 발생하게 된다. 이 문제는 두 가지의 해결 방법이 있다. 1. 이분 탐색을 통해 리스트 b에서 원소를 탐색하는 시간을 log(n)으로 줄인다. 2. set()의 in 연산자는 O(1)의 시간이 걸린다는 특징을 이용하여 리스트 b를 set으로 입력받은 후, in 연산자로 탐색한다. https://twpower.github.io/120-python-in-operator-time-complexity 구현 언어: Python 1. Binary Search import sys r = ..

→2021.02.09

[BOJ] 백준 9205 맥주 마시면서 걸어가기 / BFS

💭 문제 이해 맨해튼 거리로 계산해서 1000미터 이내에 편의점이 있다면 맥주를 20병으로 갱신할 수 있다. 편의점 좌표 또는 페스티벌 좌표가 들어있는 리스트를 탐색해서 1000미터 내에 있다면 queue에 넣고, 만일 그 좌표가 페스티벌 좌표라면 도착했다는 결과로 "happy"를 출력하고 종료한다. BFS 연산을 위한 queue가 비어서 while 문이 종료되었다면, 가진 맥주 20병으로는 도달할 수 없다는 뜻으로 "sad"를 출력하게 된다. 구현 언어: Python import sys from collections import deque r = sys.stdin.readline def distance(n_x, n_y, x, y): return abs(n_x - x) + abs(n_y - y) def ..

→2021.02.08

[AI Math] 경사하강법

미분 미분(differentiation)은 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구로, 최적화에서 제일 많이 사용하는 기법이다. In [6]: import sympy as sym from sympy.abc import x sym.diff(sym.poly(x**2 + 2*x + 3), x) Out[6]: $\displaystyle \operatorname{Poly}{\left( 2 x + 2, x, domain=\mathbb{Z} \right)}$ 미분은 함수 f의 주어진 점(x, f(x)) 에서의 접선의 기울기를 구한다. 한 점에서 접선의 기울기를 알면 어느 방향으로 움직여야 함수값이 증가/감소하는지 알 수 있다! 증가시키고 싶다면 미분값을 더하고, 감소시키고 싶다면 미분값을 뺀다. 경사..

→2021.01.26

[Python] Handling (Exception, File, Directory, Data)

아래의 본문은 부스트캠프 AI Tech 1기 수강 중에 작성한 학습 기록입니다🙂 1. Exception Handling(예외 처리) 1) try ~ except 구문 exceptions이 발생한다고 프로그램이 종료하는 것이 아니다. 그 부분만 에러 메시지를 출력하고 다음 작업을 수행한다. # 0으로 숫자를 나눌 때 예외처리 하기 for i in range(10): try: print(10 / i) except ZeroDivisionError: print("Not divided by 0") except 구문을 더 추가할 수 있다. a = [1, 2, 3, 4, 5] for i in range(10): try: print(i, 10 // i) except ZeroDivisionError: print("Not..

→2021.01.22

[Python] Python의 자료구조

Stack, Queue, List, Dict 등 Python의 자료구조와 collections 패키지의 모듈을 간단히 배웠다. 코테 문제를 풀면서 이미 자주 사용하고 있는 것들이지만, 1주차에서 Python에 대해 좀 더 꼼꼼히 배우면서 다른 컴파일 언어들을 공부할 때처럼 좀 더 깊게 찾아보게 되는 것 같다. 화요일 쯤부터 피어세션 팀원 분들과 Python에서 변수/객체/generator 등의 메모리 할당이 어떤 식으로 이루어지는지 고민하고 공부하면서 블로그 정리가 조금 밀렸다. (+ 화, 목 과제까지..) 이전까지 다루었던 언어들과 또 다른 재미가 있어서 보람차다. 공부하면서 알게 된 것들은 주말을 활용해서 정리해야겠다! 💭 List의 rotate 메소드를 활용하면 원형큐 관련 문제도 풀 수 있을 것 ..

→2021.01.21

[Python] Immutable 객체와 Mutable 객체

Everything is object in Python. Python 메모리 관리 부스트캠프 AI Tech 1기에서 강의를 듣던 중 Python의 변수 할당과 ==와 is 비교 연산자에 대해 배우게 되었다. 변수에 값을 할당할 때 또는 매개변수로 값을 전달할 때, Python은 C/C++ 또는 Java의 방식과 뭔가 다르다는 점을 깨닫게 되었다. 궁금한 점을 찾아보다가 얼떨결에 Python의 메모리 관리 방식에 대해 빡공을 하게 되었다. 뭔가 다르다는 것은 알겠는데 이해가 잘 되지 않아서 피어 세션 때 팀원 분들과 함께 이야기해보게 되었고, Python의 Mutable 객체와 Immutable 객체에 대해 듣게 되었다. 그리고 개인 학습 시간에 추가적으로 Python의 메모리 관리에 대해 찾아보면서 상당..

→2021.01.19

[BOJ] 백준 2573 빙산 / BFS

💭 문제 이해 한 덩어리의 빙산이 입력으로 주어진다. 매년, 빙산의 사방으로 접한 바다면(0)의 개수만큼 녹아내린다. 해마다 녹아내리다보면 어느 시점에 빙산이 끊어지며 덩어리가 나뉘게 된다. 예제 입력의 경우 2년이 지나면(두 번 녹으면) 덩어리가 세 덩어리로 나누어진다. 몇 년이 지나면 빙산이 두 덩어리 이상으로 나누어지는지 계산하는 문제이다. 1. 빙산을 녹인다. 2. 너비 우선 탐색을 하며 덩어리 개수를 세본다. 3. 두 덩어리 이상으로 나뉘거나, 더 이상 남은 빙산이 없다면 그 결과를 출력한다. ❗️여기서 내가 놓쳤던 포인트는 빙산을 현재 기준으로 녹이면 잘못 계산한다는 점이다. 무슨 말이냐면,, - 먼저 (1, 1) 위치의 높이 2인 빙산은 왼쪽과 위쪽이 바닷물이므로 1년이 지나면 모두 녹아 0..

→2021.01.14

[BOJ] 백준 2468 안전 영역 / BFS

💭 문제 이해 2차원 배열에 각 원소는 그 지역의 높이를 담고 있다. 물 높이가 증가함에 따라 일부 지역은 잠기게 되고, 잠기지 않은 연속된 지역을 안전영역이라 한다. 물 높이의 변화에 따라 안전영역의 개수도 변하게 되는데, 이 안전영역 개수의 최대값을 구하는 문제이다. 2차원 배열의 최대 크기는 100*100으로 전수조사를 해도 10000번 밖에 되지 않는다. 1. 현재 전체 영역의 최소 높이~최대 높이 범위 내에서 탐색을 시작한다. 2. 전체 영역에서 (0, 0) 위치부터 출발해서 현재 물 높이 기준보다 높고, 방문한 적 없는 곳을 만나면, 거기서부터 너비 우선 탐색을 수행하며 방문체크를 한다. 그리고 현재 물 높이에서의 안전영역 개수를 1 증가시킨다. 3. 모든 영역을 탐색했으면 현재 물 높이 기준..

→2021.01.13