본문 바로가기

CS/알고리즘29

[백준 11724 연결 요소의 개수] 파이썬 BFS 너비 우선 탐색 풀이 연결 요소의 개수 문제 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 뱡향 없은 양방향 그래프가 주어졌을 때 연결 요소를 구하는 문제입니다. 문제 풀이 연결 요소를 구하는 것은 즉 몇개의 구역으로 나누어져 있는지 구하는 문제입니다. 그래프를 위와 같이 표현했을때 2개의 영역으로 이루어져 있습니다. DFS, BFS 모두 사용해서 풀수 있는 문제입니다. 너비 우선 탐색 BFS로 문제를 풀어보겠습니다. 1. 그래프 연결 정보용 행렬 생성 2. BFS.. 2020. 9. 28.

[백준 1012 유기농 배추] 파이썬 BFS 너비 우선 탐색 풀이 유기농 배추 문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 2차원 배열의 유기농 배추밭이 주어지고 0(땅) 과 1(배추 심어져 있는 땅)로 데이터가 구분됩니다. 배추흰 지렁이를 배추에 서식하게 하면 사방면으로 이동이 가능하여 다른 배추를 해충으로부터 보호가 가능하다. 필요한 배추흰 지렁이의 마리수를 구하는 문제입니다. 입력 받는 정보로 아래와 같이 배추 밭을 2차원 배열 형태로 만들어 주어야 합니다. 문제 풀이 4방면으로 이동이 가능하므로 각 영역당 한마리의 배추흰 지렁이를 배치하면 해결할 수 있습니다. 즉, .. 2020. 9. 28.

[백준 10026 적록색약] 파이썬 BFS 너비 우선 탐색 풀이 적록색약 문제 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net RGB 3가지 문자로 이루어진 N * N 보드판이 주어질때 일반사람과 적록색약인 사람이 보는 구역의 수를 각각 구하는 문제입니다. 적록색약은 R과 G를 하나의 색으로 보입니다. 즉, 아래와 같이 구역이 나뉘게 됩니다. 문제 풀이 2차원 배열의 영역을 구하는 문제로 BFS 너비 우선 탐색 알고리즘을 사용해서 풀면 될것으로 판단했습니다. 단, 2가지 경우가 발생하기 때문에 2가지 버전의 배열을 만들어주고 탐색하는 방식을 선택했습니다. N의 최대 .. 2020. 9. 27.

백준 14500번 테트로미노 완전탐색(brute-force) 알고리즘 문제 :: 코드자몽 [백준] 14500번 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 풀이 이런 블록 형태의 문제가 나오면 실제로 도형을 그려보면서 문제를 푸는 것이 가장 좋은 방법인 것 같다. 먼저 N*M 크기의 종이 위에 블록 하나만 놓는다고 했으니.. 2019. 12. 23.

백준 2309번 일곱 난쟁이 완전탐색(brute-force) 알고리즘 문제 :: 코드 자몽 완전 탐색 Brute-Force 완전 탐색은 말 그대로 모든 경우의수를 일일이 탐색하여 정답을 찾아내는 알고리즘이다. 가능한 방법을 모두 확인하여 정확도가 높고 강력한 방식이지만, 시간은 다소 오래 걸리는 단점이 있습니다. 그래서 브루트 포스 알고리즘을 사용하기 전에 문제의 가능한 경우의 수를 먼저 계산을 해봐야한다. 컴퓨터가 1초에 대략 1억 번 정도의 일을 할 수 있다고 한다. 효율성을 고려하여 브루트 포스 알고리즘으로 문제를 접근할 경우 기준은 정해주는 것이 좋다. 예를 들어 "천만(10,000,000) 건 이하의 경우 수가 존재할 때만 브루트 포트 알고리즘을 사용하겠다."라는 기준을 정하고 문제를 접근하는 것이 유리하다. [백준] 2309번 일곱 난쟁이 2309번: 일곱 난쟁이 아홉 개의 줄에 걸.. 2019. 12. 23.

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽 소수(Prime Number) 소수는 자신보다 작은 두개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. ex) 5는 5*1 또는 1*5로 수를 곱합 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 소수 (수론) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 좌측은 소수, 우측은 합성수. 소수란 자신보다 작은 두 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 .. 2019. 12. 22.

최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽 최대공약수 GCD(Greatest Common Divisor) 최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다. ex) 72 와 30의 최대공약수는 6이다. 최소공배수 LCM(Least Common Multiple) 최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다. 최소공배수 = 두 자연수의 곱 / 최대공약수 ex) 72 와 30의 최소공배수는 360이다. 유클리드 호제법(Euclidean Algorithm) 2개의 자연수를 받아 최대공약수를 받기 위해 2부터 두 자연수 중 작은 자연수까지 모두 나누어보면서 가장 큰 공약수를 구할 수 있다. 위와 같은 방법으로 문제를 풀면 시간복잡도는 O(N)이 된다. 나쁜 방법은 아니지만 효율을 높이기 위해 유클리드 호제법이란 알고리즘.. 2019. 12. 22.

JAVA 자바로 비트연산 알아보기 :: 코드 자몽 비트연산자 비트연산은 2진수형태의 숫자 0과 1로 할 수 있는 연산이다. 자바에서 기본적으로 사용할 수 있는 연산 6가지를 알아보자.비트연산자를 잘 사용하면 알고리즘을 다양한 방법으로 작성할 수 있을 뿐더러 시간복잡도를 줄여 주는 효과를 볼 수 있다. 왼쪽 시프트( y 형식으로 연산자를 사용하면 되고 x의 비트를 왼쪽으로 y칸 이동시킨다는 것을 의미한다.ex) 1111 >> 2 = 111111(15) 이 11(3)로 변형되는 것을 보면 x / 2^y 으로 나머지를 제외한 몫을 반환한다. 비트의 보수(~)이진수의 모든 비트를 반대로 바꾼다. 0 이면 1, 1이면 0으로 바꾼다. 보수를 사용할 경우 32자리를 기준으로 값을 반환한다.~x 형식으로 연산자를 사용하고 x의 보수를 구하라는 의미이다.ex) ~01.. 2019. 11. 23.

[배열] 부분집합 관련 문제 비트연산으로 풀기 :: 코드자몽 부분집합 구하기 배열이 주어졌을때 부분집합을 구하는 코드를 작성해보자. 아래 기본 문제를 설명 및 코드샘플을 확인하지 않고 먼저 풀어보자. 기본 문제 {1, 2, 3, 4, -1, -5} 위 배열에서 홀수로 구성된 부분 집합을 모두 출력 하시오. 간단해 보이지만 비트연산을 이해하지 못하면 생각보다 어려운 문제이다. 위 문제를 완전탐색 혹은 배열의 위치를 이용해서 풀겠다고 접근했을것이라 생각합니다. 완전탐색 방법으로 풀려고 하다보니 for문을 중첩해서 사용하면 배열이 커질수록 효율도 떨어지고 시간복잡도가 제곱으로 늘어나는 것을 확인했을 것입니다. 그럼 배열의 위치를 이용해서 푸는 방법을 생각하다보니 0과 1을 이용하여 자리를 표시하는 방법이 떠오르게 될것입니다. 위의 문제 처럼 부분집합을 구하는 문제에서는.. 2019. 11. 22.

이전 1 2 다음

티스토리툴바