[알고리즘] 소수 구하기 _ 에토체
소수는 1과 자기자신외에 약수가 존재하지 않는 수입니다. 소수 구하기는 에라토스테네스의 체를 사용합니다. 에라토스테네스의 체 원리 구하고자 하는 소수의 범위만큼 1차원 배열을 생성 2부터 시작하고, 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. --> 이때, 이전에 지워졌던 수, 즉, 처음으로 선택된 수는 지우지 않는다. 배열의 끝까지 순서 2번을 반복한 후 배열에서 남아있는 모든 수를 출력한다. 위 그림의 코드 시간복잡도 이중 for 문을 사용해서, 보통 시간복잡도는 O(N^2)으로 알고 계신분들이 많습니다. BUt, 실제 시간복잡도는 최적화의 정도에 따
[알고리즘] 그래프
그래프 그래프는 노드와 간선(엣지edge)로 구성된 집합이다. 노드 : 데이터를 표현하는 단위 엣지edge : 노드를 연결하는 선 크게, 유니온 파인드, 위상 정렬, 다익스트라, 벨만-포드, 플로이드-워셜, MST(최소신장트리) 가 있습니다. 유니온 파인드 (그래프에서) 그래프의 사이클이 생성되는지 판별하는 알고리즘 --> 사이클의 유무를 판별한다고 보면됩니다. 위상 정렬 사용 가능한 조건이 있습니다. 싸이클이 없어야한다. 방향이 있는 그래프여야한다. (단방향) --> 어찌보면 당연한 말입니다. 싸이클이 없으니까, 방향이 있다는 소리 특징 : 값이 유일하지 않다. >다시 말해, 조건 -> 사이클 x, 방향 간선이며, 노드를 연결해주는 알고리즘이다. --> 정렬 결과가 꼭 1개 X Ex) 수강신청, 게임 빌드오더 --> 수1 ->수2 다익스트라, 벨만-포드, 플로이드-워셜 다익스 트라, 벨만-포드는 S 라는 시작점이 있
[알고리즘] 유클리드 호제법
유클리드 호제법이란 두 수의 최대공약수를 구하는 알고리즘입니다. 보통 수리영역을 공부하셨을때, 소인수분해를 이용하여 공통된 소수들의 곱으로 표현하였지만, 컴퓨터에서는 해당 방법으로 구하는 것보다 좀 더 간결하게 유클리드 호제법으로 표현가능합니다. 핵심이론 MOD 연산이 최대 공약수를 구하는 핵심이라서, MOD 연산을 이해하고 있어야 합니다. 이해하기 어려우시다면, % 기호다. 라고 생각하셔도 무방합니다. 유클리드의 호제법은 3단계로 구현됩니다. 큰 수를 작으수로 나누는 MOD 연산 수행 결과값으로 MOD 연산 수행 나머지가 0이 되는 순간의 둘 중 작은 수를 최대 공약수로 선택 참고로,  x (세로칸개수 -7)이다. --> 이유 : 최소크기가 8x8일 때, 경우의 수가 1이기 때문에 각변에는 -7을 해줘야한다. 따라서, 앞서 말했듯이 체스판을 색칠하는 경우는 총 2가지였다. 따라서 2를 곱해주면 끝이다. --> 이것은 2를 곱해서 사용하거나 반복문을 2번 돌리면 해결되는 것이다. 코드 필자가 처음 접근한 방법은 dfs다. --> 이유? -->없다. 필자는 요즘 dfs에 빠졌기 때문에, 모든 문제를 일단 d
[백준] 1012 유기농 배추 자바
문제 출처 : https://www.acmicpc.net/problem/1012 접근방법 일단 필자는 입력 코드의 예제가 크지않다면, 이해를 위해 도식화 하는 편이다. 따라서, 해당 문제도 도식화 하게 되었습니다. 배추 위치의 x,y 를 입력 받을 경우를 도식화 해보자. 그럼 여기서 카운팅을 하면 되는 것이다. 참고로 이 도식화는 이런 식으로 하라는 예시에 불과합니다. 위 도식화에서, 인접배열(리스트)에서 인접한 경우가 1인 경우에 카운트 1을 하라는 것이 아닙니다. {(0,1),(1,1),(1,0)} 중에서 아무 군데나 흰지렁이를 푼다면, 다 안전한 것입니다. 또한, {(4,2)(4,3)} 둘 중 하나, (2,4)(3,4) 둘 중 하나, (4,5)에 1개, {(7,4)~(9,5)}중 아무거나 한 군데
[백준] 1015 수열 정렬 자바
문제 링크 : https://www.acmicpc.net/problem/1015 코드 코드 설명 사실상 해당 문제 같은경우 정렬의 기본적인 문제라고 볼 수 있으며, 코드에 주석처리가 되어있어, 이해하기 쉬울 것입니다. 그래도 필자는 간단하게나마 코드에 대해 설명해드리겠습니다. 해당 코드의 전체적인 로직은 주어진 배열을 특정 기준(값과 인덱스)에 따라 정렬하는 알고리즘을 구현한 것이라고 보시면 됩니다. 즉, 값을 기준으로 오름차순 정렬하고, 동일한 값이 있을 경우 인덱스 순서대로 정렬합니다.
[백준] 1011 Fly me to the Alpha Centauri 자바
링크 : https://www.acmicpc.net/problem/1011 코드 코드설명 T 횟수만큼 반복하여 각 테스트 케이스를 처리하며, 입력을 공백으로 구분하여 x와 y 값을 추출합니다. distance 변수를 사용하여 x와 y 사이의 거리를 계산합니다. max 변수를 사용하여 거리의 제곱근을 구합니다. 이 무게 중심 이동 값을 일종의 최대 무게중심 이동 값으로 생각할 수 있습니다. 마지막으로 프로그램이 이동 횟수를 계산하여 출력합니다. 이때 세 가지 경우로 나누어 계산합니다. >- max 값이 거리의 제곱근과 동일한 경우: 이동 횟수는 2 * max - 1입니다. >- 거리가 max * (max + 1)보다 작거나 같은 경우: 이동 횟수는 2 * max입니다. >- 그렇지 않은 경우(거리가 max * (max + 1)보다 큰 경우): 이동 횟수는 2 * max + 1입니다. 결국, 수추리 & 계차수열의 문제인 것 같습니다. 참고로,
[백준] 1003 피보나치 함수
링크 : https://www.acmicpc.net/problem/1003 코드 일반dp 느낌의 풀이 해당 코드에 대한 로직의 전체적인 설명 2차원 정수 배열 dp를 선언하고, 크기는 41x2이며, dpi에는 i 번째 피보나치 수열에서 0이 호출된 횟수,dpi에는 1이 호출된 횟수를 저장. 사용자 입력을 받아 테스트 케이스 수 T를 설정 dp 배열의 초기값을 설정 이때, 피보나치 수열의 첫 번째와 두 번째 숫자는 각각 0과 1이므로, 호출 횟수도 각각 1회와 1회로 설정합니다. > dp0= 1; dp0= 0; dp1= 0; dp1= 1; 각 테스트 케이스에 대해 사용자로부터 입력받은 정수 N에 대하여 피보나치 함수를 호출하고, 결과를 출력할 문자열에 피보나치 함수에서 구한 0과 1의 호출 횟수를 추가합니다. --> while 안에서 fibonacci 메서드를 정의해야합니다.
[백준] 2606 바이러스 자바
링크 : https://www.acmicpc.net/problem/2606 코드 코드 설명 & 접근 방법 컴퓨터의 개수(n)는 7이고, 네트워크 상 연결 쌍(m)의 개수는 6입니다. 1부터 7까지의 인덱스로 이루어진 인접 리스트(adjacentList)를 초기화합니다. 다음은 입력된 연결 쌍에 따라 인접 리스트를 채웁니다. dfs(1) 함수를 호출하여 1번 컴퓨터부터 깊이 우선 탐색을 시작합니다. visited 배열은 각 노드의 방문 여부를 저장하는데 사용되며, count 변수는 1번 컴퓨터와 감염된 컴퓨터의 개수를 저장합니다. dfs(1) 함수를 호출한 뒤, 방문하지 않은 인접 노드인 2번 컴퓨터를 찾습니다. count를 1 증가시키고, 2번 컴퓨터를 방문한 것으로 표시합니다. 이어서 다시 dfs를 이용해 2번 컴퓨터와 연결된 미방문 노드를 찾습니다. 2번 컴퓨터와 연결된 미방문 노드는 3번 컴퓨터입니다. count를 1 증가시키고,
[알고리즘] greedy 그리디
탐욕적인 알고리즘, 그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘입니다. 그리디 알고리즘은 동적 계획법 dp 보다 구현하기 쉽고, 시간복잡도가 우수합니다. But, 항상 최적의 해를 보장하지 못한다는 단점도 존재합니다. 따라서, 코딩테스트 에서 그리디 알고리즘을 사용하기 전에는 항상 그리디 알고리즘을 적용할 때의 논리 유무를 확실하게, 충분히 살펴보고 사용하여야 합니다. 그리디 알고리즘 최적해를 구하기 위해 사용되는 근시안적 방법으로, 각 단계마다 가장 최선의 선택을 하는 알고리즘이다. 즉, 각 단계에서는 지금 상황에서 가장 최선의 선택을 하여, 전체적으로도 최적해에 근사한 해를 도출한다. 예를 들어, 동전 거스름돈 문제를 해결하고자 한다면, 시간 복잡도가 작은
[알고리즘] 시간복잡도
알고리즘 시간복잡도에 대해 많이 모르시고, 문제를 푸시는 것을 알게되어 이 기회에 되짚고 가면 좋겠다는 취지로 제대로 정리해보았습니다. 허접한 글이지만 미약하게나마 도움이 되면 좋겠습니다. 시간복잡도란 ? 코드의 실행시간이 어떤 요인으로 결정되는지 나타내는 시간과 입력 데이터의 함수 관계입니다. 코테에서는 자신이 짠 코드의 시간복잡도를 계산하여 문제에서 요구하는 입력을 제한 시간 내에 해결할 수 있는지 파악해야 합니다. 빅오표기법 알고리즘이 겪을 수 있는 최악의 경우에 걸리는 시간과 입력 간의 상관관계를 표기합니다. 입력크기가 N, 이에 비례하는 시간이 걸린다면 O(N)으로 표기합니다. 시간 복잡도 그래프 이진탐색 : O(logN) 선형탐색 : O(N) 정렬
[알고리즘] Binary Search 이진 탐색
23.07.13 스터디 정리 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 것입니다. Binary Search 이진탐색 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 것입니다. 다시말해, 이진 탐색은 이분법이라는 접근 방식을 사용하여 값을 찾으며, 시간 복잡도는 O(log N)입니다. 이진 탐색의 원리와 시간 복잡도를 이해하면 정렬된에서 원하는 값을 빠르게 찾는 데 도움이 됩니다. 이진 탐색의 수행 절
[알고리즘] BFS 너비 우선 탐색
23.07.13 너비 우선 탐색 알고리즘에 대해 study하였습니다. BFS(Breadth-First Search, 너비 우선 탐색)는 그래프에서 모든 정점을 방문하는 방법 중 하나로, 시작 정점에서부터 인접한 정점들을 모두 방문한 후에 방문한 정점을 기준으로 다시 인접한 정점들을 차례로 방문하는 순환이 진행되는 방식입니다. 이 방식을 통해 그래프의 모든 정점을 누락없이 한 번씩 방문할 수 있습니다. BFS, 너비우선 탐색 BFS(Breadth-First Search, 너비 우선 탐색)는 그래프에서 모든 정점을 방문하는 방법 중 하나로, 시작 정점에서부터 인접한 정점들을 모두 방문한 후에 방문한 정점을 기준으로 다시 인접한 정점들을 차례로 방문하는 순환이 진행되는 방식입니다. 이 방식을 통
[알고리즘] DFS 깊이 우선 탐색
23.07.13 스터디, 깊이 우선 탐색 알고리즘 학습 DFS (deepth-first-search) 깊이 우선 탐색 트리나 그래프에서 사용되는 탐색 알고리즘입니다. 이 방법은 시작 정점에서 시작하여 각 분기점에 대해 최대한 깊이 들어가면서 탐색하고, 더 이상 진행할 수 없게 되면 이전 분기점으로 돌아와서 다른 경로를 탐색하는 방식으로 진행됩니다. 주로 스택 또는 재귀를 이용하여 구현됩니다. DFS는 많은 문제 해결에서 사용되며, 그래프가 사이클을 포함하지 않는 경우 적합합니다. 그래프가 넓고 노드 수가 많을 경우, DFS는 탐색 과정에서 불필요한 방향으로 깊이 들어가기 때문에 시간이 오래 걸릴 수 있습니다. 이런 경우에는 BFS(Breadth-First Search, 너비 우선
[알고리즘] 기수 정렬
23.07.13 스터디 대수 정렬이라고도 부르며, 정렬할 데이터의 자릿수를 활용해 숫자나 문자열을 정렬하는 비교 기반 정렬 알고리즘이 아닌 정렬 방법입니다. 기수 정렬은 가장 낮은 자릿수부터 정렬을 진행하거나 가장 높은 자릿수부터 정렬하는 두 가지 방식이 있습니다. 이 두 방식은 각각 최하위 자릿수 우선(Least Significant Digit) 기수 정렬과 최상위 자릿수 우선(Most Significant Digit) 기수 정렬이라고 불립니다. 기수 정렬은 다음 과정을 통해 진행됩니다. 가장 낮은 자릿수부터 시작하여 각 값을 동일한 자릿수 그룹으로 분리합니다. 그룹을 차례대로 합쳐서, 다음 자릿수를 다시 그룹으로 분리합니다. 이 과정을 정렬할 데이터의 가장 높은 자릿수까지 반복합니다.
[알고리즘] 삽입 ,퀵, 병합 정렬
23.07.03 알고리즘 스터디 삽입 정렬 Insertion Sort 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식입니다. 즉, 대상이 되는 i 번쨰 수에 대해, 이미 정렬되어 있는 왼편의 어디에 삽입하면 되는지를 찾아서 집어넣고, i를 ++증가 하면서 오른쪽 끝까지 정렬해 나가는 것입니다. 평균 시간복잡도는 O(n^2) 핵심 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입 정렬의 핵심입니다. code 순서 및
[백준] 11861 Maximal Area
문제 https://www.acmicpc.net/problem/11861 부가설명 코드 및 부가 설명은 제가 따로 주석처리로 설명을 해놓았습니다. 코드 참고하시면서 보시면 조금 더 편리하게 이해하실 수 있으실 것입니다. 코드
[백준] 12846 무서운 아르바이트
문제 https://www.acmicpc.net/problem/12846 문제 설명 및 코드 설명은 생략하겠습니다. 왜냐하면, 가독성이 좋게 코드에 주석처리로 설명을 추가하였습니다. 코드
[백준] 1725 히스토그램
문제 https://www.acmicpc.net/problem/1725 TMI 필자는 지금 스택이라는 알고리즘에 빠져있다. 재밌다. 그냥 재밌다. 막 구현만 하던 나에게 알고리즘이라는 스킬이 더해져 알고리즘푸는 것이 이젠 해당 자료구조 및 알고리즘을 학습하고, 바로 백준의 고난이도 문제까지도 고민 좀 하다보면 풀린다는 것이 재밌습니다. 즉, 어느정도 막구현을 공부했다면, 알고리즘을 배우자. 접근방법 자바의 Stack 클래스를 활용해서 풀었습니다. code 코드 설명 히스토그램의 각 바를 loop--> 현재 바의 높이를 확인하고 스택을 이용하려합니다. 스택이 비어있지 않고 스택의 맨 위에 있는 바{ (stack.peek()) --> top라고 인지하면 될 것 같습니다.} 의 높이가 현재 바의 높이보다 클 때까지 스택에서 바를 꺼냄(stack.pop()). 이를 통해 현재 바를 기준으로 왼쪽에 있