알고리즘

문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 풀이 단방향 그래프에서 최단거리 찾기 위해 bfs 돌림. visited를 따로 두고 풀었는데, 다른 분들 풀이 보니까 그냥 각 노드에 대한 distance 배열을 만들어서 최단거리로 차차 갱신하며 푸는 법이 일반적 + 더 효율적인듯 코드 import sys input = sys.stdin.readline impor..

문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 피보나치 수열을 구하는 방법 중에 수열을 이용한 방법을 구현함. 메모제이션을 사용하는 법도 기억해두자,, 참고 ref ) https://www.acmicpc.net/blog/view/28 피보나치 수를 구하는 여러가지 방법 피보나치 수는 다음과 같이 정의되는 수열입니다. $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}$ 피보나치 수를 조금 써보면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144..

문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제 풀이 bfs 문제로, 모든 땅에 대해서 가장 거리가 먼 육지를 bfs로 찾고 최대값을 갱신해가면서 완전탐색 돌리면 된다. 효율적인지는 모르겠음.. 코드 import sys input = sys.stdin.readline import collections H, W = map(int,input().split()) MAP = [list(input().strip()) for _ in range(H..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 풀이 bfs 문제로, 다음 이동할 위치를 위아래 3차원까지 고려해주면 된다. 답 분기가 많아서 헷갈렸음 코드 import sys input = sys.stdin.readline import collections M, N, H = map(int,input().split()) q = collections.deque() tomato_tower = [] to_ripe =..

문제 https://www.acmicpc.net/problem/17836 문제 풀이 시작점과 공주 위치가 고정되어 있음. 검을 찾고 공주한테 가는 경우와 바로 공주한테 가는 경우 둘 다 bfs로 구해서 비교하면 됨. fail하는 경우를 잘 걸러줘야함 코드 import sys input = sys.stdin.readline import collections ''' 검을 찾고 가는 경우와 공주한테 바로 가는 경우를 비교 ''' N, M, T = map(int, input().split()) INF = 100000 def bfs(MAP, start_x, start_y, target_x, target_y, flag=0): move = {(-1,0), (0,1), (1,0), (0,-1)} visited = [[..

문제 https://www.acmicpc.net/problem/14405 14405번: 피카츄 피카츄는 "pi", "ka", "chu"를 발음할 수 있다. 따라서, 피카츄는 이 세 음절을 합친 단어만 발음할 수 있다. 예를 들면, "pikapi"와 "pikachu"가 있다. 문자열 S가 주어졌을 때, 피카츄가 발음할 수 있는 문 www.acmicpc.net 문제 풀이 코드 1) 정규표현식 코드 2) 파이썬 문자열 내장함수 replace 사용 코드 1 import re import sys input = sys.stdin.readline S = input().strip() if re.fullmatch('(pi|ka|chu)+',S): print('YES') else: print("NO") 코드 2 impor..

풀이 bfs 문제인데, 다음 위치를 큐에 채워주는 부분에서, 장애물을 만나거나 범위 끝까지 도착할때까지 미끄러지는 것을 find_next로 구현하여 다음위치를 찾음. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/169199 코드 import collections def find_next(x,y,tx,ty, board): while True: nx, ny = x, y x += tx y += ty if not 0

풀이 bfs로 풀이함 문제 https://school.programmers.co.kr/learn/courses/30/lessons/154538 bfs 개념 https://cccaaa.tistory.com/22 감자블로그 공부하고 삽질한 것 정리하는 블로그 cccaaa.tistory.com 코드 import collections def solution(x, y, n): q = collections.deque() q.append((x,0)) visited = [0 for _ in range(1000001)] visited[x] = 1 while q: x, cnt = q.popleft() if x == y : return cnt for i in range(3): if i == 0: nx = x + n else..