티스토리

공부

검색하기

블로그 홈

공부

codingstudy95.tistory.com/m

김검정 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

Kotlin 연습하기(13) - 분할 정복 알고리즘 분할 정복 알고리즘의 기본 개념분할 정복의 핵심 아이디어는 분할 정복 이름 그대로 '분할(Divide)', '정복(Conquer)', '결합(Combine)' 의 세 단계로 이루어져 있다.분할 : 큰 문제를 여러 개의 작은 문제로 나눈다.정복 : 나눈 작은 문제들을 각각 해결한다.결합 : 해결한 결과를 합쳐서 전체 문제의 답을 만든다.쉽게 설명하면 큰 케이크를 한 번에 먹으려 하면 힘들지만, 조각조각 나눠서 먹으면 쉬운것과 비슷하다. 분할 정복의 대표 알고리즘으로는 병합 정렬과 퀵 정렬이 있다. 1. 병합 정렬(Merge Sort)병합 정렬은 배열을 반으로 나누고, 각각을 정렬한 뒤, 두 정렬된 배열을 합쳐서 전체 배열을 정렬하는 방법이다. 멀쩡히 있는 배열을 왜 쪼갤까? 배열을 작게 나누면, 작은 .. 공감수 0 댓글수 0 2025. 4. 30.
Kotlin 연습하기(12) - 해시 테이블 데이터를 빠르게 검색하거나 저장하는 일은 개발에서 필수적이다. (항상 이걸 어떻게 하면 잘할까 고민한다..) 이러한 작업을 가장 효율적으로 수행하는 자료구조 중 하나가 바로 해시 테이블(Hash Table) 이다. 해시 테이블은 키-값(Key-Value) 쌍으로 데이터를 저장하며, 거의 상수 시간(평균 O(1))에 데이터에 접근할 수 있는 강력한 도구이다. 해시 테이블이란?해시 테이블은 위에서 언급한것과 같이 키(key)와 값(value)의 쌍으로 데이터를 저장하는 구조이다. 여기서 중요한 개념은 해시 함수(hash function)로, 입력된 키를 고정된 크기의 인덱스로 변환한다. 이 인덱스는 데이터를 저장할 배열의 위치를 결정한다. 예를 들어 "apple"이라는 키를 입력하면, 해시 함수는 "app.. 공감수 0 댓글수 0 2025. 4. 25.
Kotlin 연습하기(11) - 투 포인터와 슬라이딩 윈도우 알고리즘 투 포인터란 무엇일까?투 포인터 기법은 배열이나 리스트 등에서 두 개의 인덱스(포인터)를 사용하여 문제를 해결하는 알고리즘이다. 주로 정렬된 배열에서 조건에 맞는 쌍을 찾거나, 두 포인터를 이용해 특정 구간을 탐색할 때 유용하다. 슬라이딩 윈도우란 또 무엇일까?슬라이딩 윈도우는 연속된 구간(윈도우)을 다루는 기법으로, 한 번에 한 구간씩 보면서 원하는 조건(예: 합, 평균, 최대/최소값 등)을 만족하는 최적의 결과를 찾는 방법이다.이때 "윈도우"는 배열이나 문자열에서 연속된 부분을 의미하며, 이 윈도우를 한칸씩 옮겨가며 문제를 해결한다. 이해가 잘 안된다 실생활 비유? or 더 쉬운 비유로 한번 이해를 해보자. 투 포인터 비유 : 책의 양쪽 끝에서 찾기생각해보자 한 권의 책에서 특정 단어를 찾으려고.. 공감수 0 댓글수 2 2025. 4. 23.
프로그래머스 (기초) - 5명씩 https://school.programmers.co.kr/learn/courses/30/lessons/181886 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 프로그래머스 기초레벨의 5명씩 문제를 한번 풀어봤다. class Solution { fun solution(names: Array): Array { val result = mutableListOf() for (i in names.indices step 5) { result.add(names[i]) } return result.toTypedArray() }} 코드 .. 공감수 0 댓글수 0 2025. 4. 18.
Kotlin 연습하기(10) - 그리디 알고리즘 1. 그리디 알고리즘의 정의그리디 알고리즘은 문제를 해결할 때 현재 상황에서 가장 최선의 선택을 하여 최종 해답을 도출하는 방법이다. 이 때, 각 단계마다 선택하는 것이 최적해를 보장하는 경우에만 효과적이다. 2. 국부 최적 선택(Local Optimal Choice) 이란??국부 최적선택이란 각 단계에서 당장 가장 이득이 큰 선택을 하는 것을 의미한다. 예를 들어, 쇼핑할 때 할인율이 가장 높은 상품을 먼저 고르는 것과 비슷하다. 3. 그리디 알고리즘의 장단점장점 : 구현이 단순하고 빠르며, 계산 비용이 적다.문제의 크기가 커져도 각 단계의 선택만 고려하면 되므로 효율적이다.단점 : 매 순간 최선의 선택이 전체 최적해를 보장하지 않을 수 있다.문제에 따라 그리디 알고리즘이 최적해를 찾지 못하는 경우.. 공감수 1 댓글수 2 2025. 4. 14.
Kotiln 연습하기(9) - DFS / BFS 그래프(Graph)란 무엇일까?그래프는 정점(Vertex)와 간선(Edge)으로 구성된 자료구조이다. 정점(Vertex) : 그래프의 구성요소로, 사람이나 도시처럼 개별 요소를 나타낸다.간선(Edge) : 정점들을 연결하는 선이다. 두 정점 사이의 관계(예:도로, 친구 관계)를 나타낸다.예시 : 학교에서 여러 학생(정점)들이 친구 관계(관선)를 맺고 있는 것을 그래프로 생각할 수 있다. 그래프의 표현 방법그래프를 컴퓨터에서 표현하는 방법에는 여러 가지가 있다. 가장 일반적인 두 가지 방법은 인접 리스트와 인접 행렬이다.인접 리스트(Adjacency List) : 각 정점에 연결된 정접들의 리스트를 저장한다. 예시0: [1, 2]1: [0, 3]2: [0, 3]3: [1, 2] 인접 행렬(Adj.. 공감수 1 댓글수 1 2025. 4. 11.
Kotlin 연습하기(7) - 동적 계획(DP) 동적 계획법(Dynamic Programming, DP) - DPDP란 무엇일까? 동적 계획법은 큰 문제를 여러 개의 작은 문제로 나누어 해결한 후, 그 결과를 저장하여 전체 문제를 효율적으로 해결하는 방법이다. 예를 들어, 큰 퍼즐을 맞출 때, 각 조각을 따로 기억해둔다면 다시 같은 조각을 찾지 않아도 된다. DP의 핵심 개념부분 문제(Overlapping Subproblems) : 큰 문제를 해결하는 과정에서 동일한 작은 문제가 여러 번 반복되는 경우가 있다.최적 부분 구조(Optimal Substructure) : 문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있을 때, DP를 적용할 수 있다. 대표 문제 : 계단 오르기 - 문제 설명 : 계단이 총 n개 있고, 한 번에 1계단 또는 2계.. 공감수 0 댓글수 0 2025. 4. 7.
Kotlin 연습하기(6) - 선형/이진 검색 검색 알고리즘이란 무엇일까?검색(Searching)은 배열이나 리스트 같은 데이터 집합에서 특정 값(또는 조건에 맞는 요소)을 찾아내는 과정이다.예를 들어, 반에서 학생들 이름이 적힌 명단이 있을 때 "철수"라는 이름을 찾는 것과 비슷하다. 왜 검색이 필요할까?데이터 찾기 : 많은 데이터 중에서 필요한 정보를 빠르게 찾기 위해 사용된다.알고리즘 문제 : 코딩 테스트에서 특정 값을 찾는 문제가 출제된다.효율성 : 올바른 검색 알고리즘을 사용하면 데이터의 양이 많더라도 빠른 시간 안에 원하는 값을 찾을 수 있다. 1. 선형 검색(Linear Search)배열의 첫 번째 요소부터 순서대로 하나씩 검사하면서 찾고자 하는 값과 일치하는지 확인한다. 특징 간단하고 구현하기 쉽다데이터가 정렬되어 있지 않아도 사용할.. 공감수 0 댓글수 0 2025. 4. 4.
Kotlin 연습하기(5) - 버블정렬 정렬이란 무엇일까?정렬(sorting)은 데이터 (예: 숫자, 문자열 등)를 일정한 순서대로 나열하는 과정이다. 예를 들어, 시험 점수가 섞여 있을 때 낮은 점수부터 높은 점수 순서대로 정렬하면, 누구의 점수가 가장 낮고 누구의 점수가 가장 높은지 쉽게 알 수 있다. 왜 정렬이 필요할까?검색 : 정렬된 데이터를 빠르게 검색할 수 있다.분석 : 데이터를 정리해서 보고서나 그래프로 만들 때, 정렬된 상태가 더 유용하다.문제 해결 : 코딩 테스트나 알고리즘 문제에서 정렬은 자주 사용되는 기본 기술이다. 버블 정렬(Bubble Sort) 이해하기 버블 정렬의 원리 버블 정렬은 인접한 두 개의 원소를 비교하여 순서가 맞지 않으면 서로 교환한다.한 번의 반복(패스)마다 가장 큰 값이 맨 뒤로 이동하게 된다.이 과정.. 공감수 0 댓글수 0 2025. 4. 2.
Kotlin 연습하기(4)-재귀함수 재귀 함수란 무엇일까?재귀 함수란 자기 자신을 호출하는 함수이다. 즉, 문제를 해결하기 위해 동일한 문제의 더 작은 버전을 반복해서 호출하는 방식이다. 재귀 함수의 구성 요소기본 조건(Base Case) : 재귀 호출을 멈추는 조건이다. 기본 조건이 없으면 함후가 무한히 자기 자신을 호출하게되는 무한루프에 빠지게 된다.재귀 호출(Recursive Case) : 문제를 더 작은 문제로 나누어 자기 자신을 호출하는 부분이다. 재귀 함수 예제1. 팩토리얼 계산(n!)fun factorial(n: Int): Int { // 기본 조건: n이 0이면 1 반환 if (n == 0) { return 1 } // 재귀 호출: n * (n-1)! 계산 return n * fact.. 공감수 0 댓글수 0 2025. 3. 31.
Kotlin 연습하기(3) 문자열이란?문자열(String) 이란 여러 문자가 이어진 데이터이다. 예를 들어, "Hello, Kotlin!" 은 하나의 문자열이다. 문자열에서 인덱스 (Index)도 중요한데 인덱스란 문자열의 각 문자의 순서를 나타내며, 첫 번째 문자는 0번 인덱스이다.val text = "Hello"println(text[0]) // 출력: Hprintln(text[1]) // 출력: e Kotlin에서는 문자열을 다루기 위한 다양한 내장 함수를 제공한다.reversed() : 문자열을 뒤집는다.length : 문자열의 길이를 반환한다.contains() : 특정 문자가 포함되어 있는지 확인한다. 리턴값은 true / falsesplit() : 문자열을 특정 구분자로 나눈다.fun main() { val t.. 공감수 0 댓글수 0 2025. 3. 27.
Kotlin 연습하기(1) 변수와 자료형변수 : 정보를 저장하는 상자. 예를 들어, 숫자나 글자, 논리값(true/false)을 저장할 수 있다.자료형 : 변수에 어떤 종류의 값이 들어갈 수 있는지 결정한다. 예시) 정수형 : Int / 실수형 : Double / 문자열 : String / 논리형 : boolean 조건문조건문 (if문) : 주어진 조건이 참이면 특정 코드를 실행하고, 그렇지 않으면 다른 코드를 실행할 수 있다.val score = 85if (score >= 90) { println("합격")} else { println("불합격")}// score가 90 이상이면 "합격"을, 그렇지 않으면 "불합격"을 출력한다. 반복문반목문 (for, while) : 같은 작업을 여러 번 반복할 때 사용한다.for.. 공감수 0 댓글수 0 2025. 3. 21.
프로그래머스 - 3진법 뒤집기 (level 1) https://school.programmers.co.kr/learn/courses/30/lessons/68935 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 여기서의 핵심은 3진법으로 바꾼배열 nums 를 뒤집어야 3진순로 변환된 문자열이 된다는 것이다.def radixChange(num, radix): if num == 0: return '0' nums = [] while num: num, digit = divmod(num, radix) # num에는 몫이, digit에는 나머지가 담기게 된다 nums.append(str.. 공감수 0 댓글수 0 2024. 9. 9.
프로그래머스 - 짝지어 제거하기(level2) https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr def solution(s): stack = [] for case in s: if stack and stack[-1] == case: stack.pop() else: stack.append(sase) return 0 if stack else 1 공감수 0 댓글수 0 2024. 9. 4.
프로그래머스 - 이상한 문자 만들기(level 1) https://school.programmers.co.kr/learn/courses/30/lessons/12930 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 홀수와 짝수를 구별하는 문제이다. 가장 쉬운 방법은 변수를 하나 더 만들어 짝수인지 홀수인지 구별하는 것이다. def solution(s): s = list(s) cnt = 0 # 짝수/홀수 구분 인덱스 변수를 기준으로 2로 나누어 떨어질 때(짝수), 나누어 떨어지지 않으면(홀수) 라고 정의할 수 있다. 다만 공백을 만나면 새 단어를 준비한다는 의미이므로 짝수/홀수 구분 변수의 값을 초.. 공감수 0 댓글수 0 2024. 8. 27.
프로그래머스 - 시저 암호 https://school.programmers.co.kr/learn/courses/30/lessons/12926 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 여기서 생각해봐야 할 문제는 주어진 숫자만큼 더하다 보면 숫자가 알파벳의 범위를 벗어날 수 있다는 것이다. 만약 결과가 알파벳의 범위를 벗어나면 해당 알파벳의 처음인 a 또는 A로 돌아가야 한다.(소문자z -> 소문자 a, 대문자 Z -> 대문자 A). def solution(s, n): s = list(s) for i in range(len(s)): if s[i] == ' ' : c.. 공감수 0 댓글수 0 2024. 8. 23.
문자열 문자열의 특징문자열(string)이란 문자(char) 또는 문자들로 구성된 집합을 의미한다. 파이썬에서는 기본적으로 "(큰따옴표)와 '(작은따옴표) 문법을 모두 지원한다. 문자열이란먼저 컴퓨터가 받아들이는 문자열과 사람이 보는 문자열은 차이가 꽤 크다. 모든 것을 숫자로 이해하는 컴퓨터가 문자를 인식하도록 하려면 '문자를 숫자로 변환하는 과정'을 추가로 거쳐야 하며, 이 과저에서 보통 문자 집합(character set)중 가장 대표적인 유니코드를 사용한다. 만약 변수에 문자열로 "Programmers is good"을 할당하면 컴퓨터는 사람이 선언한 문자열을 각 글자에 해당하는 숫자로 인식한다. 그리고 모든 글자에 대한 정보를 한곳에 담아야 하기 때문에 암묵적으로 배열로 선언한다. 기존의 배열처럼 [.. 공감수 0 댓글수 0 2024. 8. 22.
2차원 배열 1차원 배열 + 1차원 배열?다른 언어에서는 '배열은 한 변수에 데이터 여러 개를 선언할 수 있게 해주는 자료형'이라고 할 것이다. '배열은 연속적으로 데이터를 집어넣을 수 있는 1차원 형식의 자료 구조'라고 정의할 수 있다. 배열 안의 배열, 즉 2차원 배열은 어떨까? 2차원 배열은 다음 모습과 같다. data = [[1,2,3],[4,5,6]] 1차원 배열을 선언하면 다음과 같이 한 방향으로 연속적인 데이터가 나열된다. 조회하려는 항목의 순서인 N에서 1을 뺀 숫자가 바로 원하는 데이터를 조회할 수 있는 인덱스이다. 여기에 배열을 하나 더 얹어 2차원으로 선언할 경우 다음과 같이 사각형이 된다. 이 배열에서 원하는 값을 찾으려면 1차원 배열과 다르게 '세로 위치 -> 가로 위치' 순으로 조회해야 한다.. 공감수 0 댓글수 0 2024. 8. 19.
시간 복잡도 문제 해결에 필요한 입력값과 문제를 해결하는 프로그램이 주어졌을 때, 프로그램이 입력값을 받아 동작하고 결과를 만들어내는 데 걸리는 정도를 복잡도라고 한다. 그 중 얼마나 오래 걸리는지는 시간 복잡도라고 하고, 얼마나 많은 메모리를 사용하는지는 공간 복잡도라고 한다. 빅오(Big-O) 표기법실제로 코드를 실행해보면 소프트웨어나 하드웨어적 변수가 많아 똑같은 코드라도 환경에 따라 실행 시간이 조금씩 다르다. 이런 차이 때문에 시간을 정확한 수치로 표현하기는 어렵지만, 문법이나 구성에서 발생하는 비용을 수치화해 문제를 푸는 데 필요한 총 연산의 수를 수학적으로 표기할 수 있다. 이를 점근 표기법이라고 하며, 세 가지 표기법 중 가장 흔하게 사용하며, 최악의 경우를 계산하는 계산법을 빅오(Big-O) 표기법.. 공감수 0 댓글수 0 2024. 8. 16.
순환 (Recursion) 모든 순환함수는 반복문(iteration)으로 변경 가능하다.그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능하다.순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.하지만 함수 호출에 따른 오버헤드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등)적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.모든 case는 결국 base case로 수렴해야 한다. 연습 미로찾기 입구는 (0,0)이고 출구는 (n-1, n-1)일때 입구에서 출구까지 도착하는 경우의 수를 찾아보자 현재 위치에서 출구까지 가는 경로가 있으려면현재 위치가 출구이거나 혹은이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경우가 있거나둘 중 하나이다... 공감수 1 댓글수 2 2024. 7. 16.
시간복잡도 시간 복잡도(time complex) 시간 복잡도란 어느 코드를 실행했을 때 실행 시간이 어느정도일지 표현해 보는 것이다. 여기서 실행시간이랑 함수/알고리즘 수행에 필요한 스텝(step) 수 이다. int[] multiply(int[] inputs, int multiplier) { int[] nums = new int[inputs.length]; for(int i = 0; i < inputs.length; i++) } nums[i] = inputs[i] * multiplier; } return nums; } 위와 같은 코드가 있을 때 각각 라인이 실행되는 스텝은 상수로 표시된다. 따라서 각 라인의 스텝수와 실행시간은 아래와 같이 정리할 수 있다. cost times c1 1 c2 N+1 (for 문을 돌.. 공감수 0 댓글수 0 2023. 9. 19.
Array에서 Index는 왜 0부터 시작할까? Array는 두 가지 요소로 표현할 수 있다. Array의 시작 주소 각 item의 Size(byte) c언어에서 int 배열을 하나 만들었다고 해보자 int nums[5] = {1,2,3,4,5} 배열의 시작을 가리키는 시작주소가 1000 이라고 했을 때 다음 item 의 시작 주소는 1000 + 4 로 설정되고, 다음은 1000 + 4 + 4 계속 이런 식으로 반복하게 된다. 여기서 4는 item int 의 크기 4byte를 뜻한다. 1000 + 4 === 1000 + 4 x 0 과 같다. 그렇기 때문에 쉽게 계산하기 위해서 0부터 시작하는 것이다. 여기서 Array의 장점을 알 수 있다. Array의 size가 아무리 커도 똑같은 속도로 각 위치의 item 을 가져올 수 있다는 것이다. 공감수 0 댓글수 1 2023. 9. 15.
List 와 Set List 같은 종류의 아이템을 저장 순서를 보장 중복을 허용 Set 같은 종류의 아이템을 저장 순서를 보장하지 않음 중복을 허용하지 않음 만약 월드컵에서 한번이라도 골을 넣은 순서를 저장한다고 하면 무엇을 사용해야 할까? 중복을 허용하면 안되고, 순서가 필요없기 때문에 set을 사용하면 될 것이다. 공감수 0 댓글수 0 2023. 9. 12.
Array List 와 Linked List 우선 List는 무엇인가? List란 어떤 순서가 있는 데이터의 집합이다. 그렇다면 List의 종류는 어떤것이 있을까? Array List Linked List 두 종류가 있다. 1. Array List 위 그림과 같이 Array List 는 연속적인 공간에 순차적으로 데이터를 저장한다. Array List 의 장점은 Indexing이 가능 하다는 것이다. 단점은 추가/ 삭제가 어렵다는 것이다. 사이즈가 고정되어 있다. 2. Linked List 위 그림과 같이 Linked List 는 비연속적인 공간에 순서대로 데이터를 저장한다. Linked List 의 장점은 추가/ 삭제가 쉽다는 것이다. 단점은 위치 탐색을 할때 오래 걸린다는 것이다. 같은 데이터가 들어있으면 Linked List 의 메모리가 좀 .. 공감수 0 댓글수 0 2023. 9. 8.
Array 와 List 의 차이 Array 와 List 의 차이는 무엇일까? 우선 Array란 연속적인 메모리에서 같은 종류의 아이템들을 저장할 수 있는 자료구조다. [ ] 를 사용하여 인덱스를 활용할 수 있다. 인덱스를 사용하면 사이즈가 얼마나 크던지 원하는 자료에 접근할때 걸리는 시간이 동일하다. List 는 무엇일까? 순서를 가지며 추가, 삭제, 탐색이 가능한 ADT(Abstract Data Type) 이다. Array에 비해서 추상적이다 내부적으로 어떻게 동작하는지 알려주지 않는다. * ADT는 구조의 속성과 행위를 설명한다. 따라서 add remove get contains 같은 operation을 사용 가능하다. List는 어떻게 구현할 수 있을까? Array (= ArrayList) Linked node (= LinkedL.. 공감수 0 댓글수 0 2023. 9. 8.
Queue(큐) 큐는 Last In Last Out : LILO First In First Out : FIFO 구조를 가지고 있다. 큐는 순서를 보장한다. 그렇다면 어떤 곳에 사용할 수 있을까? 은행 창구 번호표 처리, 메신저의 메신저 함, 티켓팅 시스템 등등 순서 보장이 필요한 곳에서 사용할 수 있을것 같다. 공감수 0 댓글수 0 2023. 9. 8.
Stack 스택은 Last In First Out : LIFO First In Last Out : FILO 특징을 가지고 있다. 가장 먼저 들어간 것이 마지막에 나오고 가장 나중에 들어간 것이 제일 처음에 나온다. 예들 들어 Ctrl + Z 같은 것들을 구현할 수 있을 것이다. Stack 에 집어 넣는 동작을 Push, 빼는 동작을 Pop 이라고 한다. 공감수 0 댓글수 0 2023. 9. 8.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.