분류 전체보기

이번 글부터는 여러 알고리즘 패러다임을 다뤄보며 알고리즘 문제에서 어떤 식으로 이 패러다임을 사용하는지 알아보도록 하겠습니다.브루트포스 알고리즘에 대한 접근법이나 더 많은 문제를 원하시면 하단 포스팅을 보셔도 도움이 될 것 같습니다! 👍🏻 꼭 알아야하는 코딩 테스트 유형: 7) #Bruteforcing이번에는 코딩 테스트에서 중요한 유형인 'Brute Forcing(브루트포스)'에 대해 알아보겠습니다. 브루트포스는 가능한 모든 경우의 수를 탐색하여 정답을 찾는 방법입니다. 즉, 모든 가능성을 일일이injoycode.tistory.com 개요프로그래밍 대회에서 참가자들은 종종 복잡하고도 우아한 해결책을 찾으려 하지만, 실제로는 더 간단하고 명확한 방법이 존재할 때가 많습니다.이러한 상황에서 '완전 탐색..

이번 글에서는 알고리즘 증명에 자주 사용되는 기법들, 또 그 증명의 일반적인 패턴들을 다뤄볼까 합니다!수학적 귀납법과 반복문 불변식 수학적 귀납법은 반복적 구조를 가진 명제들을 증명하는 데 유용한 방법으로, 단계별로 문제를 나누어 각 단계에서의 성립을 증명합니다. 예를 들어, 도미노가 하나씩 쓰러지는 것처럼, 첫 단계가 성립하고, 한 단계가 성립하면 다음 단계도 성립한다는 것을 보임으로써 전체가 성립함을 증명합니다. 추가적으로 반복문 불변식 또한 알고리즘의 정당성을 증명하는 데 유용합니다. 알고리즘 내의 반복문이 올바른 결과를 내기 위해 각 단계에서 특정 조건이 계속해서 유지되어야 함을 의미합니다. 이를 증명하기 위해 반복문 시작 시, 반복문 내에서, 그리고 반복문 종료 시에 불변식이 성립함을 보여야 합..

저번 글에 이어서 시간 복잡도와 관련된 빅 오 표기법(big-O notation), 주먹구구 법칙, NP 문제 등을 다뤄보겠습니다. 시간 복잡도지난 글을 돌이켜보면 알고리즘을 평가할 때 중요한 지표 중 하나는 바로 '시간 복잡도'였습니다. 이 시간 복잡도는 알고리즘이 얼마나 효율적으로 실행되는지를 나타내는 척도로, 알고리즘이 수행하는 기본 연산의 총 횟수를 입력 크기에 따라 나타낸 것입니다. 기본 연산은 더 이상 쪼갤 수 없는 최소 단위의 연산으로, 예를 들어 정수의 사칙연산, 변수 간의 대입, 논리 연산 등이 이에 해당합니다. 이와 달리 배열 정렬, 문자열 비교, 소인수 분해 같은 연산들은 여러 기본 연산을 포함하므로 기본 연산으로 분류되지 않습니다. 시간 복잡도의 핵심은 알고리즘 내부의 '가장 깊이..

알고리즘 공부를 시작하면서 읽었던 ⟪ 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 ⟫ 시리즈에 대한 내용을 정리해보려고 합니다! 책에는 C++ 코드를 위주로 설명하고 있지만, 제가 현재 코딩 테스트나 대회에서 사용하는 파이썬 코드로 따로 정리하고 싶었습니다.먼저 시간 복잡도 분석에 대한 부분입니다. 개요알고리즘의 속도를 효과적으로 측정하는 것은 더 빠른 알고리즘을 개발하는 데 필수적입니다.가장 간단한 방법은 두 알고리즘을 구현하여 동일한 입력에 대한 실행 시간을 비교하는 것이지만, 알고리즘의 효율성을 평가하는 일반적인 기준으로는 부족할 수 있습니다.실행 시간은 다양한 외부 요인에 영향을 받기도 하고, 같은 알고리즘이라도 입력의 크기나 특성에 따라 수행 시간이 달라질 수 있습니다. 알고리즘의 수행 ..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr이번에는 알고리즘 문제에 자주 등장하는 '스택 / 큐' 자료 구조를 이용한 문제들을 풀어보겠습니다! 스택은 뭐고 큐는 뭐죠?우선 스택은 LIFO(Last-In, First-Out) 원칙을 따르는 선형 자료 구조입니다. 가장 마지막에 추가된 요소가 가장 먼저 빠져나온다는 것을 의미합니다.스택은 재귀나 괄호 매칭 등의 문제에서 주로 적용되는 자료 구조입니다.두 번째로 큐는 FIFO(First-In, First-Out) 원칙을 따르는 선형 구조입니다. 대기열을 관리하거나 BFS 문제에 주로 사용됩니다.큐는 앞과 뒤 모두..

학기 중(23.11.07 ~ 23.12.13) 진행된 Process Mining Project를 간단히 정리하고자 합니다. 1. Introduction1.1 Research Question일상 속 발생하는 처방 오류를 효과적으로 줄일 수 있는 방법이 있을까?처방 오류를 줄이기 위해서 환자들도 약품에 관한 지식이 필요하지 않을까?처방 오류의 특징을 어떻게 효과적으로 식별할 수 있을까?1.2 Describe Dataset데이터 출처 : https://physionet.org/content/mimiciv/2.2/#description데이터 구조 : 프로젝트에 사용된 주요 컬럼들은 다음과 같습니다. subject_id 환자의 고유 ID chiefcomplaint 입원 주요 원인 ..

solved.ac알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다.solved.ac이번 포스팅은 정렬 문제 위주로 다뤄보겠습니다. 1676번 : 팩토리얼 0의 개수 1676번: 팩토리얼 0의 개수N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.www.acmicpc.net특정 수의 팩토리얼을 계산했을 때 뒤에 0이 몇 개가 붙는지를 계산하는 문제입니다.처음에는 그저 팩토리얼을 일일이 계산해 문자열로 변환한 뒤, 뒤집어서 0의 개수를 세어보았습니다.그러나 이 방법은 N이 커질수록 시간적으로 비효율이고 성능이 안 좋아지기에 다른 방법을 고안해보았습니다. 아래와 같은 로직을 따라가 보..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr본 카테고리에서는 프로그래머스에서 제공되는 고득점 Kit 문제들을 다뤄볼까 합니다.프로그래머스 환경은 기업이나 자격증 관련해서도 코딩 테스트에 자주 사용되기 때문에 익혀두시면 적응하기 편하실 것 같습니다.실려있는 주제 순서대로 풀어갈 예정이며, 먼저 해시 관련 문제들을 살펴봅시다. 해시는 뭐죠?해시는 데이터 저장, 검색 및 관리를 위한 기술로 key-value 쌍을 사용하여 데이터를 효율적으로 저장합니다.해시는 해시 함수를 이용하여 key를 고유한 index(hash code)로 변환하고 이를 통해 데이터를 해시 ..