그래프이미 DFS와 BFS에 대해서 글을 작성했지만, 그 전에 그래프에 대해 먼저 알고 가야한다. 그래프의 정의는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용하는것이고,간선은 방향이 없거나, 방향이 있을 수 있다. 코딩테스트에 자주 나오는 자료구조이므로 꼭 이해하고 있어야한다.탐색( DFS, BFS ), 트리에서도 사용한다. 그래프를 구현하는 3가지 방법은엣지 리스트 (순서에 맞게 배열에 저장하는 방식으로 사용 불편)인접 행렬 (2차원 배열 구조로 공간 복잡도 제약)인접 리스트 (ArrayList로 구현, 가장 많이 사용)인접리스트를 나도 가장 많이 사용했고, HashMap이나 ArrayList로 구현을 하면된다. 종류1. 가중치가 없는 ..

문제 설명한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.제한사항numbers는 길이 1 이상 7 이하인 문자열입니다.numbers는 0~9까지 숫자만으로 이루어져 있습니다."013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.입출력 예numbersreturn"17"3"011"2 입출력 예 설명 예제 #1[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다..

문제과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.입력첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.출력첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집..

드디어 DFS, BFS를 공부할 시간이 왔다.예전에 파이썬으로 코테 준비할때 찍먹한 적 있는데, 이번에 제대로 배워보려고한다.(사실 조합 & 순열 공부할 차례인데 DFS로 해야 제일 쉽게 풀 수 있단다,, 백트래킹에서도 써먹고) DFS&BFS는 그래프 탐색 알고리즘이라고도 한다. 대표적인 문제 유형경로탐색 유형 (최단거리, 시간)네트워크 유형 (연결)조합 유형 (모든 조합 만들기)DFS - 깊이 우선 탐색DFS는 루트 노드(or 일반 노드) 에서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방식이다.주로, 재귀함수나 Stack으로 많이 구현한다고 한다.ex) 미로찾기에서 길을 찾다가 길이 막히면 마지막 갈래길로 돌아가는 방식 BFS - 너비 우선 탐색BFS는 DFS와 다르게 자..

백준 9012번 : 괄호문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으..

유클리드 호제법최대공약수(GCD) , 최소공배수(LCM)를 구할떄는 유클리드 호제법을 쓰는게 제일 구현하기 간단함.유클리드 호제법은 최대공약수를 구하는 알고리즘인데, 최소공배수는 그냥 두 수를 곱한 뒤에 최대공약수를 나누면 되니까,, 뭐 그렇게 구현하면 된다 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 라고 나무위키에 나와있는데 간단히 설명하면 -  a 와 b의 나머지(r1)를 구하고 (a>b)-  r1 과 b의 나머지(r2)..

첫 게시물블로그를 깃허브랑 노션에 나눠서 하다보니 불편해서 앞으로는 여기다가 다 정리하려고 한다.마음을 불태워라. 에라토스테네스의 체에라토스테네스의 체는 이미 파이썬으로 한번 해봤는데 이번에 자바로 코테 언어 바꾸면서 다시 정리해보려고 한다.소수를 판별하기 위해서static boolean check_prime(int num){ if(num == 1){return false;} for(int i = 2 ; i물론 이렇게 작성해도 되는데, 시간복잡도가 O(N)으로 직관적이지만 느린 코드이다. 에라토스테네스의 체는 소수를 판별할때 쓰는 대표적인 알고리즘인데, 작동 원리는2부터 N까지 모든 정수를 적는다.아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소..