해시 자료구조는 16자리의 번호의 일부분을 index로 사용하는 자료구조입니다. 해시 함수란? 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수 왜 일부분만 사용하는가? 모든 해시를 배열로 가지고 있으면 10^16의 배열이 필요합니다. 이는 40페타 바이트를 차지하게 됩니다. 그렇기에 모든 hash 값을 사용하는 게 아닌 일부분만의 값을 사용하여 해시 테이블을 생성합니다. 충돌 회피 방법 1. Chaining Key가 중복된 노드를 LinkedList로 연결하여 관리합니다. Java의 STL 자료구조는 Chaining 방식을 사용합니다. 주의사항: 충돌이 빈번할수록 성능이 안 좋아지고, 해시 충돌이 한 곳으로 몰렸다면 O(N)의 시간 복잡도를 가질 수 있습니다. ...
문제 링크 백준 1430번 공격 문제 설명 해당 문제는 적이 존재하고 타워에서 사정거리 안에 든 적에게 에너지를 모두 담아 공격합니다. 만약 사정거리에 닿지 않는다면 근처 타워에게 에너지를 전달하고, 전달하는 과정에서 에너지가 반으로 줄어듭니다. 문제 조건 탑 갯수: 1 <= n <= 50 좌표: 0 <= x, y <= 1000 에너지 d: 1 <= d <= 100 사정거리 r: 1 <= r <= 500 재분배 가능 r보다 작다면 제한 내의 에너지 공유 가능 에너지 공유 시 절반만 전달 적과 거리는 r보다 작아야 함 공격 시 모든 에너지를 쏨 문제 해결 아이디어 해당 문제는 네트워크 문제와 비슷합니다. 적으로부터 연결된 타워를 방문할 때마다 에너지를 추가하는 방식을 떠올렸습니다. ...
문제 링크 프로그래머스 택배상자 간단한 문제 설명 메인 컨테이너 벨트를 타고 상자들이 순서대로 전달됩니다. 이 상자들을 서브 컨테이너 벨트를 사용하여 트럭에 전달하는 문제입니다. 메인 컨테이너 벨트로 상자들이 1, 2, 3, 4, 5 순서로 전달됩니다 트럭에서 상자를 쌓고 싶은 순서는 다릅니다 서브 컨테이너 벨트에 stack 방식으로 상자를 보관할 수 있습니다 상자들은 마지막에 넣은 것을 가져와 트럭에 실을 수 있습니다 간단한 예시 트럭에 실어야 하는 순서가 [2, 4, 5, 3, 1]이라고 한다면: ...
문제 정의 2x2 블록 안에 같은 문자열이 존재할 때 블록을 삭제하여 삭제된 모든 블록의 개수를 반환하는 문제입니다. 중학교 때 애니팡을 많이 했었는데, 이 문제를 보니까 살짝 추억이 생각나네요. 과거에 했던 게임이라 그런지 문제를 이해하는 데 크게 어려움은 없었던 문제였습니다. 문제 해결 아이디어 4칸을 조회할 수 있는 배열 만들기 x, y 좌표 완전 탐색 4칸 모두 일치하면 좌표 저장 중복되는 좌표 제거 board의 좌표 제거 제거할 좌표가 존재하지 않을 때까지 위의 과정 반복 주의 사항 우선 전부 탐색해서 삭제해야 할 좌표를 찾아서 한 번에 삭제해줘야 합니다 중복되는 좌표 중복 제거하기 코드 작성 sq = [[0, 0], [0, 1], [1, 0], [1, 1]] # 이동 배열 만들기 def solution(m, n, board): answer = 0 board = [list(i)[::-1] for i in zip(*board)] # x축 y축 뒤집기 while True: # 제거할 좌표 없을 때까지 반복 remove_list = set() for i in range(n - 1): for j in range(m - 1): # board 완전 탐색 try: now = board[i][j] for x, y in sq: # 4칸 모두 if now != board[i + x][j + y]: break else: # 모두 일치 시 제거할 좌표 추가 for x, y in sq: remove_list.add((x + i, y + j)) except: pass if len(remove_list) == 0: break remove_list = list(remove_list) remove_list.sort(key=lambda x: -x[1]) # pop을 할 때 위에서부터 해야 원하는 idx를 제거할 수 있습니다 for x, y in remove_list: answer += 1 board[x].pop(y) return answer 핵심 포인트 set()을 사용하여 중복 좌표 제거 배열을 transpose하여 x축/y축을 뒤집어 처리 pop() 시 인덱스 문제를 해결하기 위해 y좌표 내림차순 정렬 삭제할 좌표를 모두 찾은 후 한 번에 삭제
문제 링크 프로그래머스 길 찾기 게임 문제 설명 x, y 좌표로 이루어진 이진 트리의 맵에서 전위 순회, 후위 순회 방식으로 순회한 노드의 번호들을 반환하는 문제입니다. 문제 해결 방법 이 문제를 해결하기 위해서 트리 자료구조를 만들어서 문제를 해결했습니다. 트리 자료구조 만들기 class Node: def __init__(self, x, y, value=None, left=None, right=None, parent=None): self.x = x self.y = y self.value = value self.left = left self.right = right self.parent = parent 필드 구성: x와 y 좌표 자식 노드를 저장할 left, right 부모 노드를 가리키는 parent 필드 노드를 추가하는 방식 노드 추가 방식은 양방향 링크드 리스트와 유사하게 작성했습니다. ...
이진트리란? 이진 트리는 루트(Root) 노드에서 시작하여 각 노드는 왼쪽 서브트리(Left Subtree)와 오른쪽 서브트리(Right Subtree)로 이루어져 있습니다. 각 노드의 자식 노드는 최대 두 개이기 때문에, 이진 트리는 가장 단순한 형태의 트리 중 하나입니다. 이진트리의 활용 분야 데이터베이스: 색인(Index)을 만드는 데 사용 정렬 알고리즘: 이진 탐색 트리(Binary Search Tree) 압축 알고리즘: 허프만 코딩(Huffman Coding) 인공지능: 의사결정나무(Decision Tree) 이진트리의 장단점 장점 검색 속도가 빠릅니다 데이터를 효율적으로 저장합니다 구현이 간단합니다 단점 균형이 맞지 않을 경우 성능이 저하됩니다 트리의 높이가 너무 높아질 수 있습니다 메모리 사용량이 많을 수 있습니다 이진트리의 순회 방법 1 / \ 2 3 / \ / \ 4 5 6 7 전위 순회 (Preorder) ...
양궁대회 문제 분석하기 해당 문제는 라이언과 어피치가 n개의 화살을 쏴서 라이언이 가장 큰 점수 차로 이긴 배열을 반환하는 문제입니다. 첫 번째 조건 라이언은 챔피언이라 어피치에게 핸디캡을 주고 시작합니다. 0~10점까지가 있는데 땅따먹기처럼 하나의 점수는 한 사람만 점수를 획득할 수 있습니다. 예를 들어 10점을 어피치와 라이언이 1발씩 맞춘다면 어피치가 10점을 가져가게 되는 것입니다. 그렇기에 점수를 획득하려면 무조건 어피치 + 1의 화살을 맞춰야 하는 것입니다. 두 번째 조건 가장 큰 점수 차가 2개 이상이라면 점수가 낮은 배열순으로 많이 맞춘 배열을 선택합니다. ...
문제 링크 프로그래머스 후보키 문제 설명 이 문제는 데이터베이스에서 관계형 데이터의 후보키(candidate key)를 찾는 문제입니다. 데이터베이스에서는 후보키(candidate key)라는 개념을 사용하여 테이블에서 튜플을 유일하게 식별할 수 있는 속성 또는 속성의 집합을 의미합니다. 후보키의 조건 후보키는 다음 조건들을 만족해야 합니다: 1. 유일성 유일성은 데이터베이스의 모든 ROW 중에 유일하게 존재해서 식별이 가능한 값을 의미합니다. 2. 최소성 최소성은 후보키로 선택된 속성(Attribute) 집합에서 어떤 속성 하나를 제외하거나 두 개 이상의 속성을 합쳐서도 여전히 유일성이 보장되는 속성 집합을 말합니다. ...