baekjoon73 백준 알고리즘 2667번: 단지번호붙이기 문제 정보 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 핵심 DFS, 백 트래킹 알고리즘을 사용하여 풀이하는 문제 5= 0 && col < size); } } NxN 배열에서 왼쪽 가장 위(0,0) 위치부터 오른쪽 가장 아래(N-1, N-1)까지 DFS를 통하여 인접한 위치로의 깊이 우선 탐색을 하여 지도의 값이 1이면 visited를 true로 만들어 주며, 해당 위치에서 다시 깊이 우선 탐색을 실시한다 한번 탐색할 때마다 count를 계속 올려주고, 계산이 끝났다면 이를 countList 리스트에 넣어 .. 알고리즘/Java 2023. 10. 23. 백준 알고리즘 1260번: DFS와 BFS 문제 정보 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 핵심 DFS와 BFS에 대해서 알고 있는지? 그래프를 탐색하는 알고리즘에 대한 지식을 가지고 있는지? 그들을 어떤 Data Structure를 통해 구현해야 하는지 알고 있는지? 개인적으로 내부 알고리즘에서 중요한 요소는 이렇게 된다고 생각한다 - 해당 노드를 방문했는지 확인하는 boolean visitied[] - 노드들 사이 간선을 판단하는 boolean edge[][] - BFS의 경우 FIFO를 가능케 하는.. 알고리즘/Java 2023. 9. 19. 백준 알고리즘 1015번: 제곱 ㄴㄴ 수 문제 정보 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 핵심 에라토스테네스의 체 알고리즘을 활용하여 해당 범위 내에 있는 제곱 ㄴㄴ 수를 찾아낸다 여기서 제곱 ㄴㄴ 수란, 1보다 큰 제곱수로 나누어 떨어지지 않는 수이다. 1부터 10까지의 제곱 ㄴㄴ 수를 알아보면 1 2 3 (4) 5 6 7 (8) (9) 10 4(2의 제곱) 으로 나누어지는 4, 8은 제곱 ㄴㄴ 수가 아니고, 9(3의 제곱) 으로 나누어지는 9는 제곱 ㄴㄴ 수가 아니므로 이를 제외한 나머지 숫자들이 제곱 ㄴㄴ 수가 된다 .. 알고리즘/Java 2023. 9. 6. 백준 알고리즘 1644번: 소수의 연속합 문제 정보 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 핵심 일반 풀이와 투 포인터를 활용한 풀이가 두가지가 있다 무조건 에라토스테네스의 체 알고리즘을 활용하여 문제를 풀이하여야 하며 해당 개념은 이전에 올렸던 글에서 참고할 수 있다 (아래 참고 링크 확인) 위 두가지 풀이 모두 파이썬 기준 백준 제출시 통과되지만, 효율성은 투 포인터가 훨씬 좋다 풀이 일반 풀이 import sys N = int(sys.stdin.readline()) prime = [True for _ in range(N+1)] prime[0], prime[1] = False, False for i in range(2, int(N**0.5) + 1): if.. 알고리즘/Python 2023. 7. 2. 백준 알고리즘 2485번: 가로수 (Python) 문제 정보 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 핵심 최대공약수 문제다! 라는 것을 빠르게 캐치하여야 함 일일히 최대공약수를 구하는것은 정말 비효율적이니, 유클리드 호제법을 통해서 구하는 것이 올바른 풀이이다 각 가로수의 간격들의 전체 최대공약수를 구하고 이 간격에서 비어있는 가로수의 개수를 찾아서 출력해주면 된다 풀이 from sys import stdin N = int(stdin.readline()) tree = list(map(int, stdin.readlines())) def GCD(.. 알고리즘/Python 2023. 6. 29. 이전 1 ··· 6 7 8 9 10 11 12 ··· 15 다음
