Time Complexity 시간 복잡도 시간복잡도란? 시간복잡도는 문제 해결을 위한 알고리즘의 로직을 코드로 구현할 때 '입력값의 변화에 따라 연산이 실행될 경우, 연산 횟수에 비례해 시간이 얼마만큼 소요되는가'를 나타내는 것이며 Big-O 표기법을 사용해 나타낸다 2가지 코드가 있다. int n, sum = 0; scanf("%d", &n); for(int i=1;i

정렬 알고리즘 데이터를 일정한 순서로 나열하는 알고리즘 내부 정렬과 외부 정렬 30장의 카드를 한 줄로 늘어놓을 수 있는 책상에서 트럼프 카드를 정렬한다고 가정해보자 만약 카드가 30장 이하라면 모든 카드를 책상에 늘어놓고 한 번에 훑어보면서 작업할 수 있지만, 카드가 500장이라면 책상에 모든 카드를 늘어놓을 수 없기 때문에 큰 책상을 따로 마련해야 합니다. 정렬 알고리즘도 하나의 배열에서 작업할 수 있을 때에는 내부 정렬을 사용하고 하나의 배열에서 작업할 수 없을 땐 외부 정렬을 사용 한다 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 사용하는 알고리즘 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘 외부 정렬은 내부 정렬을 응..

8퀸 문제란? 서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓는 경우의 수를 찾는 문제 체스판에서 퀸은 현재 놓여있는 지점에서 가로*세로*대각선 8가지의 방향으로 직선 이동을 할 수 있다. 언뜻 보면 매우 쉬워보인다. 체스판의 가로줄을 행, 세로줄을 열이라고 하고 배열 인덱스에 맞추어 행과 열에 0~7 번호를 부여 한다. 퀸 배치하기 STEP1 8개의 퀸을 배치하는 조합은 8x8 총 64칸의 칸이 있다. 첫번째 퀸을 아무곳이나 배치하고 두번째 퀸을 배치할 땐 63 ..이러한 형식으로 64x63x62x61x60x59x58x57 = 178,462,987,637,760 가지이다. 그러나 이 조합을 모두 나열하기엔 현실상 불가능 하고 퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있다. STE..

재귀란? 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적이라고 함 재귀에 관한 기본적인 내용은 https://dusen0528.tistory.com/31?category=991091 를 참고하도록 하자 가장 기초적인 재귀 팩토리얼에 대해 알아보자 5!의 경우 5*4*3*2*1 = 120이다. 재귀의 핵심 포인트는 종료조건과 재귀조건이다. 위의 식을 보면 알 수 있듯이 n*(n-1)*(n-2)..등의 패턴이 반복되는 것을 알 수 있다. 이를 코드로 옮기면 import java.util.Scanner; public class Factorial { static int factorial(int n){ if(n>0) return n*factorial(n-1); e..

Stack 후입선출 Last In Frist Out 순서를 가진 자료구조 자세한 내용은 https://dusen0528.tistory.com/43 이 게시글을 참고하자 public class Stack1{ private int[] stk; //스택용 배열 정수 private int capacity; //스택 용량 private int ptr; //스택 포인터 public class EmptyIntStackException extends RuntimeException{ //실행 시 예외 : 스택이 비어있음 public EmptyIntStackException(){ } } public class OverflowIntStackException extends RuntimeException{ public Over..