전체 글52 [BOJ] 18352 특정 거리의 도시 찾기 - python 18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 시작 노드로부터 일정한 거리의 노드를 찾는 문제이다. 거리를 저장하는 부분에서 많은 시간이 걸렸다. 처음엔 방문 여부를 저장하는 visited와 거리를 저장하는 distance list를 따로 사용하였는데, 코드를 좀 더 간결하게 만들기 위해 visited_dis 하나로 통합하였다. 처음 제출에서는 리스트 형태의 큐를 사용하였더니.. 2022. 3. 30. [BOJ] 1012 유기농 배추 - python 1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net '11724 연결 요소의 개수 문제'와 '13565 침투' 문제를 합친 문제 같았다. 실제로도 위 두 문제를 합치니 해결이 가능했다. dfs를 이용하여 더 이상 재귀를 불러올 수 없을 경우 count를 증가시켜주는 방식으로 풀었다. 나는 행렬 형태에 입력 값을 넣었는데, 백준에서 그려놓은 그림과 같이 입력을 받으려면 입력받는 x,y 값과 행렬을 호출하는 x,y값이 반대라는 것을 주의해야한다. import sys sys.set.. 2022. 3. 27. [개념] Dijkstra(다익스트라) - python 다익스트라 알고리즘 - 유향 그래프에서 간선들의 가중치가 모두 0 이상인 경우의 최단 경로 알고리즘 왜 가중치가 0 이상이어야 할까? - 다익스트라 알고리즘에서 최단 거리를 저장한 노드는 집합에 포함시켜 놓는데, 집합에 포함된 노드의 최단 거리 값은 다시 계산하지 않는다. 그러나 가중치가 음수일 경우, 최단 거리 값이 바뀌어 노드에 저장해 놓은 최단 거리 값을 바꿔야하는 경우가 발생할 수도 있다. 하지만 집합에 포함된 노드는 값을 수정할 수 없기 때문에 다익스트라 알고리즘은 간선의 모든 가중치가 0 이상일 때 성립한다. 다익스트라 알고리즘에서의 가정 두 정점 간 경로가 존재하지 않으면 경로의 가중치는 무한대로 정의한다. 두 정점 간 간선이 존재하지 않으면 가중치가 무한대인 간선이 존재한다고 간주한다. 다.. 2022. 3. 24. [BOJ] 11724 연결 요소의 개수 - python 백준 11724번 연결 요소의 개수 문제이다. import sys sys.setrecursionlimit(10000) N, M = map(int,sys.stdin.readline().split()) visited = [0]*(N+1) graph = [[0]*(N+1) for _ in range(N+1)] def dfs(n): visited[n] = 1 for i in range(1,N+1): if visited[i] == 0 and graph[n][i] == 1: dfs(i) for _ in range(M): a, b = map(int, sys.stdin.readline().split()) graph[a][b] = 1 graph[b][a] = 1 count = 0 for _ in range(1,N+1):.. 2022. 3. 23. [BOJ] 13565 침투 - python 백준 13565번 침투 문제이다. import sys sys.setrecursionlimit(1000000) M, N = map(int,sys.stdin.readline().split()) visited = [[0]*(N) for _ in range(M)] graph = [] for _ in range(M): a = list(map(int, sys.stdin.readline().rstrip())) graph.append(a) def dfs(x,y): if x = M or y = N: return if graph[x][y] == 0 and visited[x][y] == 0: # graph[x][y]가 갈 수 있는 길이고, 방문 된 적 없으면 visited[x][y] = 1 dfs(x,y-1)# 좌 dfs(.. 2022. 3. 23. [개념] BFS(Breadth-First Search) - python BFS(Breadth Fisrt Search)은 너비 우선 탐색이라는 뜻으로, 하나의 정점으로부터 가까운 노드부터 탐색하는 알고리즘이다. BFS는 그래프 탐색의 일종이다. 그래프 탐색? - 하나의 정점으로부터 시작하여 모든 정점을 한번씩 방문하는 것 직관적인 이해를 위해 먼저 트리를 대상으로 살펴보겠다. BFS는 너비 우선 탐색이라는 이름에 맞게 가로 노드들을 순서대로 방문한다. 1번 행을 모두 탐색하면 2번 행, 2번 행을 모두 탐색하면 3번행... 순서로 탐색을 이어나간다. 탐색 순서: A - B - C - D - E - F 이제는 무향 그래프에서 수행하는 BFS를 살펴보겠다. 해당 정점을 기준으로 탐색을 시작한다. 첫 번째로 방문한 노드와 인접한 노드들을 방문한다. 두 번째로 방문한 노드와 인접한 .. 2022. 3. 20. [Git] error: pathspec 'main' did not match any file(s) known to git 해결법 master 브랜치를 main 브랜치로 변경하려고 했는데 해당 에러가 발생했다. 아래 명령을 순서대로 입력하면 해결 된다. git remote update git fetch git checkout main 2022. 3. 17. [개념] 힙 정렬 - python 힙이란 무엇일까? - 최댓값 및 최솟값을 구하는 연산을 빠르게 수행하기 위해 고안된 완전 이진 트리를 기반으로 한 자료구조이다. 그렇다면 완전 이진 트리란 무엇일까? - 우선 트리는 계층적 관계를 표현하는, 노드로 이루어진 비선형 자료구조이다. 이진 트리는 모든 노드의 자식 노드가 2개 이하인 트리 구조를 말한다. 위와 같은 이진 트리 구조에서 마지막 디그리를 제외하고 모든 노드가 채워져 있는 구조를 완전 이진 트리라고 한다. 위 트리 그래프도 완전 이진 트리 형태이다. 이제 다시 힙에 대해 알아보자. 힙에는 두 가지 종류가 있다. 부모 노드의 키 값이 자식노드의 키 값보다 항상 큰 힙을 최대 힙, 부모 노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 최소 힙이라고 부른다. 최대 힙과 최소 힙에서 .. 2022. 3. 17. [BOJ] 1946 신입 사원 - python import sys T = int(sys.stdin.readline()) for _ in range(T): N = int(sys.stdin.readline()) score = [0]*N for i in range(N): # 공백을 기준으로 int형으로 나눠 각각 리스트로 저장한다. # 리스트 내에 리스트로 저장된다. score[i] = list(map(int,sys.stdin.readline().split())) # 첫번째 값을 기준으로 정렬된다. score.sort() # 서류 심사 1등은 합격이기 때문에 1로 초기화한다. count = 1 # 서류 심사 등수를 이미 정렬해놓았기 때문에, # 면접 심사에서 앞의 사람들보다 낮은 등수를 받았다면 탈락이다. # 따라서 이전에 나온 등수 최솟값(min)보다 .. 2022. 3. 16. 이전 1 2 3 4 5 6 다음
