728x90 전체 글126 [BOJ 16234 파이썬] 파이썬 인구이동 BFS문제풀이 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 전형적인 BFS문제이다. BFS 탐색 시 처리해주어야할 예외는 국경이 열려있는지를 먼저 처리하고, 열려있을 시에 연합으로 리스트를 만들어주기만 하면 된다. 이 문제에서 주의해야할 점은 BFS 한번으로만 끝낼 생각을 하면 안된다는 것이다. 대부분의 dp,DFS 등의 알고리즘들이 단 한번 탐색하고 마는데, BFS는 이 문제와 비슷하게 여러번 탐색해야하는 경우가 많다. 즉, 땅에 대해서 BFS를 진행하는데, BFS를 한번만 하고 끝 나는것이 아니라, 국경.. 2022. 6. 21. [BOJ 1068 파이썬] 파이썬 트리 BFS 풀이 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 이 문제를 처음 보자마자 든 생각은 BFS로 풀면 되지 않을까? 였다. 먼저, 지워질 노드를 고려하지 않고 모든 노드들을 edge로 연결해주어 그래프를 만들어주었다. 이후, BFS로 탐색 하되 삭제한 노드로는 탐색하지 않게끔 예외를 주고, 부모노드가 삭제되었을 때의 예외를 해주었다. 루트노드는 연결 edge가 하나 밖에 없으므로 탐색시 연결 edge가 하나라면 답에 더해주었다. 그래서 처음 완성한 코드가 from collections import deque.. 2022. 6. 21. [알고리즘] 브루트포스(brute force) 기법 정리 Goal 1. 브루트포스 알고리즘이 무엇인지에 대하여 정확히 이해한다. 2. 브루트포스 알고리즘이 쓰이는 문제의 종류에 대하여 정리한다. 브루트포스(brute force) 알고리즘이란? 브루트포스 알고리즘이란, 완전 탐색 알고리즘을 말한다. 즉, 가능한 모든 경우의 수를 탐색하면서 조건문을 통해서 요구조건이 충족되는 결과를 도출해 낸다. 모든 경우의 수를 탐색한다 -> 예외 없이 100%확률로 답을 가져올 수 있다. - 알고리즘 설계의 가장 근본적인 방법은 해가 있을 곳을 예상해서 탐색하는 것이다. - 브루트포스 알고리즘은 전체 구역을 탐색한다. - 전체 구역을 탐색하는 방법은 선형구조를 전체 탐색하는 순차 탐색 (반복문을 통한 전체 순차 탐색), 비선형 구조를 전체 탐색하는 DFS(깊이 우선 탐색), .. 2022. 2. 23. [JAVA] 스택(Stack) Goal - 스택(Stack)의 각 함수의 시간복잡도를 구할 수 있다. - 자바로 스택(Stack)을 구현할 수 있다. 스택(Stack)의 개념 LIFO(Last in First Out) 구조의 선형 자료구조 즉, 가장 최근에 넣은 데이터만 pop()을 통해서 뽑아낼 수 있다. 스택(Stack)의 함수 push() public E push(E item) { addElement(item); return item; } 자바 라이브러리에서 구현한 함수를 봤을때, 우선 Generic을 사용해서 여러 자료형의 Data 혹은 객체가 Stack에 들어올 수 있게 해주었고, 부모 클래스인 Vector에 있는 addElement를 통해서 데이터를 push하고 있는 것을 알 수 있다. 단순 데이터를 맨마지막에 집어넣는 작.. 2022. 2. 19. 이전 1 ··· 27 28 29 30 31 32 다음 728x90
