Power of Positive Thinking

해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조를 구현하는 자료구조이다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 시간복잡도가 O(1) 이라는 점이다. 덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다. 1. 해시 해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 여기서 입력값은 ABC, 1324BC, AF32B로 각각 3글자, 6글자, 5글자이지만, 화살표로 표시한 특정 함수를 통과하면 2바이트의 고정 크기 값으로 매핑된다. 여기서 화살표 역할을 하는 함수가 바로 해시 함수다. (해시 함수를 만드는 방법론도 하나의 주제가 될 수 있지만 코딩테스트 주제를 벗어난다. 참고로, 구글은 해..

[문제] https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 와.. 이 문제는 정말 블로그에 박제할 수 밖에 없는 넘나 인상적인 문제이다. !!!! 🤦🏻‍♀️ 🤦🏻‍♀️ 🤦🏻‍♀️ 먼저, 내가 틀렸던 테스트 케이스를 공유하겠다. 이 테스트 케이스를 만들어내는 것도 정말 오래 걸렸다. 아무리 테케 만들어도 다 맞는걸 우째,, 오류나는 테스트케이스 찾음 ... 답은 9인데 -1이나옴. 4 6 010011 011001 00001..

[문제] www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net [풀이] 정수를 하나씩 외칠때마다 동생은 지금까지 수중에서 중간값을 말해야 한다. sol-1) 이진 탐색으로 풀었는데 시간초과 발생.. sol-2) 우선순위 큐로 접근하여 해결하였다. - 아이디어 : 중앙값 기준으로 왼쪽은 maxheap, 오른쪽은 minheap - 중간값 기준으로 왼쪽에 맥스힙(작은 수 중에 제일 큰거), 오른쪽에 민힙(큰 수 중에 제일 작은 값 ) : 수를 정렬했다고..

www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net import collections import sys input = sys.stdin.readline n, l, r = list(map(int, input().split())) graph = [list(map(int, input().split())) for _ in range(n)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] cnt = 0 while Tr..

www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 모든 경우의 수를 따져야 할 때 재귀적으로 코드를 짜면 구현하기 쉬워진다. 처음에는 모든 경우의 수를 '조합'을 통해 구해놓고 나서 --> 그래프를 탐색하는 식의 방식을 생각했는데 이는 너무나 복잡하다. 마치 운영체제에서 프로그램을 메모리로 로드(load)할 때 모든 명령어와 정적 데이터를 프로그램 실행 전에 한꺼번에 모두 로드하는 것처럼 말이다. 그래서 우아한 코드를 짜려면 경..

1. 트리의 정의 : 계층적 구조를 갖는 자료들을 표현하기 위한 자료 구조이다. ex) 월드컵 본선 대진표, 회사나 학교의 조직도, 인터넷 상점의 상품 분류 기준 등 2. 개요 트리는 현실 세계의 개념을 추상화해 표현하는 자료 구조로 고안되었지만, 탐색형 자료 구조로도 유용하게 쓰인다. 특정한 조건을 지키도록 구성된 트리들을 이용하면 배열이나 리스트를 사용하는 것보다 같은 작업을 더 빠르게 할 수 있기 때문이다. 즉, 어떤 형태로 트리를 구성하느냐, 자료들을 어떻게 배치하느냐에 따라 다양한 형태의 트리가 있을 수 있으며, 이들을 이용해 다양한 문제들을 빠르게 풀 수 있다. 3. 트리의 구성 요소 - 트리는 자료가 저장된 노드(node)들이 간선(edge)으로 서로 연결되어 있는 자료 구조이다. 노드 간에..