모영이의 블로그

1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 분할 정복 : 시작점을 기준으로 +d만큼 탐색을 한다. 만약 압축 실패시 분할 압축. 전체 코드 import sys input = sys.stdin.readline def apchuk(si, sj, d, result): color = graph[si][sj] isTrue = True for i in range(si, si + d): for j in range(sj, sj + d): if graph[i][j] != color: isTrue = Fals..

1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라 알고리즘 : 벽의 길은 가중치를 1을 두고 나머지 길은 0으로 두면 다익스트라 알고리즘을 사용할 수 있다. BFS로 상하좌우를 탐색하고 갈 수 있는 길을 찾아내면 된다. 길의 가중치가 0이라면 벽이 없는 길은 아무렇게나 가도 상관이 없을 것이다. 1) 최소 힙에 가중치와, 노드좌표를 넣는다. 2) 다익스트라 알고리즘 사용 3) 상하좌우 탐색 BFS사용 전체 코드 import sys import collections import h..

1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 : 각 자리의 최대값은 위의 왼쪽 오른쪽 중 최댓값에 자기 자리를 더한 것이다. 1) 각 층별로 계산을 해야한다. 한칸 내려갈 때마다 계속 1씩 늘어나는 구조다. 2) p1과 p2에 부모의 값을 담는다. 왼쪽 부모는 맨 왼쪽 인덱스일때를 제외하고 담을 수 있고, 오른쪽 부모는 맨 오른쪽 인덱스일때를 제외하고 담을 수 있다. 3) p1과 p2 중 큰 값 + 자신의 현재 위치값 업데이트 해주기 전체 코드 import sys input = sys.stdin.readline N = int(input()) graph = [..

7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net BFS : 나이트가 이동할 경로를 전부 업데이트 하다가 목적지를 만나면 값 출력 1) 나이트는 총 8개의 범위를 갈 수 있고 그 경로를 dx와 dy에 저장해 놓고 사용한다. 2) 나이트의 현재 위치가 목적지와 같다면 그 곳의 dp값을 리턴한다. 3) 나이트가 갈 수 있는 방향 8개를 전부 확인하고 나이트가 가지 않았던 위치면 그곳을 탐색한다. dp값이 -1 초기값이면 한번도 안갔던 곳이고 dp값을 업데이트 시켜주는데, 이전의 출발 지점의 dp값에 +1 한 값을 넣..

13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 그리디 알고리즘 : 처음에는 주유소 배열에서 최솟값 인덱스를 찾고 도로를 슬라이싱 해서 도로의 합 X 주유소 최솟값을 해주고, 주유소 최솟값 인덱스 뒤에 값들을 슬라이싱으로 다 제거 했다. 이렇게 해서 답은 나왔는데 시간 초과와 말도 안되는 비효율이 났다. 순서대로 for문을 돌아도 충분히 된다..! 1) for문을 돌며 min_value에 주유소 최솟값을 업데이트 한다. 단 첫번째의 경우 무조건 주유소를 들러야 한다. 2) (min_value * ..

4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 유니온 파인드 : 부모를 숫자가 아닌 문자열로 바꾼다고 생각하면 쉽다. 그냥 똑같은 유니온 파인드 문제인데, 파이썬만 그런지 모르겠지만, for문에서 find함수를 써서 부모가 같은 친구들의 수를 카운트 했었는데 시간 초과가 나서 number라는 새로운 딕셔너리를 만들어서 친구의 수를 저장하도록 했다. 1) parent 딕셔너리에 key = '친구이름', value = '친구이름'으로 초기화 해준다. 처음 입력 받을 때만 해야한다. 2) number ..