분류 전체보기
[BaekJoon] 백준 14719 빗물
[BaekJoon] 백준 14719 빗물 문제: https://www.acmicpc.net/problem/14719 내코드 처음에는 왼쪽부터 시작해서 start, end 변수를 갱신해가며 구해줬다. 하지만 28 100 10 20 과 같이 마지막에 작은 값으로 끝나는 경우 저리가 어려워 실패했다. 그래서 서칭을 통해 찾은 방식은 다음과 같다. 1. for문으로 가로 전체를 돌아준다. 2. 현재 위치(i)의 왼쪽과 오른쪽 각각에서 최대값을 찾는다. 3. 2에서 찾은 두 값 중 더 작은 값을 찾는다. 4. 3에서 찾은 값과 현재 위치(i)의 높이의 차를 계산한다. 5. 4에서 계산한 값이 현재 위치에서 물이 차오르는 정도이다. 따라서 결과 값에 더해준다. 구현 문제가 나오면 대응을 잘 못하는 것 같다. 아무래..
[BaekJoon] 백준 1913번 달팽이
[BaekJoon] 백준 1913번 달팽이 문제: https://www.acmicpc.net/problem/1913 내코드 - 시간이 부족했던 문제가 아니라 단순 코딩으로 구현할 수 있었다. - 상하좌우로 이동하는 횟수에서 규칙을 찾아서 구현했다. # BaekJoon1913.py N = int(input()) num = int(input()) arr = [[0 for _ in range(N)] for _ in range(N)] value = 1 a = int(N / 2) b = int(N / 2) arr[a][b] = value tmp = int((N - 1) / 2) for i in range(tmp): # 위로 이동 for _ in range(2 * i + 1): value += 1 a -= 1 ar..
[BaekJoon] 백준 1325 효율적인 해킹
[BaekJoon] 백준 1325 효율적인 해킹 문제: https://www.acmicpc.net/problem/1325 내코드 관계로 엮여져 있고, 하나의 컴퓨터에서 시작해서 가장 많이 연결된 컴퓨터의 수를 구한다는 것에서 dfs로 풀어야겠다고 생각했다. 따지자면 방향성이 있는 그래프를 dfs로 탐색하는 문제다. bfs로도 풀 수는 있겠지만 bfs는 최단 시간에 더 적합한 알고리즘이어서 dfs로 풀어봤다. 간단한 dfs 문제였지만 파이썬으로 푸니 시간초과가 나서 pypy로 채점했다. # BaekJoon1325.py import sys input = sys.stdin.readline N, M = map(int, input().split()) relation = [[] for i in range(N)] s..
[BaekJoon] 백준 20444번 색종이와 가위
[BaekJoon] 백준 20444번 색종이와 가위 문제: https://www.acmicpc.net/problem/20444 내코드 처음으로 규칙을 찾아보았다. 6(n)번 가위질을 하는 것을 예시로 들었을 때 모든 경우의 수는 다음과 같다. 7(1X7, 가로0 세로6), 12(2X6, 가로1 세로5), 15(3X5, 가로2 세로4), 16(4X4, 가로3 세로 3) 즉, 가로로 자르는 횟수와 세로로 자르는 횟수에 의해 잘라진 색종이의 개수(k)가 정해진다. 여기서 색종이의 개수를 두 수의 곱으로 표현해 뒀는데 각각의 수를 a, b라고 하자. 이를 식으로 표현해보면 a + b = n + 2 a x b = k 이다. 문제에서 입력으로 n과 k는 주어지므로 위의 식을 만족하는 a와 b를 구하면 된다. b =..
[BaekJoon] 백준 1182번 부분수열의 합
[BaekJoon] 백준 1182번 부분수열의 합 문제: https://www.acmicpc.net/problem/1182 내코드 문제를 봤을 때 N의 최대값이 100,000이었고 배열 전체를 다 돈다고 해도 시간초과가 나지 않을 것 같아서 백트래킹으로 풀어야 겠다고 생각했다. dfs로 첫번째 숫자부터 탐색을 하면서 합이 S가 되면 결과값에 1을 더해줬다. 처음에는 이런 류의 문제가 어려웠는데 풀면서 익숙해지는 것 같다:) # BaekJoon1182.py N, S = map(int, input().split()) arr = list(map(int, input().split())) visited = [False] * N result = 0 # 방문하지 않은 처음은 제외하기 위해 사용 def check_fa..
[Algorithm] 최소 신장 트리 Minimum Spanning Tree
Minimum Spanning Tree(MST) MST(Minimum Spanning Tree)에 대해 알아보기 전에 Spanning Tree가 무엇인지 부터 알아야 한다. Spanning Tree란 1. 그래프의 모든 정점을 포함 2. 간선의 수가 가장 적음(n-1개) 3. 사이클이 없음 인 트리의 특수한 형태이다. 위의 두 조건을 만족하는 경우는 여러가지 이므로 하나의 그래프에는 많은 신장 트리(spanning tree)가 존재할 수 있다. 이는 BFS, DFS를 이용하여 찾을 수 있다. 그렇다면 MST는 무엇일까 MST는 위에서 설명한 spanning tree 중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비..
[BaekJoon] 백준 18870번 좌표 압축
[BaekJoon] 백준 18870번 좌표 압축 문제: https://www.acmicpc.net/problem/18870 내코드 처음 문제를 풀었을 때 시간초과가 났다. 이유가 뭘지 고민하다가 검색해보니까 다른 사람도 나와 같이 풀어서 시간 초과가 난 경우가 많았다.(역시 사람 생각하는건 다 똑같..) 문제는 index 메서드였다. index 메서드는 O(N)의 시간 복잡도를 가지기 때문에 for문 안에서 N*N이 되어 시간이 오래 걸리는 거였다. # 틀린 코드 # BaekJoon18870.py N = int(input()) arr = list(map(int, input().split())) sorted_arr = sorted(list(set(arr))) for i in range(N): arr[i] ..
[BaekJoon] 백준 2630번 색종이 만들기
[BaekJoon] 백준 2630번 색종이 만들기 문제: https://www.acmicpc.net/problem/2630 내코드 재귀로 푸는 쉬운 문제였다. 배열 정보를 받아서 한변의 길이 & x 좌표 & y 좌표 이렇게 3개의 값으로 사분면 모두를 돈다. 만약 특정 사분면의 모든 값이 같다면 더이상 자를 필요가 없으므로 해당 색상 + 1 을 해주고 해당 사분면을 확인하는 것을 종료하고 만약 특정 사분면의 모든 값이 같지 않다면 한번더 4등분해서 들어간다(재귀). def checkSame(n, x, y): global arr value = arr[x][y] for i in range(n): for j in range(n): if arr[x + i][y + j] != value: return False ..