Seung's Learning Record

난이도 : 실버2 소요시간 : 57분 사용한 풀이법 : dfs_재귀, bfs_큐 풀이 과정 입력받은 n값에 대한 탐색용 배열 생성 후 false 초기화 bfs, dfs 각각의 방문 탐색용 배열 생성 후 false 초기화 m에 대해 반복문 돌리면서 입력된 값들에 해당하는 인덱스 값 True 변환 각각의 행의 값들 중 True값은 연결된 엣지의 번호를 뜻함 ex) 1번 행의 3,4열이 true이면, 1-3/1-4 연결된 것! bfs는 큐를 이용한 풀이 python 특성상 queue보다 deque가 효율적이라서 deque사용 dfs는 재귀를 이용한 풀이 스택으로 할라다가 실패함ㅎ.. 작성 코드 from collections import deque n,m,v = map(int, input().split(' ')..

난이도 : 골드5 소요시간 : 47분 사용한 풀이법 : bfs 풀이 과정 1. color 입력 받는 동시에 배열에 삽입 2. for문 돌면서 미방문한 곳 발견 시 bfs() 호출 3. bfs()함수에서는 호출 된 부분의 색과 동일한 곳만 탐색 4. 탐색이 끝나면 normal++ 후 bfs 재호출 5. color배열 탐색 종료 후, 적록색약 버전 카운트위해 vis[][] 0으로 재초기화 6. color배열의 'G'를 'R'로 대치 7. bfs()호출 및 blind++과정 반복 8. normal과 blind 각각 출력 작성 코드 #include #include #include using namespace std; queue Q; char color[101][101]; int vis[101][101]; int..

난이도 : 실버2 소요시간 : 1시간 9분 사용한 풀이법 : bfs,queue 풀이 과정 1. 테스트 케이스 시작 때 마다 vis[][], bc[][] 배열 0으로 초기화 2. 배추 위치 입력 들어올 때 마다 bc[][]배열 1 삽입 3. for문 돌면서 방문 이력이 없으면서 배추가 있는 곳을 만나면 bfs 실행 => 하나의 배추 군단이 끝나면 bfs종료 후, cnt++됨 4. cnt값 출력 작성 코드 #include #include #include using namespace std; queue Q; int bc[50][50]; int vis[50][50]; int t,n,m,k,x,y; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int d..

BFS(Breadth First Search) BFS란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 시작 정점을 방문한 후, 인접한 정점들을 우선 방문하는 방법이다. 해당 그래프의 방문 순서가 저럴 경우, 큐에 값이 들어가고 나가는 순서는 다음과 같다. push(0) -> pop(0) -> push(1), push(2) -> pop(1) -> push(3) -> pop(2) -> push(4) -> pop(3) -> pop(4) BFS구현 이론 BFS 구현을 위해서는 큐를 사용해야 한다. 쉬운 이해를 위해 빨간색,파란색이 섞여있는 2차원 배열에서 파란색 칸만을 탐색하는 알고리즘을 작성하는 과정을 예로 들어 구현 플로우를 대강 정리해보자. 시작 좌표(0,0)를 방문 표시 후,..

브루트 포스? 브루트 포스(brute force)의 사전적 의미는 '무식한 힘'이다. 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 '해가 하나 이상 존재한다.'는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 복잡한 알고리즘없이 빠르고 쉽게 구현이 가능하다는 장점이 있지만, 알고리즘의 실행시간이 오래걸리며 메모리 효율성이 떨어진다는 단점이 있다. 종류 선형 구조 : 순차탐색 비선형 구조 : 백트래킹, DFS, BFS 선형 구조 - 순차탐색 순차 탐색(Sequential Search)는 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로..