profile
공부하자!!

BOJ 1450 냅색문제(투 포인터 알고리즘)

브루트 포스 방식으로 접근할 경우 30개의 원소를 가진 배열의 부분집합을 모두 구해야 하므로 $2^{30}$의 경우의 수를 계산해야하므로 불가능하다. 따라서 수의 크기를 줄여야 한다. 두 개의 $2^{15}$짜리 문제로 바꾼 후 투 포인터 알고리즘($O(N)$)으로 두

2일 전
·
0개의 댓글
·

BOJ 11404 플로이드 (플로이드-워셜 알고리즘)

그래프 최소거리 문제 중 각 정점에서 다른 모든 정점으로의 최소거리를 구하는 문제를 푸는 알고리즘. 백준의 11404 문제가 대표적인 문제이다.구현은 간단하다. 시작점, 끝점, 중간점을 기준으로 for문을 작성하면 된다. 모든 정점에 대해 3번 반복문이 작성되므로 시간

5일 전
·
0개의 댓글
·

BOJ 11657 타임머신 (벨만-포드 알고리즘)

다익스트라와 거의 같은 방법으로 최소 비용 경로를 찾는 알고리즘이지만, 대신 비용에 음수가 있을 경우를 가정한 방법론.$G = (V, E)$로 표현되는 그래프에서 시간복잡도는 $O(V \* E)$이다. 모든 정점의 수만큼 반복하고($V$만큼), 각 반복마다 모든 간선을

5일 전
·
0개의 댓글
·

BOJ 11401 이항 계수 3

${N}\\choose{R}$을 구하는 간단한 문제이지만 $N$의 범위가 너무 커 단순 계산으로 풀 수 없는 문제이다. ($N\\le4,000,000$)수의 크기를 줄이기 위해 $\\frac{N!}{(N-R)!R!}$에서 팩토리얼을 미리 $1,000,000,007$으로

2022년 5월 26일
·
0개의 댓글
·

BOJ 10986 나머지 합

처음에는 길이가 1인 부분 구간, 2인 부분 구간...해서 길이가 $n$인 부분 구간인 경우를 모두 구하려 했다. 당연히 시간 초과가 났다.찾아보니 누적합과 나머지를 사용하여 풀 수 있는 문제였다. 예시 입력인 1 2 3 1 2을 넣었을 때의 풀이과정을 보자.문제에서

2022년 5월 5일
·
0개의 댓글
·

BOJ 12865 평범한배낭

전형적인 배낭 알고리즘 문제. 담을 수 있는 무게가 정해져있을 때 담긴 물건의 가치 합을 최대로 하는 알고리즘이다.dp 배열에 무엇을 메모이제이션으로 기록해야 하는지 생각해보면 어렵지 않게 풀 수 있다. dp\[i]\[j]에 메모해야 할 것은 i번째 물건까지 고려하고

2022년 5월 4일
·
0개의 댓글
·

BOJ 9251 LCS

이 문제는 점화식을 아예 외워두는 것이 의미가 있을 것 같아서 기록해둔다.LCS는 Longest Common Subsequence의 줄임말로, 두 수열(문자열)의 부분 수열 중 일치하는 최장의 수열을 의미한다. 문제에서 준 예시를 보면, ACAYKP와 CAPCAK LC

2022년 5월 2일
·
0개의 댓글
·

BOJ 2156 포도주 시식

