문제  이 문제를 처음 풀려고 했을 때는 너무 어렵게 느껴졌다. BFS로 풀어야되는 건 금방 알겠는데 어떻게 테두리 영역만 따로 구하고 테두리 영역중에서 구멍이랑 맞닿은 테두리 부분은 제외 해줘야할 지 감이 잘 안잡혔다.  하지만 이 문제는 생각을 조금만 다르게 해주면 금방 풀린다. 처음에는 치즈의 영역에 너무 집착 했는데 반대로 공기의 영역을 먼저 구해주면된다.  공기의 영역을 어떻게 구해주냐하면 가장자리는 항상 공기 부분이 되기 때문에 0,0 지점부터 BFS를 시작하여 인접한 부분중에 0인 부분만 방문해주면 된다. 그렇게 되면 구멍 부분을 제외한 공기부분이 전부 방문 처리 된다.   위 내용에 대한 그림 예시이다. 빨간색으로 칠한 부분이 전부 방문 처리 되게 된다. 이렇게 방문처리 해준 후 치즈가 있..

문제     처음 이 문제를 보고 찾은 풀이법은 수의 최대길이가 8까지 이기때문에 모든 단어의 길이를 8로 맞추고 '*****AAA''*****AAA' 이렇게 적용된 단어들이 든 배열을 0번째 인덱스부터 확인하면서 가장 앞의 자리가 높은 숫자를 가지도록 해서 문제를 풀어주었다. 그러나 계속 해서 오답이 나왔다 ... 오답코드n = int(input())vocas = []dic = {}nums = [0,1,2,3,4,5,6,7,8,9]for _ in range(n): tmp = input() l = len(tmp) vocas.append('*' * (8-l) +tmp)vocas.sort(key = lambda x:len(x))for i in range(8): for voca in vo..

