본문 바로가기

분류 전체보기

 (147)
Baekjoon 7453. 합이 0인 네 정수 / Python 7453. 합이 0인 네 정수난이도 : 골드 2소요 시간 : 40분날짜 : 2024.12.20언어 :Python알고리즘 유형 : 이분탐색, 투포인터, 정렬설명 보기전에 문제 풀어보러 가기1. 문제 설명숫자를 담은 배열 A, B, C, D가 주어진다.A에서 숫자 하나(a), B에서 숫자 하나(b), C에서 숫자 하나(c), D에서 숫자하나(d)를 골라서합(a + b + c + d)이 0이 되는 쌍의 개수를 찾는다.2. 해결 방식우선 숫자의 개수는 최대 4000개이다.완탐 시간복잡도 O(n^4) : 4000^4 = 256,000,000,000,000 -> 약 250만 초가 걸린다.......투포인터 알고리즘을 사용해서 해결했다.우선 a + b와 c + d 의 순서쌍을 모두 찾는다. (시간복잡도 O(2 * n..
알고리즘 유형공부 - 위상정렬 (Topological Sorting) 위상정렬 (Topological Sorting)1. 개요위상정렬(Topological Sorting)은 방향성 비순환 그래프(DAG, Directed Acyclic Graph)에서 노드들을 선형으로 정렬하는 방법이다.이 정렬은 그래프의 모든 간선 (u, v)에 대해 노드 u가 노드 v보다 앞에 오도록 정렬한다. 위상정렬은 순서가 필요한 작업 스케줄링, 컴파일러의 의존성 분석, 데이터 처리 파이프라인 등 다양한 분야에서 활용된다.2. 알고리즘의 원리위상정렬은 두 가지 주요 알고리즘을 사용한다: Kahn의 알고리즘 (BFS 기반): 진입 차수(indegree)를 기반으로 정렬한다. 깊이 우선 탐색 (DFS 기반): 각 노드를 방문한 후, 역순으로 정렬한다. 위상정렬이 가능한 그래프는 사이클이 없는 방..
Baekjoon 2623. 음악프로그램 / Python 2623. 음악프로그램난이도 : 골드 3소요 시간 : 30분날짜 : 2024.12.19언어 : Python알고리즘 유형 : 위상정렬, 그래프이론, 방향비순환 그래프설명 보기전에 문제 풀어보러 가기1. 문제 설명순서가 주어진 리스트 여러개가 주어진다.이 순서를 유지하면서 주어진 모든 수를 정렬한다.2. 해결 방식위상정렬의 아주 대표적인 문제이다.위상정렬알고리즘의 풀이방식을 그대로 사용한다.연결리스트 자료구조를 만들어 풀이할 수도 있을 것 같아서 해봤다. (사실 더 효율적이어서 한건 아니고, 이런 자료구조를 만드는 것에 익숙해지기 위해서 했다.)3. 정답 코드풀이 1 -  위상정렬import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt"..
Every CS - 데이터베이스 06 - NoSQL DB 06 - NoSQL1. 개요NoSQL (Not Only SQL): 테이블 형태가 아닌 다양한 형태로 데이터를 저장할 수 있는 데이터베이스 유형이다.NoSQL은 높은 부하를 감당하거나 대용량 데이터를 다루는 분산 환경에서 빛을 발한다.NoSQL의 주요 장점은 확장성, 유연성, 가용성, 성능이다.2. NoSQL의 유형1. 키-값 데이터베이스키-값 데이터베이스는 데이터를 키와 값의 쌍으로 저장한다. 이는 NoSQL의 가장 간단한 형태다.대표적으로 Redis, Memcached 등이 있으며, 이들은 주로 메모리에 데이터를 저장한다.이런 데이터베이스는 가벼운 정보를 저장하거나 다른 주요 데이터베이스를 보조하는 용도로 활용된다.2. 문서지향 데이터베이스문서지향 데이터베이스는 데이터를 도큐먼트 형식으로 저장하며..
알고리즘 유형공부 - 비트마스킹 (BitMasking) 비트마스킹 (Bitmasking)1. 개요비트마스킹(Bitmasking)은 정수를 이진수로 표현하여 각 비트를 활용해 데이터를 효율적으로 처리하는 기법.주로 집합의 상태를 표현하거나 조합 문제를 해결할 때 사용된다.2. 알고리즘의 원리비트마스킹은 비트 연산을 통해 데이터를 조작한다.비트 연산을 이용해 특정 비트의 ON/OFF 상태를 확인하거나 변경할 수 있다.비트마스킹의 주요 작업은 다음과 같습니다:비트 켜기 (Set Bit): 특정 비트를 1로 설정한다.비트 끄기 (Clear Bit): 특정 비트를 0으로 설정한다.비트 토글 (Toggle Bit): 특정 비트를 반전한다.비트 확인 (Check Bit): 특정 비트가 1인지 확인한다.3. 비트마스킹을 사용하는 이유메모리 절약: 각 비트를 상태로 사용하기..
Baekjoon 9328. 열쇠 / Python 9328.열쇠설명 보기전에 문제 풀어보러 가기1. 문제 설명'.'은 이동가능한 곳'*'은 이동 불가능한 곳'$'는 문서가 있는 곳'소문자 알파벳'은 열쇠'대문자 알파벳'은 잠긴 문건물 밖에서 안으로 돌아다닐 수 있으며, 문서를 가장 많이 챙길 수 있을 때, 문서의 개수를 구하는 문제2. 해결 방식기본적인 bfs문제에다 문/열쇠의 개념이 추가되었다.우선 빌딩 을 '.'안에 넣는 방식으로 건물 외부에 대한 배열을 추가했다.새로운 열쇠를 얻을 때 마다, 방문했던 잠긴 문을 열 수 있는 가능성이 생기므로 이를 해결해주는 것이 중요하다.새로운 열쇠를 얻게 되면, 방문했던 잠긴 문들 중에 얻은 열쇠로 열리는 문이 있다면 큐에 추가하는 방식으로 해결했다.3. 정답 코드import sys# sys.stdin = ope..
알고리즘 유형공부 - BFS와 DFS DFS와 BFS1. DFS1. 개요깊이 우선 탐색(Depth First Search, DFS)은 그래프 탐색 알고리즘으로, 한 노드를 선택한 후 가능한 깊이까지 탐색한 후 돌아와 다른 경로를 탐색합니다.2. 알고리즘의 원리시작 노드에서 출발합니다.방문하지 않은 인접 노드가 있으면 그 노드로 이동하고 방문 처리를 합니다.더 이상 방문할 수 있는 노드가 없으면 이전 노드로 돌아갑니다.모든 노드를 방문할 때까지 이 과정을 반복합니다.주로 스택을 사용하며, 재귀 호출로 구현할 수 있습니다.3. 시간복잡도 및 공간복잡도시간복잡도 `: O(V + E) (V: 노드 수, E: 간선 수)공간복잡도 `: O(V)4. 예시 코드# DFS 예시 코드 (재귀 버전)def dfs(graph, v, visited): vis..
Every CS - 데이터베이스 05 - 데이터베이스 설계 DB 05 - 데이터베이스 설계01. ER 다이어그램ER 다이어그램(ERD) : 데이터베이스를 구성하는 요소들의 관계를 나타내는 그림목적 : 데이터베이스의 저장되는 엔티티의 구조를 모델링하는 것(즉, 시각적으로 설계하는 것)효과 : 추후에 데이터베이스를 확장하거나 수정할 때, 어떤 부분이 영향을 받는지 쉽게 파악할 수 있어, 유지보수가 용이하고 원활한 소통이 가능하다.ERD 표기 방식 1 - 피터 첸 표기법이런 표기방식은 개념적으로 엔티티를 모델링하는 데에 매우 유용하다.하지만 엔티티가 많아질 경우 그림이 다소 복잡해지고 RDBMS 상에서 어떻게 테이블의 형태로 표현되는지 한 눈에 파악하기 어렵다.따라서, 요즘에는 IE 표기법(새 발 표기법, 까마귀 발 표기법)이라고 하는 ERD 표기 방식을 사용한다.E..
Baekjoon 1197. 최소 스패닝 트리 / Python https://www.acmicpc.net/problem/11972024.12.16 - [알고리즘/알고리즘 정리] - 알고리즘 유형공부 02 - 최소신장트리 (MST) 알고리즘 유형공부 02 - 최소신장트리 (MST)최소신장트리, 최소스패닝트리 - Minimum Spanning Tree개요신장트리란 무엇일까?신장트리(Spanning Tree)란 - 그래프에서 모든 정점을 포함하며, 모든 정점에 대한 최소한의 연결만을 가진 그래프이다.그developer-traxer.tistory.com알고리즘 설명은 위 글을 참고하면 좋다.문제는 그냥 이 최소스패닝트리를 구현하는 것이다.1. PRIM 알고리즘이 경우에는 시간초과가 난다. 그 이유는 프림알고리즘의 시간복잡도는 I(V * ElogV)이므로 O(10^11)이기..
마크다운(Markdown)과 사용법 1. 마크다운(Markdown)이란?마크다운은 마크업 언어의 일종으로 읽고 쓰기 쉬운 문서 양식을 지원한다.HTML로 변환이 가능하다.HTML에서 사용하는 귀찮은 태그들을 간편한 '약속'으로 사용할 수 있다.2. 마크다운의 장점과 단점2.1 장점 1. 간결하다. 2. 별도의 도구없이 작성가능하다. 3. 다양한 형태로 변환이 가능하다. 4. 텍스트(Text)로 저장되기 때문에 용량이 적어 보관이 용이하다. 5. 텍스트파일이기 때문에 버전관리시스템을 이용하여 변경이력을 관리할 수 있다. 6. 지원하는 프로그램과 플랫폼이 다양하다.2.2 단점 1. 표준형식이 존재하지 않는다. 2. 모든 HTML요소를 대변할 수 없다.3. 마크다운 사용법 (문법)3.1 기본문법Head..

티스토리툴바