yeony's story

> dfs > bfs 실행시간 약 112ms 해당 좌표의 위치가 집인지 그리고 해당 좌표에 방문했었는지 안했는지에 대한 조건이 중요했던 문제 from collections import deque n = int(input()) array = [[] for _ in range(n)] for i in range(n): for j in list(input()): array[i].append(int(j)) # 상,우,하,좌 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] answer = [[0 for _ in range(n)] for _ in range(n)] cnt = 1 def bfs(i, j): queue = deque() queue.append((i, j)) global cnt if a..

> BFS 처음에 떠올렸던 생각은 다이나믹 프로그래밍 근데 지나야하는 최소의 칸 수를 구해야하므로 BFS로 풀었음. 문제에서 주어진 예제 2번의 과정을 풀어보았음. 그림이 좀 지저분하긴 한데.. 일단 노란색 형광펜으로 쳐져있는 길로 가야 최소의 이동칸 수를 구할 수 있다. 오른쪽에 써있는 작대기 + 숫자는 -> 이동순서 여기서 현재 위치란 nx,ny (x,y에서 이동한 값) 1. 만약 길이라면? 1.1 방문한 적이 없는 경우라면? 1.1.1 큐에 현재 위치 append 1.1.2 현재 위치 방문처리 1.1.3 answer 리스트의 현재 위치 부분에 +=1 해주기 1.2 방문한 적이 있는 경우라면? --> *** 이 부분이 중요 *** 1.2.1 answer[nx][ny]의 값과 answer[x][y]+1..

> 자료구조 > 스택 > 재귀 https://www.acmicpc.net/problem/1662 이 문제를 풀 때 스택을 생각해내지 못하고 빡구현으로 하려고 시도했으나 처참하게 실패했다. 문자열 스택!! 문자열 문제에서 스택이 자주 쓰였던 것 같은데 왜 항상 까먹는지 이번 기회에 기억해두길.. 이 문제를 풀 때 길이가 아니라 문자열 자체를 저장해두다보니 메모리초과가 발생했다. words = input() answer = '' temp = '' stack = [] for idx in range(len(words)): if words[idx] != ')': stack.append(words[idx]) else: while True: x = stack.pop() if x != '(': # 숫자 temp+=x ..

> Dp 처음에 떠올렸던 알고리즘은 dfs였다. 그런데 dp로 풀게 되면,, 조건을 처리해주는 부분이 매우 까다로울 것 같아서 힌트를 봣더니 역시나 틀린 방법을 .. ㅎ 이 문제는 다이나믹 프로그래밍 기법을 이용하여 풀어야한다. D분 후 위치해있어야하는 곳은 정보과학관이다. 초기값은 정보과학관 전산관 미래관 신양관 한경직기념관 진리관 형남공학관 학생회관 초기값 (0분) 1 0 0 0 0 0 0 0 1분 후 정보과학관에서 전산관으로 가는 방법은 1가지 정보과학관에서 미래관으로 가는 방법은 1가지 정보과학관 전산관 미래관 신양관 한경직기념관 진리관 형남공학관 학생회관 초기값 (0분) 1 0 0 0 0 0 0 0 1분 후 0 1 1 0 0 0 0 0 2분 후 정보과학관 전산관 미래관 신양관 한경직기념관 진리관..

> 정렬 처음에 이 문제를 보고 묶음이 여러개 있어도 된다는건가?라는 생각과 함께 묶음이 짝수인 경우 묶음 안에 있는 호반우를 품질을 기준으로 정렬했을 때 (묶음개수/2+1)번쨰 호반우를 중앙값으로 정의해야한다는 글을 보고 묶음 개수가 배열에서 내가 정한 묶음의 개수를 의미하는건가..라는 생각과 함께 한참 헤매고 있었다. 그런데 묶음의 개수가 이 의미가 아니었다. 만약 배열이 [2,4,8,9]라고 가정하자. 그러면, 지금 내가 2랑 9를 묶으면 이 묶음의 총 길이는 2이다. 짝수이므로 중앙값은 2/2+1 = 2가 되니까 배열의 2번째 값인 9가 중앙값이 되는 것이다. 만약 내가 [2,4,9]라고 묶었다고 가정하면 총 길이는 3이다. 홀수이므로 중앙값은 3+1/2=2이고 우리는 최대 이익을 만들어야하기 때..

> DFS set()을 이용해 중복을 잡아냈다. 실행시간은 약 94ms array=[list(map(int,input().split())) for _ in range(5)] result=set() # 상,우,좌,하 dx=[-1,0,0,1] dy=[0,1,-1,0] def dfs(i,j,answer): if len(answer)==6: result.add(answer) return answer+=str(array[i][j]) for k in range(4): nx=i+dx[k] ny=j+dy[k] if 0

처음에 문제를 보고 헤맸던 부분은 부모 - 자식 순으로 입력이 주어지는 줄 알았다. 1번 노드가 루트 노드라는 게 문제에 딱 나와있는데, 그걸 놓쳐서 ㅠ.. 어차피 양방향 그래프로 받게 되면 상관이 없음 DFS를 이용하여 풀었다. 1번 노드부터 탐색을 시작해야한다고 문제에 나와있으므로 1번 노드부터 탐색 시작 그래프 입력받은 건 [[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]] 1번 노드 : [6.4] 2번 노드 : [4] 3번 노드 : [6,5] 4번 노드 : [1,2,7] 5번 노드 : [3] 6번 노드 : [1,3] 7번 노드 : [4] 1번 노드를 보면 6번과 4번 노드와 연결되어 있다. 6번 노드와 4번 노드는 아직 방문을 하지 않은 노드이므로 1..

dfs와 bfs를 알아야 풀 수 있었던 문제! DFS : 깊이 우선 탐색 깊게 파고들때까지 파고들다가 막히면 돌아오는 방법 즉 가장 멀리있는(깊이 있는)노드부터 탐색하는 방법 BFS : 넓이 우선 탐색 큐를 이용하여 가장 가까운 노드부터 탐색하는 방법 from collections import deque n, m, v = map(int, input().split()) array = [[] for _ in range(n + 1)] for i in range(m): x, y = map(int, input().split()) array[x].append(y) array[y].append(x) for i in range(n+1): array[i]=sorted(array[i]) dfs_visited = [Fals..

https://www.acmicpc.net/problem/2606 처음에는 그래프를 단방향으로 했다. 문제에 나와있는 예시도 통과했길래 이게 맞는 건 줄 알았는데 아니었다 ^^ 양방향으로 받아야한다. 단방향으로 받게되면 3에서 탐색이 끝나버린다. 배열 인덱스 3 위치에 있는 곳에는 아무런 노드가 없기 때문에 양항뱡으로 받으면 정상적으로 탐색이 가능해진다. 모든 노드가 연결되어 있는 경우를 생각하지 못했다. n = int(input()) connect = int(input()) array = [[] for _ in range(n + 1)] visited = [False for _ in range(n + 1)] for _ in range(connect): c1, c2 = map(int, input().spl..

temp[D[i]-1]=s[i] 를 이용하면 풀 수 있었던 문제! n, k = map(int, input().split()) s = list(map(int, input().split())) d = list(map(int, input().split())) for _ in range(k): temp = [0 for _ in range(n)] for i in range(n): temp[d[i]-1] = s[i] s = temp print(*s)