문제   이 문제는 어떤 알고리즘을 사용해야할 지는 쉽게 감이 잡히는데 조건이 많아서 이걸 다 충족하면서 구현하는게 까다로웠던 문제이다.특히 BFS를 활용하는데 이동대상이 하나가 아니다보니 이걸 변형하는걸 생각하는게 어려웠던 문제였던 것 같다. (사실 조금만 변형하면 되는 문제임에도 불구하고 처음으로 접해보다보니 고정관념에 사로잡혀 쉽게 생각해주지 못햇던 것 같다.)  일단 BFS 알고리즘을 활용하는데 이때 while문을 돌때 보통 하나의 대상에 대해서만 이동가능 좌표를 추가해줬다면 이 문제에서는 고슴도치의 이동 가능 좌표, 물의 이동가능 좌표를 같이 추가해주면 된다. 정답코드from collections import dequer,c = map(int, input().split())graph = [lis..

문제    이 문제를 처음봤을 때 생각이 난 알고리즘은 dfs/bfs , 플로이드 워샬이 있었다.그런데 더 간단한 문제로 풀 수 있었다. 바로 union-find 알고리즘   왜냐하면 도달할 수 있는 경로란 결국 같은 집합에 속한 원소라는 뜻이다. 그래서 같은 집합에 속한 원소들의 부모를 하나로 통일해준 뒤 경로에 포함된 원소가 서로 다른 부모를 가진다면 분리된 집합이라는 뜻으로 도달할 수 없는 경로임을 알 수 있다. 정답코드n = int(input())m = int(input())def union(x,y): x = find_parent(x) y = find_parent(y) #작은걸로 부모를 통일 if x      간단하게 풀릴 수 있는데 dfs를 써서 하느라 고생했다.참고로 df..

문제  일단 이 문제를 보면 구현해야할 로직이 크게 두가지 이다.  1.  빙산 깎기2. 몇 덩어리인지 확인   이게 매 해마다 반복되고 종료조건이 충족되면 종료하도록 해주면 된다. 먼저 빙산깎기는 이중 for 문 으로 돌면서 값이 0이상인 곳에 들어가면 동서남북의 0의 개수를 구한 후 빙산을 깎아주면 된다  이때 이중 for문을 돌면서 순차적으로 각 칸의 값을 갱신하는데 이 값이 매해마다 달라지는 것이므로 같은 해에 변경된 값이 다른 좌표의 값에 영향을 줘서는 안된다.그래서 값을 갱신하기 전에 tmp에 빙산값을 받아서 갱신되지 않은 값을 기준으로 주변 0의 개수를 세도록 해주었다. 그런데 빙산의 값은 2차원 배열이므로 단순히 대입이 아니라 deepcopy를 사용해서 저장해주었다.  그리고 몇 덩어리인지..

문제     처음 이 문제를 보았을 때  한 정점에서 다른 모든 정점까지의 거리가 아니라 1번정점에서 N번정점으로 가는 최단거리를 물어보다 보니 플로이드-워샬 알고리즘으로 풀어주려고 했다.  하지만 N의 범위가 800까지로 N의 세제곱이되는 플로이드-워샬의 시간복잡도를 생각하면 시간초과가 우려된다는 것을 알 수 있다.그리고 역시나 시간초과가 떴다.  그래서 어떻게 하나 고민하던 찰나 이 문제에는 특정한 조건이 있다 바로 v1, v2 노드를 반드시 거쳐서 가야한다는 점  그렇게 되면 가능한 루트는 딱 두가지가 된다. 1.  1번노드 -> v1 -> v2 -> N2. 1번노드 -> v2 -> v1 -> N   그렇기 때문에 다익스트라 알고리즘으로도 풀 수가 있다.  이게 무슨 뜻이냐면은 다익스트라 알고리즘은..

문제   이 문제에서 가장 유의해야할 점은 시간복잡도이다 왜냐하면 첫째줄에 주어지는 문자열의 길이의 범위가 굉장히 크기때문이다. (그래서 초반엔 시간복잡도 오류가 많이 발생함;;)먼저 이 문제를 어떤 알고리즘으로 풀어야할지 생각을 해본다면 단순히 폭발문자열이 들어가있는 때는 간단하지만 "CC44"처럼 연속해서 오는경우가 까다로워 진다. (while문으로 없을 때까지 확인하면 시간초과가 발생)그런데 이 문제 잘 생각해보면 괄호여닫기와 굉장히 유사하다는 것을 알 수 있다. 그래서 stack 을 사용하면 이 문제를 풀 수 있다.  for 문으로 첫번째 문자열을 돌면서 폭발문자열이 들어가면 pop해주는 형식으로 구현해주면 된다. 이때 구현하면서 한가지 실수를 했는데   오답코드 string = input()b..

문제     이 문제에서 고려해야하는 것은 크게 2가지이다 1. 가로, 세로에 1~9까지의 숫자가 한번만 나타나야 한다.2. 굵은 선으로 구분된 정사각형안에 1~9가 한번만 나타나야한다.   이 조건을 해결하기 위해 함수를 따로 만들어 주었다. 그리고 이 문제는 완전탐색을 해주어야하는데 최대한 효율적으로 확인하기 위해 백트래킹 기법을 사용해주었다.   전체코드 sdoku = [list(map(int,input().split())) for _ in range(9)]#x행을 확인하는 함수def row(x,a): for i in range(9): if a == sdoku[x][i]: return False return True#y열을 확인하는 함수def col(y,a..

문제    사실 이 문제는 어떤 알고리즘을 써야 할지 전혀 감히 잡히지 않았던 문제였다. 구글링을 통해 이분탐색을 써야 된다는 걸 알게 됐지만 그래서 target이 뭔데....? 라는 생각만 들고 감이 안잡혔었다. target이 명시적으로 딱 주어지지 않더라도 이것을 뽑아내는 능력을 좀 길러야 할 것 같다.  이분 탐색을 활용해 풀어보자면, 목표는 C개를 설치할 때의 간격(mid)의 최댓값을 찾는 것이다.공유기 개수를 조정하면서 mid 값을 점점 키워가며 탐색한다.탐색 과정에서 C개를 설치할 수 있으면 mid를 더 키워도 되는지 확인하기 위해 start = mid + 1을 진행한다.반대로 C개를 설치할 수 없으면 간격이 너무 크다는 뜻이므로 end = mid - 1을 줄인다.이 과정을 start 마지막으..

문제   이 문제를 보고 처음 생각이 든 알고리즘은 LIS이다.그러나 문제는 최장 증가 부분수열이 아니라 바이토닉수열로 어떤 수를 기준으로 오른쪽 부분은 감소하는 부분수열도 찾아주어야한다.  그래서 생각한 방법은 최장증가 부분수열을 구하고 최장감소 부분수열을 구해서 이 둘의 합이 최대가 되는 지점을 찾아주는 것이다.   정답코드n = int(input())a = list(map(int,input().split()))ans = 0dp1 = [0] * ndp2 = [0] * n#최장 증가 부분수열for i in range(n): dp1[i] = 1 for j in range(i): if a[i] > a[j]: dp1[i] = max(dp1[i],dp1[j]+1)#최..