모영이의 블로그

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 ..

20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 유니온 파인드 처음 파이썬으로 돌렸을 때 런타임 에러가 났다. for문에서 find함수 사용을 없애고, union함수 내에서 인덱스 값을 저장하도록 했다. 그리고 합칠 때 부모의 최솟값으로 통일 되게 했는데 이렇게 안하면 런타임 에러가 났다. 1) 입력 받은 두 개의 점을 유니온 함수로 합친다. 2) 두개의 점의 부모가 다르면 합치고, 부모가 같으면 게임 끝. 3) 최초의 게임 끝일 때의 인덱스 값을 endgame에 저장하고 출력. 전체 코드 import s..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 알고리즘 1 -> N까지 가야하고 v1, v2를 거쳐야 한다. 양뱡향이므로 그래프에 저장할 때 둘 다 저장해야한다. 우선순위 힙을 사용하고 heappush()로 값을 넣고 heappop()으로 값을 추출한다. 1) 1에서 출발, v1에서 출발, v2에서 출발하는 세가지 distance를 구한다. 2) 1 -> v1 -> v2 -> N 과 1 -> v2 -> v1 -> N을 비교해서 최솟값이 답이다. 3) 갈..

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 와샬 알고리즘 1) i 에서 j 까지의 최단 거리를 (i ~ k + k ~ j)와 비교하며 업데이트 2) INF 값 그대로면 0출력, 아닐시 거리 값 출력 전체 코드 import sys input = sys.stdin.readline N = int(input()) M = int(input()) INF = sys.maxsize dosi = [[INF for _ in range(N+1)] for __ in range(N+1)] for _ in range(M)..

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투포인터 1) 용액 배열을 오름차순으로 정렬한다. 2) sp는 제일 왼쪽 인덱스 출발, ep는 제일 오른쪽 인덱스 출발 3) sp가 ep보다 커지거나 서로 만나면 while문 종료 4) 합쳐질 용액의 값 두개와 합의 절댓값을 계속 저장하고, 합이 > 0 이면 ep를 -1하고, 합이 0보다 크면 합을 더 작게 만들어야 하기에 오른쪽 포인터를 왼쪽으로 한칸 옮기고 -> 0보다 작으면 합을 더 크게..