Coding Ha

연결리스트

연결리스트(Linked List) - 데이터를 링크로 연결해서 관리하는 자료구조 - 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음 연결리스트의 장점 - 데이터 공간을 미리 할당할 필요 없음 - 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이 연결리스트의 단점 - 연결구조를 위한 별도 데이터 공간 필요 - 연결 정보를 찾는 시간이 필요(접근 속도가 상대적으로 느림) - 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요 연결리스트 기본 구조 노드(Node) - 데이터 저장 단위로, 값과 포인터로 구성 * 포인터(Pointer): 다음 노드나 이전 노드의 연결 정보 ▶ 데이터 추가 - 데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요 ▶ 데이터 삭제..

배열

배열(Array) - 많은 수의 데이터를 다룰 때 사용하는 자료 구조 - 각 데이터를 인덱스와 1:1 대응하도록 구성 - 데이터가 메모리 상에 연속적으로 저장됨 배열의 장점 - 인덱스를 이용하여 데이터에 빠르게 접근 가능 배열의 단점 - 데이터의 추가/삭제가 번거로운 편 : 미리 최대 길이를 정해서 생성해야 함 : 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성 : 데이터 삭제 시, 인덱스를 유지하기 위해 빈 공간 유지 실습 코드 // 선형 자료구조 - 배열 import java.util.ArrayList; import java.util.Arrays; public class Main { public static void main(String[] args) { // 1차원 배열 Syste..

알고리즘 복잡도

복잡도(Complexity) - 알고리즘 성능을 나타내는 척도 ▶ 시간 복잡도(Time Complexity) : 알고리즘의 필요 연산 횟수 - 어떤 문제를 해결하기 위한 알고리즘의 필요 연산 횟수 - 빅오(Big-O) 표기법을 통해 나타냄 ▶ 공간 복잡도(Space Complexity) : 알고리즘의 필요 메모리 - 어떤 문제를 해결하기 위한 알고리즘의 필요 메모리 사용량 - 빅오 표기법을 통해 나타냄: 일반적으로 메모리 사용량 기준은 MB 단위 ▶ 시간 복잡도와 공간 복잡도는 Trade-off 관계 실습 코드 // 기초 수학 - 알고리즘 복잡도 public class Main { static int fibonacci(int n) { if (n < 3) { return 1; } return fibonac..

지수와 로그

제곱, 제곱근, 지수 제곱 - 같은 수를 두 번 곱함 - 거듭 제곱: 같은 수를 거듭하여 곱함 제곱근 (=root) - a를 제곱하여 b가 될 때 a를 b의 제곱근이라고 함 로그 - a가 b가 되기 위해 제곱해야 하는 수 실습 코드 // 기초 수학 - 지수와 로그 public class Main { public static void main(String[] args) { // 1. 제곱, 제곱근, 지수 System.out.println("== 제곱 =="); System.out.println(Math.pow(2, 3)); System.out.println(Math.pow(2, -3)); System.out.println(Math.pow(-2, -3)); System.out.println(Math.pow(..

점화식과 재귀함수

점화식(Recurrence) - 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식 ex) 피보나치 수열 재귀함수 - 어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식 재귀함수는 어떻게 보면 반복문이 된다. 자기 함수를 계속 호출하기 때문에. 반복문을 탈출하기 위한 종료 조건이 반드시 있어야 된다. 없으면 무한 루프에 빠짐 재귀함수는 점화식으로 나타낸 것을 굉장히 편리하게 풀어낼 수 있다. 실습 코드 // 기초 수학 - 점화식과 재귀함수 public class Main { static int recursion1(int n) { if (n == 1) { return 1; } return 3 * recursion1(n - 1); } static int recursion2(int n) { if (..

프론트엔드와 백엔드 차이점

