2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 조금 어려웠던 벨만포드 문제 ~~~~ 아주 전형적인 벨만포드 문제라면 음수 사이클의 존재 여부만 체크할텐데 이 문제에서는 음수 사이클이 존재하는지 & 해당 사이클에서 목적 노드로의 path가 있는지 또한 검사해야 했다 그래서 3번이 처음에는 음수 사이클이 존재한다면 Gee를 출력하는 줄 알았지만 ~~ 여러개의 음수 사이클이 존재하더라도, 하나의 음수 사이클에서라도 도착지로 가는 path가 있을 ..

✅ 이 글의 전반적인 내용은 아래의 글을 정리하여 작성하였음 https://d2.naver.com/helloworld/831311 해시 시리즈 3탄 이 글을 쓰기 위해 이전의 글을 써왔고, 해시에 대해 잘 알지 못한다면 참고하는 것도 좋을 것 같다https://2jinishappy.tistory.com/230 빠른 데이터 검색을 위한 Hashing과 Hash Table select * from ~ where key="name" 우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다 데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 2jinishappy.tistory.com https://2jinishappy.tistory.com/2..

https://www.ted.com/talks/joy_buolamwini_how_i_m_fighting_bias_in_algorithms/up-next How I'm fighting bias in algorithms MIT grad student Joy Buolamwini was working with facial analysis software when she noticed a problem: the software didn't detect her face -- because the people who coded the algorithm hadn't taught it to identify a broad range of skin tones and facial stru www.ted.com 학교 다닐 때 ..

➕ Hash Table은 java에서의 HashTable API가 아닌 Hash function을 통해 mapping된 value를 저장하는 Table을 뜻함 👇 이전 글 보기 https://2jinishappy.tistory.com/230 빠른 데이터 검색을 위한 Hashing과 Hash Table select * from ~ where key="name" 우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다 데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 2jinishappy.tistory.com 서로 다른 key에 대해 hash function으로 변환된 h(x)가 같을 경우, 같은 index에 값을 저장해야 하는 coll..

select * from ~ where key="name" 우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다 데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 것이 효과적인지 고민하는 과정에서 해싱의 원리를 찾을 수 있다. 특정 key가 주어졌을 때, 해당 key 값을 가진 record를 찾기 위한 방법으로는 1️⃣ Key를 index로 가진 array로 table 구현 2️⃣ BST 이용 1번은 조회하는 데 O(1)이 소모되는 대신 |max(key)|만큼의 메모리를 요구하기 때문에 실제로 사용하기에는 어렵다. 2번 또한 1번에 비해서는 get, insert의 평균적인 시간이 짧긴 하지만 O(log n)도 수천, 수만개의 re..

이전에 Biconnected Component와 Cut Vertex에 대해 포스팅한 적이 있다 https://2jinishappy.tistory.com/169?category=903864 무방향그래프에서의 Cut Vertex와 Biconnected Components 우리는 종종 Connected Component에 대해 들어보곤 한다. 주로 BFS 알고리즘 관련 문제를 풀이할 때 등장하는 개념이며, 정확하게는 maximal connected subgraph(가능한 한 connected한 모든 vertex 및 edge를 포.. 2jinishappy.tistory.com 간단히 요약하자면 Cut Vertex: Connected Undirected Graph에서 특정 정점을 제거했을 때 2개 이상의 Conn..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 응용 BFS문제인 공주님을 구해라 ~!~! 공주에게 도달할 수 있는 최단거리 상태가 검을 얻었을 때/검을 얻지 못했을 때로 나뉘기 때문에 visit 배열을 3차원으로 만들어주어야 한당 이렇게 3차원 visit 배열을 요구하는 BFS문제는 까다로울 수 있기 때문에 주 의 하 자 #include #include using namespace std; typedef struct { int..

https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 기본 MST 문제~!~!~!~!~! #include #include #include #define pii pair #define INF 987654321 using namespace std; vector g; int n, m; long long sum; long long pr..