-
Leetcode 684. Redundant Connection https://leetcode.com/problems/redundant-connection/description/?envType=daily-question&envId=2025-01-29 In this problem, a tree is an undirected graph that is connected and has no cycles.You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already exist.. -
알고리즘 공부 KMP 문자열 패턴매칭 알고리즘인 KMP 알고리즘입니다. 아호코라식 공부한지 꽤 시간이 지났는데, 그동안 KMP는 정리하지 않다가 이제야 글을 쓰네요 ㅎㅎ 노션에 정리한 글을 붙여넣은거라, 내용이 조금 깨져있어서 보기 힘드실 수 있습니다. 노션 링크를 참고해주세요! https://hollow-cushion-33f.notion.site/KMP-04882b3843c84c099eb343ab683a9b0b KMP Knuth-Morris-Pratt Algorithm Naive한 문자열 매칭의 시간 복잡도? 패턴 문자열의 길이를 M, 주어진 문자열의 길이를 N이라고 할 때, **시간복잡도 : O(NM)** inputString = "aaaaaa" targetString = "aa" matchList = [] for i i..
-
Leetcode [Leetcode Medium] 1268. Search Suggestions System Search Suggestions System - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com You are given an array of strings products and a string searchWord. Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products sh..
-
BOJ (Baekjoon Online Judge) [BOJ Gold 4] 1581 락스타 락동호 1581번: 락스타 락동호 한국이 낳은 세계적인 락스타 락동호는 2007년 2월 1일 역대 최대 규모의 콘서트를 열었으며, 2007년 2월 11일에 자신의 음악세계를 세상에 알리고, 2007년 3월 4일에는 자신의 작곡 비법을 세계에 공 www.acmicpc.net 문제 한국이 낳은 세계적인 락스타 락동호는 2007년 2월 1일 역대 최대 규모의 콘서트를 열었으며, 2007년 2월 11일에 자신의 음악세계를 세상에 알리고, 2007년 3월 4일에는 자신의 작곡 비법을 세계에 공개했다. 하지만, 그 후 락동호는 음악을 접고 체스에 입문하게 되었고, 그 결과 2007년 3월 31일 Heroes원정대에서는 체스 부분으로 참가하게 된다. 그 후 절대로 음악을 하지 않을 것 같았지만, 모두의 예상을 깨고, 200.. -
Leetcode [Leetcode Hard] 745. Prefix and Suffix Search Design a special dictionary with some words that searchs the words in it by a prefix and a suffix. Implement the WordFilter class: WordFilter(string[] words) Initializes the object with the words in the dictionary. f(string prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the l..
-
독학사 [독학사] 독학사 컴퓨터 공학 2과정 합격 후기 회사 일정과 독학사 시험 준비로 일이 바빠 오랜만에 글을 씁니다. 고등학교 졸업 후 바로 반도체 관련 회사에 설비 엔지니어로 입사한 후, 군 병특 및 개발 직군으로의 진로 변경을 위해 독학사 컴퓨터공학과 시험을 준비하게 되었습니다. 8과목 전 과목을 응시했지만, 시간이 부족해 웹 프로그래밍은 공부하지 못한 채로 시험을 보았습니다. 먼저 결과부터 말씀드리면, 8과목 중 웹프로그래밍을 제외한 7과목을 합격해 2과정을 통과하게 되었습니다. (과목별 90~80점 취득 ) 독학사 2과정 설명 / 난이도 2과정은 총 8과목으로 이루어져 있고, 이 중 6과목 이상이 60점을 넘겨야 통과하게 됩니다. 이산수학 | 쉬움 컴퓨터 구조 | 약간 어려움 운영체제 | 어려움 논리회로 | 쉬움 자료구조 | 쉬움 웹프로그래밍 | ..
-
BOJ (Baekjoon Online Judge) [BOJ Gold 2] 16724 피리 부는 사나이 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 문제 피리 부는 사나이 성우는 오늘도 피리를 분다. 성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다. 이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 ..
-
BOJ (Baekjoon Online Judge) [BOJ_Gold3] - 2904 수학은 너무 쉬워 [python] 2904번: 수학은 너무 쉬워 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다. www.acmicpc.net 문제 상근이의 할머니는 매우 유명한 수학자이다. 할머니는 매일 수학 문제로 상근이를 힘들게 한다. 할머니는 종이 N장에 숫자를 하나씩 쓴 다음 상근이에게 준다. 그 다음 상근이는 다음과 같이 문제를 풀어야 한다. 두 수 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음, A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다. 상근이는 위의 행동을 무한히 반복할 수 있다. 할머니는 상근이가 만든 수를 보고 점수를 계산한다. 점수가 높을수록 할머니는 상근이에게 사탕을 많..
-
Leetcode [Leetcode Medium] 934. Shortest Bridge You are given an n x n binary matrix grid where 1 represents land and 0 represents water. An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid. You may change 0's to 1's to connect the two islands to form one island. Return the smallest number of 0's you must flip to connect the two islands. Example 1: Input: grid = [[0,1],[1..
-
자료구조 [자료구조] 힙 | Heap 공유된 코드 - Color Scripter colorscripter.com 힙, 힙트리는 부모 노드가 자식 노드보다 우선순위가 높은 값을 가지고있음이 보장되는 힙구조로 이루어진 트리형태의 자료구조입니다. 이 정의를 가지고 귀납적으로 생각해보면, 루트노드에 담겨있는 값이 항상 우선순위가 가장 높은 값임을 알 수 있습니다. 또, 균형 이진트리 형태를 항상 유지하므로, 값의 삭제 및 삽입을 항상 O(logN)시간복잡도 내에 할 수 있음이 보장됩니다. 이러한 힙트리의 특성을 활용해, 다익스트라(Dijkstra), 힙 정렬(Heap Sort)등을 수행할 수 있습니다. 위 링크는 힙트리를 개인적으로 구현한 소스코드입니다.
-
자료구조 [자료구조] 세그먼트 트리 | Segment Tree 세그먼트 트리(Segment Tree)란? 세그먼트 트리는 어떤 구간에 대한 정보(특정 구간에서의 최대/최솟값, 평균, 합 등)를 각각의 노드가 저장하고 있다는 특성을 이용해, O(logN)의 시간복잡도로 구할 수 있게 해주는 자료 구조입니다. 구현의 편의를 위해, 완전 이진트리 형태로 구현하였습니다. 먼저, 전체적인 구조는 아래와 같습니다. 주어진 노드(BaseNodes)의 개수 $N$에 대해 $N < X$를 만족하는 가장 가까운$2^N$값 X에 대해, 세그먼트 트리의 루트노드는 구간 [0,X]까지의 BaseNodes의 세그먼트 값(합)을 의미합니다. 또한, 이 BaseNode의 자식들은 각각 구간[0,X//2),[X//2,X)의 합을 저장하고 있습니다. 이러한 세그먼트 트리의 특성을 잘 이용하면, 우.. -
자료구조 [자료구조] 희소 행렬 | Sparse Matrix 희소행렬, Sparse Matrix는 대부분의 값이 0으로 이루어진 행렬을 뜻합니다. 2차원 배열로 희소 행렬을 구현하는 경우, 간단하게 연산을 구현할 수 있지만, 대부분의 공간이 0으로 채워져있어 공간의 낭비가 심합니다. 때문에, 이를 0이 아닌 값으로 채워진 곳의 위치 (행,열,값) 만을 저장하는 방식으로 변형하면, 메모리 공간을 절약할 수 있게 됩니다. 다만, 이로인해 각종 행렬 연산들의 구현이 복잡해지게됩니다. -
자료구조 [자료구조] 연결 리스트를 이용한 큐 / 스택의 구현 | Linked Queue & Stack 앞서 설명한 링크드 리스트를 이용해, 큐와 스택을 그대로 구현할 수 있습니다. 연결 큐의 구현은 다음과 같습니다. 링크드 리스트의 맨 앞에 위치한 노드를 Front, 맨 뒤에 위치한 노드를 Rear라고 했을 때, Dequeue는 기존 Front의 다음에 있는 노드를 새로운 Front로, Enqueue는 기존 Rear 다음에 새로 추가된 노드를 Rear로 변경하는 방식으로 구현합니다. 연결 스택의 구현은 다음과 같습니다. 링크드 리스트의 맨 앞에 위치한 노드를 Top, 맨 뒤에 위치한 노드를 Bottom라고 했을 때, Pop은 기존 Top의 다음에 있는 노드를 새로운 Top으로, Push는 새로 추가된 노드를 Top으로 변경하고, 포인터를 기존 Top과 연결하는 방식으로 구현합니다.
728x90