| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 | 31 |
- AWS
- 알고리즘
- django ORM
- Django
- django widget
- 백준
- DRF
- 장고
- Algorithm
- 파이썬 알고리즘
- Baekjoon
- PYTHON
- CSS
- 알고리즘 연습
- java
- Git
- 알고리즘 문제
- js
- 알고리즘 풀이
- MAC
- 파이썬
- javascript
- web
- HTML
- c++
- API
- django rest framework
- react
- form
- es6
- Today
- Total
목록알고리즘 (87)
수학과의 좌충우돌 프로그래밍
한글, 워드 등의 에티터는 물론이고 웹페이지에서도 찾기 기능이 존재합니다. 본인이 원하는 단어나 음절이 있을 시에 이를 빠르게 찾아 줄 수 있는 기능이죠. KMP 는 바로 이 검색을 위한 알고리즘으로서 알고리즘을 만든 인물들, Knuth, Morris, Pratt 세 명의 이름을 따서 지었습니다. 이 알고리즘이 어떻게 동작하는지 함께 알아보도록 합시다. 단순한 문자열 검색 특별한 알고리즘 없이 문자열 검색을 구현한다면 아마 다음과 같이 생각하기 쉽습니다. 두 개의 문자열 P 와 T 에 대하여 문자열 P 가 문자열 T 에 몇 번이나 어느 위치에 있는지를 찾아야하는 문제입니다. 이 때 T의 길이를 n, P의 길이를 m 이라고 하면, 일반적으로 n>=m 이 성립합니다. n 0 && p[i] != p[j]) j..
문제보러가기 8901번: 화학 제품 문제 상근이는 각기 다른 병에 담긴 세 화학 물질 A, B, C를 가지고 있다. 두 화학 물질을 같은 양만큼 혼합하면, 화학 제품을 얻을 수 있다. A와 B를 혼합하면 AB가 되고, B와 C를 혼합하면 BC, C와 A를 혼합하면 CA가 된다. (A 하나와 B 하나를 혼합하면 AB 하나를 얻게 된다) AB, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다. www.acmicpc.net 입력으로 주어지는 모든 숫자는 1000이하이기 떄문에 다음과 같이 어렵지 않게 접근하였습니다. ab 혼합물의 수를 0부터 a,b의 갯수의 최소값까지 만들어준다. bc 혼합물의 수를 0 부터 ..
문제보러가기 8895번: 막대 배치 문제 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. 위의 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다. 막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만 www.acmicpc.net 동적계획법을 사용한 문제였습니다. 먼저 점화식을 세워보도록 하겠습니다. dp[n][l][r] 를 n 개의 막대에 대해, 왼쪽에서 보이는 막대가 l 개, 오른쪽에서 보이는 막대가 r 개인 경..
문제 보러 가기 9455번: 박스 문제 m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다. 그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다. 박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이 www.acmicpc.net ACM-ICPC 문제라고 하기에 쉽고 간단한 문제 였습니다. 박스는 각 column 에서만 이동을 할 수 있으므로 column 을 기준으로 나눠서 생각해주었습니다. 박스가 있을 경우, 바닥으..
이진 탐색 알고리즘 (Binary Search) 이진탐색의 특징 log N 의 시간복잡도 데이터가 정렬되있는 배열에서만 사용가능 반복문, 재귀함수를 통한 두 가지 방법으로 구현 가능 반복문을 통한 이진 탐색 구현 int search(int *arr, int length, int target) { int start = 0; int end = length-1; int mid = 0; while (start target) end = mid-1; } } return -1; } 재귀함수를 통한 이진 탐색 구현 int recursive_search(int *arr, int start, int end, int target) { int mid = (start+end) / 2; if (start > end) return..
안녕하세요 강민성입니다. 이번 포스팅에서는 소수를 찾는 방법에 대해서 알아보도록 하겠습니다. 소수를 찾는 방법이 여러가지가 있지만 그 중에 가장 효율이 좋은 '에라토스테네스의 체' 에 대해서 알아보도록 합시다. 최적의 소수 찾기, 에라토스테네스의 체 먼저 동영상을 보고 어떠한 원리로 소수를 찾는지 보도록 하겠습니다. 2부터 120까지 수 중 소수를 판별한다고 해보겠습니다. 다음과 같은 알고리즘으로 소수를 찾게 됩니다. 1. 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수들은 소수가 아니므로 체크한다. 2. 다음 숫자를 확인하여 체크가 안되있으면 그 수를 오른쪽에 쓰고 그 수의 배수들은 체크, 체크가 되어있으면 다음 수로 넘어간다. 3. 120의 제곱근까지 다음 과정을 반복한다. 이 알고리즘을 이제 C++ ..
안녕하세요 강민성입니다. 오늘은 오랜만에 알고리즘 문제를 들고 와봤습니다. 겨울방학 동안 백준 사이트에 있는 문제를 풀어보고자 하는데 좋은 문제가 있으면 많이 포스팅 하도록 하겠습니다. 오늘 소개할 문제는 1463번 '1로 만들기' 라는 문제 입니다. 문제부터 보도록 하겠습니다. 문제는 생각보다 간단합니다. 3가지 연산만 골고루 써서 1을 만들어 주면 되는 것이죠. 그래서 문제없이 코드를 작성하였습니다. 123456789101112131415X = int(input()) count = 0while X!=1: print(X) if X % 3 == 0: X //=3 count += 1 elif X % 2 == 0: X //= 2 count += 1 else: X -= 1 count += 1print(coun..
안녕하세요 강민성입니다. 오늘은 유클리드 알고리즘과 그 확장에 대해서 알아보도록 하겠습니다. 유클리드 알고리즘이란? 먼저 유클리드 알고리즘이란 유클리드 호제법이라고도 하며 두 수에 대해서 최대공약수를 구하는 방법입니다. 두 수가 일반적인 방법으로 최대 공약수를 구하기 너무 커졌을 때 이 유클리드 알고리즘을 사용하면 보다 쉽게 구할 수 있습니다. 이제 유클리드 알고리즘을 살펴보면 두 수 a,b에 대해서(a>b), a = q * b + r 라 하면 q 는 몫, r은 나머지가 됩니다. 이 때, gcd(a,b) = gcd(b,r) 이 성립하고 이와 같은 과정을 계속 거쳐 나머지가 0이 되었을 때 나누는 수가 a,b의 최대공약수에 만족하게 됩니다. 예시를 통해서 알아볼까요? 240꽈 46의 최대공약수를 구한다고 ..
안녕하세요 강민성입니다. 이번에 풀 문제는 2018서머코딩 알고리즘 문제 중 하나 입니다. 대회에서 나오는 문제들을 보면 매번 저런 문제를 어떻게 만들어내는지 그저 신기할 따름입니다. 문제를 이해하고 코드를 짜는 것도 적지 않은 시간이 걸리곤 하는데... 요즘 주변에 취업원서 넣고 코딩테스트 보러 가는 사람들이 많아서 그런지 알고리즘의 중요성을 새삼 다시 깨닫습니다. 1차에서 떨어지는 경우도 비일비재 하더라고요. 그러면 문제 보도록 하겠습니다. [ 문제 ] xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다. 각 사원은 딱 한 번씩..
안녕하세요 강민성입니다. 이번엔 간단한 문제지만 배울 점이 있어서 쉬운 문제를 하나 들고 왔습니다. 문제 한 번 보실까요? [문제] 프로그래머스 모바일은 개인정보 보호를 위해 고지서를 보낼 때 고객들의 전화번호의 일부를 가립니다. 전화번호가 문자열 phone_number로 주어졌을 때, 전화번호의 뒷 4자리를 제외한 나머지 숫자를 전부 *으로 가린 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 s는 길이 4 이상, 20이하인 문자열입니다. 입출력 예 phone_number return 01033334444 *******4444 027778888 *****8888 문제를 푸는데는 크게 어려움이 없었습니다. 12345678910111213def solution(phone_number):..