평범한 dp문제이지만, 왜인지 안 풀리다가 나중에 내 오류를 발견한 문제. 처음 생각한 논리 구조는 다음과 같다.메모이제이션을 할 배열을 만든다. 배열의 구조는 \[\[0, 0] for \_ in range(n+1)] . 이는 \[앞 잔을 안 먹고 현재 잔 먹음, 앞

2022년 4월 29일
·
0개의 댓글
·

BOJ 1676 팩토리얼 0의 개수BOJ 2004 조합 0의 개수 (0의 개수)

두 문제 모두 결국 팩토리얼의 0의 개수를 세야 하는 문제다. 팩토리얼 우선 쉽게 구할 수 있는 팩토리얼의 0의 개수부터 생각해보자. 2와 5가 곱해져야 0이 생기고, 팩토리얼의 결과를 소인수분해하면 5의 지수가 2의 지수보다 작을 것이므로 결국 팩토리얼 계산 중 곱해

2022년 4월 21일
·
0개의 댓글
·

BOJ 2981 검문

주어진 숫자들을 정렬한 결과가 $a_1, a_2,...,a_n$ 이라 하자. 그럼 문제의 조건을 만족하는 $M$은 다음과 같이 나타내어질 수 있다.$$\\begin{aligned}&a_1 = b_1 M + r \\&a_2 = b_2 M + r \\&\\dots \\

2022년 4월 20일
·
0개의 댓글
·

BOJ 2609 최대공약수와 최소공배수 BOJ 1934 최소공배수 (유클리드 호제법)

두 수의 최대공약수를 구하는 알고리즘. 나머지가 0이 될 때까지 서로의 나머지를 재귀적으로 구한다. 코드는 간단하다.최소공배수는 두 수의 곱을 최대공약수로 나누면 되므로 호제법만 기억하자.

2022년 4월 19일
·
0개의 댓글
·

[Vue] 트랜지션 transition

내 포트폴리오를 만들다 보니 찾은 <transition></transition> 태그. 페이지 전환 간 간단한 애니메이션을 넣기 위해 사용하는 태그(!)이다.CSS랑 결합해서 내가 원하는 애니메이션을 만드는 것이 가장 좋겠지만, 나는 공식 홈페이지에서 소개가

2022년 4월 19일
·
0개의 댓글
·

BOJ 10989 수 정렬하기 3

카운팅 정렬을 쓰면 된다고 나와 있어서 그냥 섰다가 메모리 에러 때문에 애먹은 문제.해결법은 생각보다 단순했다. 카운팅 정렬을 사용하되, counting 배열만 저장하고 나머지는 입력을 따로 저장하지 않고 처리하는 방법론이다.

2022년 4월 13일
·
0개의 댓글
·

카운팅 정렬

배열에 존재하는 원소의 갯수를 세고, 순서대로 그 배열을 나열하는 방식의 정렬. 배열의 최댓값을 $k$라 할 때 시간 복잡도는 $O(n + k)$.$k$가 크지 않다면 매우 효율적인 방법이다. 구현에는 여러 방법이 있지만 여기서는 싸피에서 배운 걸 작성한다.

2022년 4월 13일
·
0개의 댓글
·

버블 정렬

가장 기본적인 정렬 방법. 배열 내 원소들을 순서대로 탐색하며 뒤에 있는 원소보다 큰 원소의 경우 뒷 원소와 순서를 바꾼다.시간복잡도는 $O(n^2)$.

2022년 4월 12일
·
0개의 댓글
·

깃허브 프로파일 설정

깃허브에서 내 아이디 그대로 만든 리포는 Github Profile의 기능을 활성화한다. github.com/에서 볼 수 있는 마크다운이 깃허브 프로파일이다. githubprofileexample 일반 깃허브 리포처럼 README.md 파일을 수정하면 된다. 자세한

2022년 4월 11일
·
0개의 댓글
·

M1 맥에 pyenv로 파이썬 설치

pyenv로 파이썬을 설치하는 와중에 겪은 애로사항이 많아 기록해둠기존 것 삭제하고 M1 전용 brew 설치삭제설치안내에 따라 다음 실행pyenv 설치~/.zshrc 에 다음 내용 추가새 파이썬 설치여기서 문제 생길 경우 : 난 C 관련 문제가 많이 난 듯...다음을

2022년 4월 10일
·
0개의 댓글
·

BOJ 11729 하노이 탑 이동 순서

문제링크생각보다 쉽지 않았던 문제.재귀를 내릴 때 어떤 변수를 함께 내려야 하는 지 항상 생각할 것.하노이의 탑 같은 경우 링을 옮기려는 기둥의 번호를 재귀 함수의 변수로 사용하는 것이 핵심이다.중간 단계로 사용할 기둥은 set을 사용해 구함.나머지는 기초 재귀!

2022년 4월 10일
·
0개의 댓글
·

목표(희망편)

최소 1주일 5 커밋5번 모두 알고리즘 관련 내용 존재(문제풀이 혹은 개념정리)장고, 뷰 어떻게 했더라..?html css도 뭐 많았는데...?요건 아직 고민 중 => 서버를 어떻게 할지 잘 몰라서!일단을 colab 활용할 듯Ionic, Capacitor 함 써보자

2022년 4월 10일
·
0개의 댓글
·