티스토리

어제보다 한걸음 더

검색하기

블로그 홈

어제보다 한걸음 더

jian-nii.tistory.com/m

지안22 님의 블로그입니다.

구독자: 2

방명록 방문하기

주요 글 목록

[책] 누구나 자료구조와 알고리즘 - 15장 이진 탐색 트리로 속도 향상 (2/2) 삭제, 순회 https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 삭제 삭제는 이진 탐색 트리에서 가장 어려운 연산이기 때문에 주의 깊게 실행해야한다. 리프 노드(트리의 가장 끝 노드)를 삭제하게 되면 아무런 문제가 없다. 하지만 중간 노드를 삭제하게 되면 해당 서브트리의 노드의 재배치가 필요하다. 삭제 알고리즘의 규칙 삭제 할 노드에 자식이 없으면 그냥 삭제한다 삭제 할 노드에 자식이 하나면 .. 공감수 0 댓글수 0 2024. 1. 29.
[책] 누구나 자료구조와 알고리즘 - 15장 이진 탐색 트리로 속도 향상 (1/2) 검색, 삽입 https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 데이터를 자주 정렬해야 한다면 항상 정렬된 순서로 유지하는 것이 좋다. - 정렬 알고리즘은 아무리 빨라도 O(NlogN)의 시간이 걸리기 때문이다. 정렬된 배열은 읽기에는 O(1), (이진)검색에는 O(logN)으로 우수한 성능을 낸다. - 하지만 삽입, 삭제 시에는 O(N)이 걸리기 때문에 비교적 느리다. 해시 테이블은 O(1).. 공감수 0 댓글수 0 2024. 1. 22.
[책] 누구나 자료구조와 알고리즘 - 14장 노드 기반 자료 구조 https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 이어지는 장들에서 다룰 자료구조들은 모두 노드(node) 기반이다. 노드란 컴퓨터 메모리 곳곳에 흩어져있는 데이터 조각이다. 노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다. 연결 리스트의 효율성 면에서의 장단점(trade-off)를 알아보고, 성능이 크게 높아지는 상황도 알아 볼.. 공감수 0 댓글수 0 2024. 1. 15.
[책] 누구나 자료구조와 알고리즘 - 17장 트라이(trie)해 보는 것도 나쁘지 않다 https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 다음으로 읽을 단원은 14장 이지만, 트라이가 궁금해 17장 먼저 읽기로 했다. 정리 스마트폰의 자동완성(autocomplete) 기능은 어떻게 동작하는걸까? 전체 단어 사전에 접근했을 때, 정렬되지 않은 배열에서 찾는다면 O(N)이 걸리고, (N이 전체 단어 개수를 뜻하기 때문에 매우 느린 연산이다.) 해시 테이블도 O(1)으로.. 공감수 1 댓글수 1 2024. 1. 1.
[책] 누구나 자료구조와 알고리즘 - 13장 속도를 높이는 재귀 알고리즘 https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 퀵정렬(Quicksort)은 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘이다. 재귀를 사용함에도 불구하고 어떻게 알고리즘의 속도를 크게 향상시키는지 배우고, 실제 쓰이고 있는 다른 실용적인 알고리즘에도 똑같이 적용해볼 수 있다. 퀵정렬은 매우 빠른 정렬 알고리즘으로 특히 평균 시나리오에서 효율적이다. 최악의 시나리오(.. 공감수 0 댓글수 1 2023. 12. 18.
[책] 누구나 자료구조와 알고리즘 - 11장 재귀적으로 작성하는 법 https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 이번 장에서는 재귀 작성법에 대해 알아 볼 것이다. 재귀는 알고리즘의 시간 복잡도에 몹시 부정적인 영향을 미치지만, 우선은 재귀적 사고방식을 기르는 데 집중한다. 1. 재귀 카테고리: 반복 실행 - 상향식 재귀에는 다양한 "카테고리"가 존재한다. 어떤 카테고리에 효과적인 기법을 터득하면 같은 카테고리에 속하는 문제와 마주했을 때 .. 공감수 0 댓글수 0 2023. 12. 12.
[책] 누구나 자료구조와 알고리즘 - 10장 재귀를 사용한 재귀적 반복 https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 재귀(recursion)는 이후에 나올 보다 고급 알고리즘을 이해하기 위한 컴퓨터 과학의 핵심 개념이다. 재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어다. 잘못 사용하게 되면 무한재귀가 되어 전혀 쓸모없게 되지만, 올바르게만 활용하면 재귀는 강력한 도구가 될 수 있다. 루프 대신 재귀 루프 대신 재귀를 사용할 수 있다. 기저.. 공감수 0 댓글수 0 2023. 12. 4.
[책] 누구나 자료구조와 알고리즘 - 9장 스택과 큐로 간결한 코드 생성 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 스택과 큐는 제약을 갖는 배열이다. 운영체제 아키텍처, 출력 잡, 데이터 순회 등 임시 컨테이너로 사용해 뛰어난 알고리즘을 만들 수 있다. 이러한 스택과 큐는 임시 데이터를 처리하되 데이터를 처리하는 순서에 특히 중점을 둔다. 스택 Stack 스택에는 다음과 같은 세가지 제약이 있다. 데이터는 스택의 끝에만 삽입할 수 있다. 데이터는 스택의 끝에서만 삽입할 수 있다. 스택의 마지막 원소만 읽을 수 있다. 이미지 출처: ht.. 공감수 0 댓글수 0 2023. 12. 4.
[책] 누구나 자료구조와 알고리즘 - 8장 해시 테이블로 매우 빠른 룩업 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | product.kyobobook.co.kr 배열에서 특정 요소를 검색할 때, 정렬된 배열이면 O(logN), 정렬되지 않은 배열이면 O(N) 단계가 걸린다. 이 때, 해시 테이블을 사용하면 O(1) 만에 데이터를 룩업할 수 있다. 해시 테이블 해시 테이블은 쌍(key, value)으로 이뤄진 값들의 리스트이다. 해시 , 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다. 해시 함수를 이용하여 key를 해싱한다. 이 해싱 된 key의 값이 value가 저장될 위치를 결정한다. 때문에 key로 검색 시, O(1)의 성능을 가진다. value로 검색 시에는 일반 배열과 동일하게 O(N)의 성능을 가진다. 언어에 .. 공감수 0 댓글수 2 2023. 11. 27.
[책] 누구나 자료구조와 알고리즘 - 12장 동적 프로그래밍 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | product.kyobobook.co.kr 원래 8장 해시테이블 부터 읽어야됐는데 포스트잇이 잘못 붙어있어서 실수로 건너뛰고 읽었습니다..ㅎㅎ.. 하지만 그래도 읽으면서 크게 이질감 드는 부분이 없어서 확실히 읽기 좋은 책이다 싶었습니다! 정리 1번 상황 - 배열에서 최대 값 구하기 재귀 호출 시, 불필요한 재귀 호출이 일어나는 경우가 있습니다. def max(array) // 배열의 크기가 1이라면 첫번째 요소 반환 return array[0] if array.length == 1 if array[0] > max(array[1, array.length - 1]) return array[0] else return .. 공감수 0 댓글수 1 2023. 11. 11.
[책] 누구나 자료구조와 알고리즘 - 7장 일상적인 코드 속 빅 오 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | product.kyobobook.co.kr 이번 장에서는 여러가지 상황에서 빅 오 표기법을 사용해 시간 복잡도를 계산하는 방법을 알려준다. 상황 1 : 짝수의 평균 문제: 배열에서 모든 짝수의 평균을 반환할 때의 빅 오 표기법을 사용해 시간 복잡도를 구한다. 평균 = 짝수의 합 / 짝수의 개수 메서드로 전달 된 수 배열 == 데이터 원소 N (N은 배열의 크기) 짝수의 합, 짝수의 개수를 담을 변수를 각각 만든다. (2) 루프를 돌면서 원소를 순회한다. (N) 짝수라면 짝수의 합에 더한다 (N) 짝수의 개수를 늘린다. (N) 짝수의 평균을 구하기 위해 나누기를 수행한다. (1) 2.에서 최악의 경우 배열의 모든 .. 공감수 0 댓글수 3 2023. 10. 28.
[책] 누구나 자료구조와 알고리즘 - 6장 긍정적인 시나리오 최적화 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | product.kyobobook.co.kr 사담 정리하는 습관을 들이고자 책을 읽고 내용을 정리하는 스터디를 시작하게 되었다. 이전까지의 내용은 시간이 되면 다시 정리하기로 하고, 지금부터 읽은 내용들부터라도 차근차근 정리하려고 한다. 정리 이전 장(챕터)까지 버블 정렬, 선택 정렬에 대한 알고리즘 효율성을 알아봤다. 두 정렬 알고리즘 모두 최악의 경우에 O(N^2)를 가지지만, 선택 정렬의 경우는 O(N^2 / 2)를 가지므로 약간 더 빠르다는 사실을 알 수 있었다. (하지만 빅오 표기법에서는 상수를 제거하므로 선택 정렬도 최악의 경우 O(N^2)가 정확한 표기법이기는 하다) 이번 장(챕터)에서는 삽입 정렬까지 .. 공감수 1 댓글수 3 2023. 10. 21.
BOJ 백준 14499번, 주사위 굴리기 - Python 파이썬 문제: https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 알고리즘 유형은 구현 문제로, 문제 자체가 어렵진 않았지만 코드로 정리하는데에는 오래 걸렸다. 처음 제출한 코드가 조금 아쉬워서 다른 사람이 봐도 이해하기 쉽도록 리팩토링을 진행했다. import sys input = sys.stdin.readline # (지도의)세로, 가로, (주사위의)x, y, 명령어 개수 N, M, x.. 공감수 0 댓글수 2 2023. 6. 14.
네트워크 - 허브, 스위치, 라우터, WAP, 인터넷 공유기 차이 허브 hub LAN에서의 연결된 포트 간의 통신(데이터 교환)을 가능하게 해준다. 그러나 허브는 특정 포트를 구별할 수 없기 때문에, 연결된 모든 포트에 브로드 캐스팅을 보내게 되어, 1. 보안 문제가 생긴다 2. 불필요한 트래픽이 발생하여 대역폭이 낭비된다. - 포트: Process 식별자 - 브로드 캐스팅: 모두에게 동일하게 메세지를 보내는 기능 스위치 switch 허브와 기능은 동일하지만, 각 포트의 물리적 주소(MAC주소)를 학습할 수 있어 특정 포트를 지정하여 데이터를 전달할 수 있다. 라우터 Router 허브와 스위치는 IP주소를 읽을 수 없어 LAN 내에서의 통신만 가능하다. 하지만 라우터는 IP주소를 읽을 수 있어 다른 네트워크와의 통신(WAN)도 가능하다. 라우터는 네트워크의 게이트웨이다.. 공감수 0 댓글수 1 2023. 6. 8.
BOJ 백준 4485번, 녹색 옷 입은 애가 젤다지? - Python 파이썬 문제: https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 요새 젤다의 전설 왕국의 눈물 재밌게 하고 있는데 이런 문제가 있어서 냉큼 풀어보게 되었다.ㅎㅎ 이 문제는 BFS나 다익스트라(테이크스트라)로 풀 수 있는데, 다익스트라에 익숙하지 않아서 처음에는 BFS와 섞어서 문제를 풀게 되었다. # 첫번째 제출 코드 import sys from collections import deque input = sys.stdin.readlin.. 공감수 0 댓글수 0 2023. 6. 2.
BOJ 백준 14235번, 크리스마스 선물 - Python 파이썬 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 문제: https://www.acmicpc.net/problem/14235 알고리즘 분류는 자료구조, 우선순위 큐 였다. 문제에서는 Max-heap 정렬을 요구했지만, 파이썬에서 제공하는 모듈인 heapq를 사용할 경우에 정렬은 min-heap 이었다. 때문에 heapq에 선물을 저장 할 때에는 양수인 우선순위를 음수로 바꿔 min-heap으로 정렬되게 하고, 꺼낼 때는 음수를 다시 양수로 변환해서 출력해줬다. 파이썬에서는 음수 -> 양수로 바꿀 때 그저 하이픈(-.. 공감수 0 댓글수 0 2023. 4. 5.
BOJ 백준 13335번, 트럭 - Python 파이썬 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제: https://www.acmicpc.net/problem/13335 import sys # queue 보다 사용 가능한 메서드가 더 많은 deque를 사용했다. from collections import deque input_line = sys.stdin.readline n, w, L = list(map(int, input_line().rstrip().split())) trucks = deque(list(ma.. 공감수 0 댓글수 0 2023. 4. 5.
BOJ 백준 1244번, 스위치 켜고 끄기 - Python 파이썬 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 문제: https://www.acmicpc.net/problem/1244 import sys # 실패 # 20개 단위로 끊어서 출력하는 요구사항 파악을 못하는 실수가 있었다. def switch_switch(switches, i): if switches[i] == 0: switches[i] = 1 elif switches[i] == 1: switches[i] = 0 def male_switch_control(switches, receive_n, switch.. 공감수 0 댓글수 0 2023. 3. 28.
BOJ 백준 1149번, RGB 거리 - Python 파이썬 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제: https://www.acmicpc.net/problem/1149 import sys n = int(sys.stdin.readline().rstrip()) dp = [[0]*3 for _ in range(n+1)] for i in range(1, n+1): R_0, G_1, B_2 = list(map(int, sys.stdin.readline().rstrip().split())) dp[i][0] = R_0 + min(dp[i-1][1.. 공감수 0 댓글수 0 2023. 3. 28.
BOJ 백준 2579번, 계단 오르기 - Python 파이썬 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제: https://www.acmicpc.net/problem/2579 # 실패 # 1. 점화식 수정 # 2. 작은 수를 넣었을 때 dp와 stairs 생성이 불가, 런타임 에러가 나서 수정 n = int(input()) dp = [0] * n # stairs = [] # for i in range(0, n): # stairs.append(int(input())) stairs = [int(input()) for _ in range(n)] if n 공감수 0 댓글수 0 2023. 3. 28.
BOJ 백준 1063번, 킹 - Python 파이썬 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 문제: https://www.acmicpc.net/problem/1063 # 1063번 킹 import sys def position_calculate(position, moves): column_index = column.index(position[0]) + move_calculate_column(moves) row_index = row.index(position[1]) + move_calculate_row(moves) if (0 공감수 0 댓글수 0 2023. 3. 28.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.