자료구조 / 맵 - Tech.it

Tech.it

Sign in Subscribe

자료구조 / 맵

맵(Map) 자료구조를 사용한 문제들입니다.

[PS] BOJ 8905 / 리트

[PS] BOJ 8905 / 리트

문제 링크: https://www.acmicpc.net/problem/8905 재밌게 풀었던 백트래킹 문제입니다. 풀이 리트 변환 규칙 문제에서 언급한 리트 표기의 규칙은 다음과 같습니다. * 각 알파벳을 리트로 나타낼 때, 최대 $K$개의 문자로 나타낼 수 있습니다. * 한 문자를 리트로 바꾸는 방법은 한 가지입니다. * d를 앞서 [)로 바꿨다면, 다른 d를 |>로

[PS] BOJ 3865 / 학회원

[PS] BOJ 3865 / 학회원

문제 링크: https://www.acmicpc.net/problem/3865 그래프 탐색을 응용하는 문제입니다. 풀이 파싱 + 그래프 탐색 파싱을 통해 유향 그래프를 만들어낸 뒤, 그래프 탐색으로 진출 차수가 0인 정점의 개수를 세면 됩니다. 1) 파싱 먼저, 입력 데이터는 다음과 같이 구성됩니다. N academy_name:member1,member2,...,memberK. ... (repeated N-1 times) $N$은

[PS] BOJ 9328 / 열쇠

[PS] BOJ 9328 / 열쇠

문제 링크: https://www.acmicpc.net/problem/9328 Thumbnail: Photo by Susan Q Yin (Unsplash) 격자 그래프 상에서 그래프 탐색을 하는 문제입니다! 풀이 BFS 기본적인 풀이는 BFS로, 벽과 길을 구분해 갈 수 있는 곳을 모두 탐색하면 됩니다. 다만, 격자 그래프 상의 타일(각 칸)이 벽과 길만 있는 것이 아니라

[PS] BOJ 26123 / 외계 침략자 윤이

[PS] BOJ 26123 / 외계 침략자 윤이

문제 링크: https://www.acmicpc.net/problem/26123 Thumbnail: Photo by Danie Franco (Unsplash) 풀이 윤이가 레이저를 발사하는 방식을 그대로 구현해주면 됩니다. 맵을 사용해, 각 높이별로 건물의 개수를 기록해두고 $D$일동안 반복하면 됩니다. 전체 코드 input = open(0).readline N, D = map(int, input().split()) heights = {} max_height = 0 for

[PS] BOJ 1417 / 국회의원 선거

[PS] BOJ 1417 / 국회의원 선거

문제 링크: https://www.acmicpc.net/problem/1417 Thumbnail: Photo by Arnaud Jaegers (Unsplash) 풀이 먼저, 각 후보자를 투표 수를 기준으로 맵에 저장합니다. 이후, 투표 수를 기준으로 우선 순위 큐에 추가해주고, 다솜이보다 더 많은 표가 예상되는 후보들의 표를 1씩 줄여가며 계산합니다. 전체 코드 from heapq import heappush, heappop input = open(

[PS] BOJ 27440 / 1로 만들기 3

[PS] BOJ 27440 / 1로 만들기 3

문제 링크: https://www.acmicpc.net/problem/27440 Thumbnail: Photo by 青晨 (Unsplash) 그래프 탐색을 활용해, \(N\)을 1로 만드는 최단 경로를 찾으면 됩니다. 풀이 그래프 탐색 임의의 수 \(X\)에 대해, 수행할 수 있는 연산은 3가지입니다. 1. \(x\)가 3으로 나누어 떨어지면, 3으로 나눕니다. 2. \(x\)가 2로

[PS] BOJ 1967 / 트리의 지름

[PS] BOJ 1967 / 트리의 지름

문제 링크: https://www.acmicpc.net/problem/1967 Thumbnail: Photo by Gene Gallin (Unsplash) 다양한 방법으로 풀 수 있겠지만, 그래프 탐색을 두 번 하는 것으로 풀었습니다. 풀이 가장 거리가 먼 두개의 정점 찾기 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만

[PS] BOJ 29721 / 변형 체스 놀이 : 다바바(Dabbaba)

[PS] BOJ 29721 / 변형 체스 놀이 : 다바바(Dabbaba)

문제 링크: https://www.acmicpc.net/problem/29721 Thumbnail: Photo by Daniel Stiel (Unsplash) 맵을 활용하는 문제였습니다. 풀이 체스판 전체를 배열로 관리하려고 하기보단 Map 자료구조를 활용해 방문한/이미 기물이 위치한 위치를 저장하는 편이 유리합니다. 먼저 모든 기물의 위치를 저장한 뒤, 각 기물의 위치에서 이동 가능한 모든 위치에 대해 해당 위치에

[PS] BOJ 17070 / 파이프 옮기기 1

[PS] BOJ 17070 / 파이프 옮기기 1

문제 링크: https://www.acmicpc.net/problem/17070 Thumbnail: Photo by Samuel Sianipar (Unsplash) DFS/BFS의 그래프 탐색으로 푸는 문제이지만, 그냥 풀면 시간 초과를 맞닥뜨리게 되는 문제였습니다. 풀이 DFS [\((0, 0), (0, 1)\)]에 가로로 배치되어있는 파이프를 오른쪽 / 아래 / 대각선의 3가지 방향으로 밀면서 \((N, N)\)으로 옮길 수 있는 경우의

[PS] BOJ 29714 / 브실이의 구슬 아이스크림

[PS] BOJ 29714 / 브실이의 구슬 아이스크림

문제 링크: https://www.acmicpc.net/problem/29714 Thumbnail: Photo by Elza Kurbanova (Unsplash) 여러분은 어떤 아이스크림을 좋아하시나요? 저는 메로나를 제일 좋아합니다 😄 풀이 태그에 해시를 이용한 집합과 맵이 있듯이, Map 자료구조를 이용하면 간단히 풀이할 수 있습니다. 기본적인 원리는 "각 아이스크림 구슬이 몇 개 있는지 파악하자" 입니다. 저는 파이썬의