https://www.acmicpc.net/problem/1548 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 아이디어 해당 링크 참고함 https://isukorea.com/group/morgorithm/board/b/8 import sys import heapq input = sys.stdin.readline n = int(input().rstrip()) A = list(map(int, input().rstrip().split()..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 아이디어 단순 BFS이다. 하지만 deque를 사용하면 시간초과가 나기 때문에, day를 제일 첫 번째 원소로 가지고 있는 heapq를 사용해야한다. import sys import heapq input = sys.stdin.readline m,n = map(int, input().rstrip().split()) maps = [] queue = [] visited = [[0 for..

https://www.acmicpc.net/problem/20436 20436번: ZOAC 3 첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다. 그 다음 줄에는 알파벳 소문자로 구성된 문자열이 주어진다. 문자열의 www.acmicpc.net 매번 느끼는거지만 문제를 잘 읽자... 오른손은 한글의 모음 부분만, 왼손은 한글의 자음 부분만 가능하다는 조건을 빼놓아서 괜히 어렵게 풀었다. 그냥 단순하게 구현만 하면 되는 문제 import sys input = sys.stdin.readline l,r = input().rstrip().split() want_str = list(input().rstrip()) keyboard_lis..

https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 복잡한 구현문제이다. 전체적인 구조는 1시간정도 걸려서 구현했는데, 구슬폭파 부분에서 시간이 많이 걸렸다. 차례대로 구슬 폭파를 하지 않고, 한꺼번에 해야하는데 차례대로 구슬폭파를 하는 식으로 구현해서 몇 시간이나 낭비했다. 아이디어 먼저 N*N 크기의 맵의 각 자리에 숫자를 부여한 뒤, 이를 참고해서 1번 자리에 있는 숫자부터 N*N-1번 자리에 있는 숫자까지 maps 배열에 ..

1. 그래프 관련해서 이미 배운 내용 정리 - 그래프랑 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미한다. - 그래프와 트리 비교 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 - 그래프의 구현 방법 : 노드의 개수가 V, 간선의 개수가 E인 그래프일 때 인접 행렬 인접 리스트 방식 2차원 배열을 사용하는 방식 리스트를 사용하는 방식 메모리 공간 O(V^2) O(E) 특정 노드에서 다른 노드로 이어진 간선의 비용을 알기 위한 시간 복잡도 O(1) O(V) 2. 서로소 집합 - 서로소 집..

1. 다익스트라 최단 경로 알고리즘 - 다익스트라 (Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 떄, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. => '음의 간선'이 없을 때 정상적으로 동작한다. => 따라서, 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. - 다익스트라 알고리즘은 일반적으로 그리디 알고리즘으로 분류된다. => 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. (1) 다익스트라 알고리즘의 간략한 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. (모든 값을 무한으로 초기화한다) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른..