본문 바로가기

전체 글82

[백준] 14940번: 쉬운 최단거리 파이썬 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 오늘의 백준 문제는 14940번 쉬운 최단 거리 ~ (근데 난 별로 안쉽더라) 풀이 이 문제는 bfs로 풀어야한다. 지도가 2차원 배열로 주어지고 목표 지점에 대한 최단거리를 모두 구하면된다. 일반적인 bfs문제와 같다. visted를 미리 -1로 초기화해놓고 아예못가는 부분은 0을 넣었다. from collections import deque impo.. 2024. 4. 3.
[백준] 11724번: 연결 요소의 개수 파이썬 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 백준 11724번 연결요소의 개수 문제는 dfs, bfs 어느 걸 써도 풀 수있다. 난 bfs로 풀었다. bfs 헷갈린당. 계속 연습하자 풀이 일단 입력으로 방향없는 그래프가 주어진다. 간선 의 양 끝점을 받아서 2차원 리스트로 저장합니당. 파이썬 bfs는 큐로 구현합니다. 큐는 시간복잡도를 고려해서 deque 라이브러리를 활용해 구.. 2024. 4. 2.
BFS(너비우선탐색) python으로 구현 Breadth First Search, BFS오늘은 BFS를 알아보자BFS는 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법루트에서 시작한다.자식 노드들을 [1]에 저장한다.[1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.[2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.위의 과정을 반복한다.모든 노드를 방문하면 탐색을 마친다.그림을 보면, DFS는 갈림길에서 하나의 길로 들어서서 막다른 길이 나올 때까지 깊게 탐색을 하는 것을 볼 수 있고, BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 넓게 탐색하는 것을 볼 수 있다. 코드 구현 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김큐에서 .. 2024. 4. 1.
UMC(University MakeUs Challenge) 5기 후기 umc 5기 수료하고 적는 글 이 글을 검색해서 보고있는 사람이면 다 알겠지만 UMC(University MakeUs Challenge)는 대학생 IT 연합 동아리로, 다양한 대학의 학생들이 모여서 개발을 하는 동아리 이다. 일단 이 동아리 들어가게된 계기는..내가 컴퓨터공학과 전과를 코로나 비대면 시기에 해서 동아리나 외부활동 경험이 너무나 부족했기떄문이다.그냥 생각없이 비대면 수업만 열심히 들었다. 그래서 학점만 높았다.. 어쨋든 4학년인데 뭐라도 해야할 거 같다라고 생각하던 순간 학과 단톡방에 올라온 umc 홍보글을 보았다. 마침 저번학기에 웹프로그래밍 수업들으면서 기초 웹 프로그래밍 지식이 있다고 생각해서 바로 지원했다.면접은 비대면 zoom으로 진행했다. 면접질문으로는 간단한 웹프로그래밍 지식을.. 2024. 3. 26.

티스토리툴바