분류 전체보기

부분집합(Subset)이란?부분집합은 주어진 집합의 원소들 중 일부를 선택하여 형성된 집합을 말한다. 주어진 집합 S의 모든 가능한 부분집합을 구하는 것이 부분집합 문제이다. 예를 들어, 집합 S = {A, B, C}의 부분집합은 0(공집합), {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C}와 같다.쉽게 말해 순서가 바뀌어도 연산(혹은 값)이 동일하고 선택해야 하는 개수가 따로 고정되어 있지 않은 모든 경우라면 부분집합을 고려해 볼 수 있겠다.  시간 복잡도부분집합을 생성하는 시간 복잡도는 O(2^N)이다. 이는 각 원소에 대해 두 가지 선택(포함 또는 미포함)이 가능하므로, 모든 가능한 부분집합을 생성하기 위해 2^N개의 경우를 탐색해야 함을 의미한다. 이로 인해..

순열이란?순열(Permutation)은 집합에서 일부 원소를 선택하여 순서를 고려해 나열하는 방법을 말한다. 선택된 원소들의 순서가 다르면 다른 순열이 된다. 예를 들어, 주어진 집합 {A, B, C}에서 2개를 선택하여 나열할 수 있는 순열은 AB, AC, BA, BC, CA, CB 등이 있다.쉽게 말해 순서가 바뀌면 연산(혹은 값)이 달라지고 선택해야 하는 개수가 고정되어 있으면(위의 예시로 들자면 개수는 2로 고정되어 있다.) 순열을 고려해 볼 수 있겠다. 사용 사례문제 해결 : 원소들을 모든 가능한 방법을 나열해야 할 때 사용된다. 예를 들어, 순열을 이용하면 문제의 가능한 모든 경우의 수를 탐색하거나, 정렬된 순서대로 원소들을 나열하는 경우에 활용된다.암호 해독 : 암호 해독 문제에서 가능한 모..

3학년 2학기부터 4학년 1학기까지 졸업작품 프로젝트를 개발하였다. 기업과 연계하여 기업의 요구사항을 바탕으로 의료자문분석시스템을 구현하였다.  의료자문분석시스템이란?의료 분야에서 불편을 겪었던 사용자에게 전문의와 직접 연결해 주고 이를 통해 자문•분석•번역 의뢰를 제공해주어 보험금 미지급과 같은 악용 사례를 방지해 줄 수 있는 서비스다.  프론트엔드는 배운 적이 없었지만 팀원 모두가 백엔드를 공부하는 친구들이라 울며 겨자 먹기로 프론트도 같이 진행하였다. 처음에는 너무 힘들었지만 계속하다 보니 오히려 백엔드와 프론트의 통신하는 과정에 있어서 이해를 더욱 잘할 수 있게 되었다.  프로젝트를 진행하며 우리는 몇차례 기업에 방문하여 중간보고를 대표님께 드렸다. 대표님의 조언에서 많은 것을 배울 수 있었다. ..

Arrays.sort()와 Collections.sort()알고리즘 정렬 문제를 풀던 중 Arrays.sort()와 Collections.sort()의 시간복잡도에 차이가 있다는 점을 깨닫게 되었다. 같은 sort() 메서드지만 내부에서는 다른 정렬법을 사용한다. 정렬 방식시간 복잡도Arrays.sort()Dual-Pivot QuickSort평균 : O(n log n) / 최악 : O(n^2)Collections.sort()TimSort (삽입정렬과 합볍정렬을 결합한 정렬)평균, 최악 : O(n log n) Arrays.sort()의 경우 Dual-Pivot QuickSort 알고리즘을 사용한다. 평균 시간복잡도가 O(n log n)이고 매우 빠른 알고리즘인 것은 맞다. 하지만 최악의 경우 시간복잡도는 ..

카운팅 정렬(Counting Sort)이란?정수나 정수로 표현할 수 있는 자료에 대해 유효한 알고리즘으로, 시간 복잡도가 O(n + k)인 정렬 알고리즘이다. 여기서 n은 배열의 크기이고 k는 배열의 요소 중 최댓값이다. 카운팅 정렬은 주로 범위가 제한된 작은 정수들로 구성된 배열을 정렬하는 데 적합하다. 정렬 과정가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트를 생성데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가증가된 리스트에서 0인 값을 제외하고, 인덱스를 인덱스 값만큼 출력  카운팅 정렬을 사용하면 안되는 상황카운팅 정렬은 수많은 정렬 알고리즘 중 시간복잡도가 O(n)으로 좋은 성능을 보여주는 알고리즘이다.다만, 카운팅 정렬의 단점은 count..

투 포인터 알고리즘 (Two Pointer Algorithm)배열이나 리스트에서 '두 개의 포인터'를 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘이다. 일반적으로 배열이나 리스트가 '정렬되어 있을 때' 사용한다.투 포인터 알고리즘은 보통은 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킨다.또는 동일한 시점을 기점으로 왼쪽 포인터를 고정한 상태에서 오른쪽 포인터를 이동하고, 조건에 따라 왼쪽 포인터도 이동하며 탐색하는 방식을 가진다.해당 알고리즘은 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용될 수 있다. 투 포인터 수행 단계배열 또는 리스트의 시작 위치에 첫 번째 포인터와..

📖 문제 ☑️ 입출력 예제 알고리즘❓ 풀어내기❗️다른 풀이 코드들을 보면 나와는 다르게 푼 게 대부분이었다. 내가 작성한 코드는 그렇게 깔끔한 코드는 아니지만 정말 단순하게 풀 수 있다. 풀이는 다음과 같다.모든 크로아티아 알파벳을 각각의 새로운 변수에 대입해 준다. 그런 다음 입력받은 문자열을 이전에 크로아티아 알파벳으로 대입해 준 변수들로 하나씩 replace() 메서드를 사용하여 "a"로 대체해 준다. 이렇게 하고 나면 문자열은 a로만 이루어져 있을 것이고, 이 문자열의 길이가 답이 된다. 🧑🏻‍💻 풀이 코드import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner ..

📖 문제 ☑️ 입출력 예제 알고리즘❓ 풀어내기❗️각각의 말에 정해진 개수로 초기화를 해주고 입력받은 수를 빼주면 된다. 🧑🏻‍💻 풀이 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int king = 1;        in..