Python

그래프와 그래프 탐색

그래프 (Graph) 노드와 그 노드를 연결하는 간선의 집합으로, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프를 표현하는 방법에는 크게 인접 행렬과 인접 리스트 2가지 방법이 있다. 인접 행렬 이차원 배열로 그래프의 연결 관계를 표현하는 방식으로, 모든 관계를 저장하므로 노드 개수가 많을수록 메모리 낭비가 심하다. 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 알 수 있으므로 효율성이 떨어진다. 인접 리스트 리스트로 그래프의 연결 관계를 표현하는 방식으로, 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용할 수 있다. 인접 행렬에 비해 특정한 두 노드의 연결 정보를 얻는 속도가 느리다. n, m = map(int,input().split()) # 인접 행렬..

20182 골목 대장 호석 - 효율성 1

문제 https://www.acmicpc.net/problem/20182 20182번: 골목 대장 호석 - 효율성 1 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 접근 20168 골목 대장 호석 - 기능성 문제는 백트래킹으로 풀이했으나, 이 문제에서는 N과 M의 범위가 아래와 같으므로 시간초과 발생 1 ≤ N ≤ 100,000 1 ≤ M ≤ 500,000 솔직히 풀이 방법이 생각이 안나서 힌트를 참고해서 다익스트라를 써야한다는 것을 알았다. 그러나 문제는 출발지부터 목적지까지의 최단거리를 구하는 것이 아니라, 가지..

해시 테이블

해시 테이블 Key-Value로 데이터를 저장하는 자료구조 중 하나로, 해싱을 통해 정보를 빠르게 저장하고 검색할 수 있다. 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라고 한다. 먼저 각각의 키에 해시 함수를 적용해 해시 코드를 계산하고, 계산한 해시 코드를 이용해 배열의 고유한 인덱스를 계산한다. 계산한 인덱스를 통해 값을 저장하거나 검색하며, 실제 값이 저장되는 장소를 버킷이라고 한다. 해시 함수 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수로, 충돌이 발생할 확률을 최대한 줄이는 것이 중요하다. 충돌은 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나, 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 것을 말하며, 충돌이 자주 발..

21277 짠돌이 호석

문제 https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호석 DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태 www.acmicpc.net 접근 카카오 기출 문제 중 자물쇠와 열쇠 문제에서 힌트를 얻어, 기준 퍼즐1의 범위를 확장 시켜서 전체 경우마다 퍼즐2와 맞춰보는 식으로 풀이했다. 퍼즐의 크기 제한이 50 이므로 상하좌우 50씩 확장할 경우, 최대로 확장될 수 있는 퍼즐의 한 변의 길이는 150이다. 따라서 회전까지 고려했을 때 최대 4 * 100 * 100 * 50 * 50 = 10 * 9..

10703 유성

문제 https://www.acmicpc.net/problem/10703 10703번: 유성 작고 특이한 모양의 유성 사진이 인터넷에 올라왔다. 사진에는 매우 높은 곳에서 떨어지고 있는 유성이 허공에 찍혀 있었다. 유성이 떨어지고 난 뒤의 사진도 있었지만 안타깝게도 소실돼버려 www.acmicpc.net 접근 각각의 유성 조각에 대해 떨어질 수 있는 높이의 최솟값을 구한 후, 모든 유성에 대해 구한 최솟값 만큼 아래로 떨어트린다. 아래와 같이 유성 조각 아래에 땅이 있고 또 그 아래에 유성 조각이 있는 경우 또한 처리해줘야 한다. . . . . . . . . . . . X X X X . . . . . X . . . . . . . . X # # # # # # . . X . . . . . # . . X X ..

13168 내일로 여행

문제 https://www.acmicpc.net/problem/13168 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net 접근 문제를 처음 보고 내일로 티켓을 구입했을 때와 구입하지 않았을 때의 비용 정보를 따로 저장하고, 동일한 최단거리 알고리즘으로 비용을 계산한 후 비교해야 겠다고 생각했다. 경로마다 비용이 다르므로 다익스트라와 플로이드 워셜 중 하나를 이용하기로 했다. 문제에서 방문하려는 곳의 전체 경로가 정해져 있고 각 부분 경로마다 최단거리로 이동해서 목적지까지 드는 ..

1421 나무꾼 이다솜

문제 https://www.acmicpc.net/problem/1421 1421번: 나무꾼 이다솜 첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 둘째 줄부터 총 N개의 줄에 이다솜이 가지고 잇는 나무의 길이가 한 줄에 하나 www.acmicpc.net 접근 나무의 개수가 50보다 작고 자를 수 있는 나무 길이가 10000보다 작으므로, 자를 수 있는 모든 길이에 대해 벌 수 있는 돈을 계산해서 최댓값을 구했다. 주의할 점은 가지고 있는 나무를 전부 잘라서 팔아야하는 것은 아니므로, 해당 나무를 팔았을 때 얻는 비용과 자를 때 드는 비용의 차가 양수일때만 나무를 판다. 풀이 n, c, w = map(int, input().split(..

스택과 큐

스택 (Stack) 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 구조로, 가장 최근에 스택에 추가한 항목이 가장 먼저 나오는 후입선출 방식 재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어두고 재귀함수를 빠져나와 백트랙할 때는 스택에 넣어 두었던 임시 데이터를 빼내야 하는데, 스택은 이런 일련의 행위를 직관적으로 가능하게 해준다. 구현 (JAVA) import java.util.ArrayList; import java.util.EmptyStackException; public class Stack extends ArrayList { public Stack() { super(); } public Stack(int capacity) { super(capacity); } public E pus..

배열과 연결리스트

배열 자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉘는데, 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다. C 언어를 기준으로 배열은 크기를 지정하고 해당 크기만큼 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말하며, 크기가 고정되어 있어서 한 번 생성한 배열은 크기를 변경하는 것이 불가능하다. 배열의 가장 큰 장점은 논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에 원하는 요소의 인덱스 값을 알고 있으면 항상 O(1)에 해당 원소에 접근 가능하다는 점 예를 들어 int 배열에서 4번째 값에 접근하고 싶다면 (배열의 시작 주소 + (4 - 1) * 4)로 주소를 계산해 한번에 접근 가능하다. 단, 삭제 또는 삽입의 경우 원소들의 인덱스를 sh..