프론트엔드 백엔드 개념 프론트엔드는 웹사이트에서 사용자들이 사용하는 화면과 같은 앞단을 말하고 그리고 이러한 사용자 화면을 개발하는 사람을 프론트엔드 개발자라고 한다. 백엔드는 눈에 보이지 않는 영역으로 API와 같은 뒷단의 영역을 말한다. 그리고 이러한 API를 개발하는 사람을 백엔드 개발자라고 한다. 넓은 의미로는 클라이언트 서버라고도 한다. 클라이언트는 인터넷상에서 요청하는 쪽을 말하고 서버는 이러한 요청에 대해 서비스를 제공하는 역할을 한다. 정리하면 프론트엔드는 요청하는 앞단의 영역이고 백엔드는 요청에 응답하는 뒷단의 영역이라고 할 수 있다. 장/단점 프론트엔드 개발의 장점은 본인이 하는 작업의 비쥬얼 피드백을 바로 얻을 수 있다는 것이다. 본인이 작업한 아름다운 웹사이트, 앱, 비디오게임 등을..

조합

조합(Combination) - 서로 다른 n개 중에서 r개를 선택하는 경우의 수(순서 X, 중복 X) ex) 서로 다른 4명 중 주번 2명 뽑는 방법 중복 조합 - 서로 다른 n개 중에서 r개를 선택하는 경우의 수(순서 X, 중복 O) ex) 후보 2명, 유권자 3명일 때 무기명 투표 방법 실습 코드 // 기초 수학 - 조합 public class Main { static int getCombination(int n, int r) { int pResult = 1; // 결과를 저장할 변수 for (int i = n; i >= n - r + 1; i--) { pResult *= i; } int rResult = 1; for (int i = 1; i = n - r + 1; i--) { pResult *= ..

(Stack)백준 25556 포스택

스택(Stack) 문제 https://www.acmicpc.net/problem/25556 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 포닉스는 길이가 N인 순열 A와 네 개의 비어있는 스택을 가지고 있다. · 길이가 N인 순열이란, 1 이상 N 이하의 서로 다른 정수 N개가 임의로 나열된 수열을 말한다. · 스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출(Last In First Out, LIFO)의 특성을 가지고 있다. 포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다. 순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 1, 2, 3,..

순열

팩토리얼(Factorial) - 1에서 n까지 모든 자연수의 곱(n!) 1! = 1 2! = 1x2 3! = 1x2x3 순열(Permutation) - 순서를 정해서 나열 - 서로 다른 n개 중에 r개를 선택하는 경우의 수(순서 O, 중복 X) ex) 5명을 3줄로 세우는 방법 ex) 서로 다른 4명 중 반장, 부반장 뽑는 방법 중복 순열 - 서로 다른 n개 중에 r개를 선택하는 경우의 수(순서 O, 중복 O) ex) 서로 다른 4개의 수 중 2개를 뽑는 방법(중복 허용) ex) 후보 2명, 유권자 3명일 때 기명 투표 방법 원 순열 - 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수 ex) 원 모양의 테이블에 3명을 앉히는 경우 실습 코드 // 기초 수학 - 순열 import java.util.s..

경우의 수

경우의 수 어떤 사건에서 일어날 수 있는 경우의 가짓 수 - 예시 1) 동전을 던지는 사건: 경우의 수 2 - 예시 2) 주사위를 던지는 사건: 경우의 수 6 → 사건 A가 일어날 경우의 수 : n(A) 합의 법칙 사건 A 또는 사건 B가 일어날 경우의 수 → 사건 A와 사건 B의 합의 법칙: n(A∪B) 합의 법칙은 공통된 규칙을 뺀다. 예시) 두 개의 주사위를 던졌을 때 합이 3 또는 4의 배수일 경우의 수 * 사건 A: 합이 3의 배수일 경우 3: (1, 2), (2, 1) 6: (1, 5), (2, 4), (3, 3), (4, 2), (5, 1) 9: (3, 6), (4, 5), (5, 4), (6, 3) 12: (6, 6) * 사건 B: 합이 4의 배수일 경우 4: (1, 3), (2, 2), ..