지금은마라톤중

이번에는 DP(Dynamic Programming, 동적 계획법)에 대해 공부해봤습니다. 원래 BFS와 DFS를 했으니 다른 그래프 이론들을 공부하려다가 코테에 잘 나오는거 먼저 하자!! 해서 순서가 좀 바뀌었습니다 ㅎㅎ DP(Dynamic Programming, 동적 계획법) : 복잡한 문제를 효율적으로 해결하기 위한 알고리즘 설계 기법 중 하나입니다. 이 방법은 주로 최적화 문제를 해결하는 데 사용되며, 큰 문제를 작은 부분 문제로 나누어 해결한 후, 그 결과를 저장해두고 필요할 때 다시 사용(메모이제이션)함으로써 계산의 중복을 피하는 것이 핵심 전략입니다. 동적 계획법은 문제를 분할하여 각각의 작은 문제들을 한 번씩만 풀어 큰 문제의 해답을 구하는 방식으로, 불필요한 계산을 줄이고 효율성을 높입니다..

이번 문제에서는 런타임 에러와 시간초과로 2번 실패했었습니다. 접근법 - DFS로 접근 - 깊이 탐색 후 방문하지 않은 노드 있을 때 cnt 증가 에러해결 1. 런타임에러 - 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회 → 재귀 최대깊이는 재설정해줌 sys.setrecursionlimit(10000) 2. 시간초과 - input 대신 sys.stdin.readline을 통해 시간초과 해결 input = sys.stdin.readline import sys input = sys.stdin.readline sys.setrecursionlimit(10000) n,m = map(int,input().split()) graph = [[] for _ in range(n+1)] for _ in range(m)..

컴파일러 언어 컴파일러는 고급언어를 저급 언어로 변환하는 것입니다. 고급언어는 사람이 이해하기 쉽도록 작성된 프로그래밍 언어로 C,C++,JAVA 등이 있습니다. 저급언어은 컴퓨터 내부에서 바로 처리가 가능한 프로그래밍 언어로 기계어와 어셈블리어 등이 있습니다. 컴파일 단계와 실행 단계가 분리되어 있어, 실행시에는 컴파일하지 않고 실행만 하면 되어 실행 속도가 빠릅니다. - 종류 : C, C++, C#, JAVA 인터프리터 언어 인터프리터는 프로그래밍 언어의 소스 코드를 바로 실행하는 프로그램입니다. 인터프리터 언어는 컴파일 하지 않고 소스 코드를 한줄씩 읽어들여 실행합니다. 빌드 과정을 거치지 않아, 별도의 실행 파일이 존재하지 않고 코드 수정에 용이하다는 장점이 있습니다. 컴파일 과정이 없기 때문에 ..

이 문제 역시 그래프 탐색 문제입니다. 접근법 - DFS로 접근 - DFS로 탐색하면서 cnt를 증가하여 단지 내 건물 수 체크 - 건물 수 담은 리스트 활용하여 결과 출력 n = int(input()) matrix = [] visited = [[False] * n for _ in range(n)] cnt_list = [] dx = [0,0,1,-1] dy = [1,-1,0,0] # mapping matrix for _ in range(n): m = input() matrix.append(m) def dfs(matrix,x,y,visited): global cnt if x = n or y = n : return 0 if matrix[y][x] == "0" or visi..

접근법 - 2명 사이의 촌수를 계산해야하니 DFS로 접근 - 촌수를 계산할 수 없을 때 -1 출력해야하니 check 변수 사용 from collections import deque n = int(input()) a,b = map(int,input().split()) num = int(input()) check = False graph = [[] for _ in range(n+1)] visited = [0] *(n+1) for _ in range(num): x,y = map(int,input().split()) graph[x].append(y) graph[y].append(x) def dfs(graph, c, visited, cnt): visited[c] = 1 global check if c == b :..

이 문제는 BFS에 대해 하나도 모를 때 한번 도전했다가 실패했던 문제입니다. 최근에 DFS와 BFS에 대해 공부해서 다시 도전해봤습니다. BFS로 접근하였고 너비우선탐색이니 큐를 활용했습니다. from collections import deque t = int(input()) dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(matrix, a,b): queue = deque() queue.append((a,b)) matrix[a][b] = 0 while queue: x,y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx = n or ny = m : continu..

그렇습니다. DFS와 BFS입니다..ㅎㅎ 알고리즘을 공부하며 미루고 미루고 미루다가 직면했습니다..하하하 DFS(깊이우선탐색)과 BFS(너비우선탐색)은 코딩테스트에 필수적인 문제 중 하나라고 생각합니다. 알고리즘을 접하지 얼마되지 않았을때 너무 어려워서 외면했는데 최근 기업 공채 코딩테스트를 봐보니 이제는 마주할 때가 되었다고 생각했습니다. DFS(Depth First Search)와 BFS(Breadth First Search)를 탐색 알고리즘입니다. 데이터 속에서 원하는 데이터를 찾을 때 깊이와 너비를 우선적으로 고려하여 탐색하는 방법으로 차이를 둘 수 있습니다. - DFS와 BFS 탐색 그래프 DFS BFS 탐색과정 현재 노드에서 갈 수 있는 끝까지 방문하여 탐색 현재 노드에서 연결된 노드를 방문 ..

가끔 알고리즘 문제를 풀었지만 오랜만에 포스팅 합니다. 이번 문제에서 놓치고 있던 지식을 상기시켰습니다. 바로 자료형의 시간 복잡도 입니다. 기존에 시간초과가 발생했을 때 주로 입력부분과 불필요한 반복문에서 시간초과가 많이 발생하여 자료형에 따른 시간 복잡도를 놓쳤습니다. 이번 문제로 한번 더 상기시킬 수 있는 기회였습니다. 시도 1. input(), list() 활용 - 시간초과로 실패 n,m = map(int, input().split()) n_lst = [ input() for _ in range(n)] m_lst = [ input() for _ in range(m)] lst = n_lst + m_lst lst.sort() total_lst = [] for i in lst : if lst.count..