꾸준히 써보는 공부 기록

탐색 (Search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미. 대표적인 탐색 알고리즘으로 DFS, BFS. 자료 구조 ‘데이터를 표현하고 관리하고 처리하기 위한 구조’를 의미. 그 중 스택과 큐는 자료구조의 기초 개념으로 pop과 push로 이루어져 있다. 스택 (Stack) 박스 쌓기 !! FILO 구조이다 (First In Last Out) !! 삽입 순서 : a - b - c 삭제 순서 : c - b - a stack = [] stack.append(a) stack.pop() 파이썬의 경우, 기본 리스트에서 append( )와 pop( ) 메서드를 이용. 큐 (Queue) 대기줄 !! FIFO 구조이다 (First In First Out) !! 삽입 순서 : a - b - c 삭..

구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 흔히 알고리즘 대회에서 구현 유형의 문제란? ⇒ 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭 완전 탐색 : 모든 경우의 수를 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행해야 하는 문제 유형 파이썬에서 리스트 크기 리스트를 이용할 때에 고려해야 할 사항 -> 코딩 테스트의 메모리 제한 대체로 코딩 테스트에서는 128~512MB로 메모리를 제한한다. 메모리 제한을 염두로 두고 코딩!! 데이터 개수(리스트 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB

https://covenant.tistory.com/131 그리디 알고리즘(Greedy Algorithm) 및 백준 문제 추천 조감도 탐욕 알고리즘 아이디어를 활용한 알고리즘(문제들) 입니다. 도입 제주 카카오에서 일하고 있던 무지는 판교 카카오에 있는 라이언이 빨리 오라는 카톡을 보고 판교 카카오로 이동하려 covenant.tistory.com 위 블로그 저자분의 글을 참고하여서 공부를 할 예정이다!! 꼼꼼하게 공부를 하셔서 많은 도움이 되고 있다!! 그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 아직 그리디 알고리즘의 풀이법을 바로 생각해내는데 어려움이 있다... 그리디는 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서..

문제 M 이상 N 이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 예제 입력 1 3 16 예제 출력 1 3 5 7 11 13 해결 방법 에라토스테네스의 체를 이용해서 해결하였다. 에라토스테네스의 체 알고리즘 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용 에라토스테네스의 체 알고리즘의 구체적인 동작 과정은 다음과 같다. 2부터 N까지의 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하..

문제 한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다. x와 y는 정수이다. 이 직사각형에 하나의 대각선을 그렸다. 직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다. x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 가로의 길이 xcm와 세로의 길이 ycm가 주어진다. x와 y는 1,000,000,000 이하의 자연수이다. x와 y 사이에는 빈칸이 하나 이상 있다. 출력 첫째 줄에 대각선이 그려져 있는 타일의 개수를 출력한다. 예제 입력 1 8 12 예제 출력 1 16 해결 방법 타일 위에서의 직선을 생각해보았..

문제 분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자. 두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력 첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다. 예제 입력 1 2 7 3 5 예제 출력 1 31 35 해결 방법 유클리드 호제법 (Euclidean Algorithm)을 이용해서 계산하였다. 두 분수가 주어졌을 때,..

문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4*5/6 1/2+3+4-5*6 1+2/3*4-5+6 1/2*3-4+5+6 식의 계산은 연산자 우선..

문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. 예제 입력 1 110 예제 출력 1 99 해결 방법 스터디 내용을 토대로 Brute Force Search 방식을 사용해서 모든 값을 확인하는 방식을 사용하였다. 수가 10보다 작은 경우 count에 1을 더하고, 10보다 큰 경우, 반복문을 통해서 등차수열임을 확인하고 등차 수열이 맞는 경우 count에 1..

문제 수현이는 4차 산업혁명 시대에 살고 있는 중학생이다. 코로나 19로 인해, 수현이는 버추얼 학교로 버추얼 출석해 버추얼 강의를 듣고 있다. 수현이의 버추얼 선생님은 문자가 2개인 연립방정식을 해결하는 방법에 대해 강의하고, 다음과 같은 문제를 숙제로 냈다. 다음 연립방정식에서 x와 y의 값을 계산하시오. $$\begin{cases}ax+by=c\\dx+ey=f\end{cases}$$ 4차 산업혁명 시대에 숙제나 하고 앉아있는 것보다 버추얼 친구들을 만나러 가는 게 더 가치있는 일이라고 생각했던 수현이는 이런 연립방정식을 풀 시간이 없었다. 다행히도, 버추얼 강의의 숙제 제출은 인터넷 창의 빈 칸에 수들을 입력하는 식이다. 각 칸에는 −999 이상 999 이하의 정수만 입력할 수 있다. 수현이가 버추..

문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 예제 입력 1 216 예제 출력 1 198 해결 방법 스터디 내용에 맞춰서 Brute For..