전체 글
시간 복잡도 / 공간 복잡도
1. 시간 복잡도, 공간 복잡도란? 좋은 알고리즘이란 무엇일까? 얻고자 하는 결과를 짧은 시간과 적은 메모리 공간을 이용하여 구해내는 알고리즘을 좋은 알고리즘이라 할 수 있다. 이 때 알고리즘 수행에 드는 시간 효율과 공간 효율을 알아내는 방법이 필요한데, 그것이 시간 복잡도와 공간 복잡도이다. 2. 시간 복잡도 알고리즘의 시간 복잡도를 계산할 때는 알고리즘의 연산의 횟수를 계산하여 정한다. 알고리즘은 경우에 따라 연산 횟수가 최선의 경우, 평균적인 경우, 최악의 경우로 달라질 수 있다. 대체로 최악의 경우를 산정하고 시간 복잡도를 파악한다. 그렇다면 이 때 연산이라고 할 수 있는 것에 무엇이 있을지 알아보자. 대입 연산 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈) 비교 연산 함수의 호출 public int..
BOJ 11576 Base Conversion [Java]
BOJ 11576 Base Conversion 1. 문제 링크 https://www.acmicpc.net/problem/11576 2. 문제 해설 a진법의 수를 b진법의 수로 바꿔줘야하는 문제이다. a진법의 수를 10진수로 바꿔주고 그 10진수를 b진법의 수로 바꿔주는 방식으로 해결했다. 아래 코드에서 sum은 a진법의 수를 뜻하는 10진수이고, 그 10진수를 b로 나누어주면서 나머지를 스택에 저장하였다. 입력된 수가 0일 경우에는 0을 바로 출력하게 설정하였다. 3. 코드 보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedR..
BOJ 2089 -2진수 [Java]
BOJ 2089 -2진수 1. 문제 링크 https://www.acmicpc.net/problem/2089 2. 문제 해설 -2진수도 2진수와 같이 결국 1과 0으로만 표현해야한다. 10진수를 2진수로 바꿔줄 때와 비슷하게 10진수를 -2로 나누어주며 과정이 진행된다. -2로 나누어주면 나머지가 0 혹은 -1이 나오는데 0의 경우는 2진수와 동일하게 처리가 가능하지만, -1의 경우는 다른 방식이 필요하다. 나머지가 -1인 경우를 어떻게 처리하는지 예시를 들어보겠다. 7을 -2로 나누는 경우를 생각해보자. 7 / (-2) = (-2) x (3) - 1 이다. 이것을 다르게 표현하면, 7 / (-2) = (-2) x (4) + 1 이다. 즉, 나머지가 -1인 경우에는 나머지를 1로 바꿔주고 몫을 1 더해주면..
![위상 정렬(Topological sorting) [Java]](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2Fu9yc4%2FbtrbuBvB6FN%2FAAAAAAAAAAAAAAAAAAAAALqZQLczopgcTOO2cBFuZrUXalT6jTa2SeMfp67YKSef%2Fimg.jpg%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1753973999%26allow_ip%3D%26allow_referer%3D%26signature%3Dmt6pTd8QdlMo5ofVTgFCRZCEIMA%253D)
위상 정렬(Topological sorting) [Java]
목차 1. 위상정렬이란? 2. 위상정렬의 과정 3. 위상정렬 구현 1. 위상정렬이란? 위상정렬은 사이클이 존재하지 않는 방향 그래프에서 정점들을 정렬하는 알고리즘이다. 대표적인 실생활의 예로 대학교의 선후수 교과과정이 있다. 위와 같은 상황에서 과목을 듣는 순서를 짜는 것이 위상정렬의 한 예이다. 만약 사이클이 있다면 선후 관계가 모호해지기 때문에 사이클은 올 수 없다. 2. 위상정렬의 과정 위 그래프를 한번 위상정렬해보자. 먼저 들어오는 간선이 없는 A가 제일 앞에 올 것이다. A에서 나가는 간선을 보면 B, C, D를 향해 있다. 이것의 의미는 B, C, D를 거치기 전에 반드시 A가 등장해야한다는 의미이다. 지금 상태에서는 A가 제일 앞에 등장했으니 A에서 나가는 간선은 의미가 없다. 그러므로 A와..
BOJ 1978 소수 찾기 [Java]
BOJ 1978 소수 찾기 1. 문제 링크 https://www.acmicpc.net/problem/1978 2. 문제 해설 소수인지 아닌지 판별해야하는 수가 1000이하이고 100개 이하로 주어진다. 주어진 조건의 범위가 작기에 1부터 1000까지 전부 다 나눠보는 방식으로 하여도 충분히 시간 제한을 만족한다. 입력 받은 수가 소수인지 판별하는 isPrime 메소드를 만들었다. cnt는 소수의 갯수를 의미한다. 주어진 n개의 수에 isPrime 메소드를 이용하여 소수인지 판별하고, 소수라면 cnt를 1 더해준다. 최종적으로 cnt를 출력한다. 3. 코드 보기 import java.io.*; import java.util.*; public class Main { static boolean isPrime(..