helloahram

1. 문제 영문 알파벳, 공백, 소괄호와 대괄호로 이루어져 있는 문자열에서 소괄호와 대괄호가 짝을 이루는지 판단하는 프로그램  2. 제한시간 제한 1초 메모리 제한 128MB  3. 알고리즘 분류 * 자료 구조* 문자열 * 스택  4. 접근 방식 9012 괄호 https://www.acmicpc.net/problem/9012 문제는간단하게 stack 를 이용해서 ( 이면 stack 에 넣고, ) 이면 pop 해서 짝을 맞췄는데 괄호의 종류가 두 개가 되니 ) 이면 ( 이랑 맞추고 ] 이면 [ 와 맞추는 작업을 추가했다  5. 전체 코드 w/ Python # https://www.acmicpc.net/problem/4949# 영문 알파벳, 공백, 소괄호와 대괄호로 이루어져 있는 문자열에서# 소괄호와 대괄..

MySQL 에 Dummy Data 삽입 w/ Python 더미 데이터가 필요한 일이 생겨서 코드를 만들어봤다 userTest 라는 Table 을 만들고 id, name, email Column 으로 구성했다 CREATE TABLE userTest ( id INT AUTO_INCREMENT PRIMARY KEY, name VARCHAR(100), email VARCHAR(100));Cursor 커서 MySQL 에서 SQL 쿼리를 실행하고 그 결과를 가져오는 역할커서를 사용하여 SELECT, INSERT, UPDATE, DELETE 같은 SQL 문을 실행할 수 있다  import mysql.connectorimport randomimport string # MySQL 연결 정보 config = { ..

유클리드 호제법 Euclidean algorithm2개의 자연수의 최대공약수를 구하는 알고리즘 호제법 - 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘  유클리드 호제법 진행 순서1. 두 수 중 큰 수를 작은 수로 나눈다2. 나머지가 0이면 작은 수가 최대 공약수가 된다3. 나머지가 0이 아니면 작은 수가 큰 수가 되고, 나머지가 작은 수가 되어    다시 큰 수를 작은 수로 나눈다  유클리드 호제법 특징1. 시간 복잡도 O(log(min(a, b))) - 두 수의 크기에 비례하여 알고리즘의 수행 시간이 결정된다 2. 재귀적으로 구현도 가능하다 ( gcd(a, b) -> gcd(b, a % b) )+ 최대공약수 성질 중에 gcd(a, 0) = a 라는 성질도 있다, 즉, 어떤 수와..

1. 문제 최대 K 만큼의 무게만을 넣을 수 있는 배낭에무게 Weight 와 가치 Value 를 가지는 N 개의 물건이 있다배낭에 넣을 수 있는 물건들의 가치의 최대값 찾기 2. 제한시간 제한 2초, 메모리 제한 512MB물품의 수 1 버틸 수 있는 무게 1 각 물건의 무게 1 해당 물건의 가치 0 3. 알고리즘 분류* 다이나믹 프로그래밍 * 배낭 문제 4. 접근 방식Knapsack Problem 을 한 번 공부했다 Knapsack Problem 개념 정리 물건을 쪼갤 수 있다는 언급은 없어서 0-1 Knapsack 방식으로 접근했다 예시 입력을 기준으로 - n = 4, k = 7, 물건 (6, 13), (4, 8), (3, 6), (5, 12) 일 때물건을 무게 오름차순으로 다시 정렬하고 (3, 6),..

배낭 문제 Knapscak Problem 최대 K 의 무게를 담을 수 있는 배낭 각기 다른 가치 V 를 가지고 W 의 무게인 N 개의 물건을 배낭에 최대한 가치가 높은 물건들로 담을 수 있는 조합을 찾는 문제  만약 n개의 물건이 있을 때, 가능한 모든 조합을 만들기 위해서는 2^n개의 경우를 시도해 보아야 하고그렇게 된다면 시간 복잡도는 O(2^n) 이기 때문에 Brute Force 는 적합하지 않다  배낭 문제는 물건을 쪼갤 수 있는 Fraction Knapsack Problem 과물건을 쪼갤 수 없는 0-1 Knapsack Problem 으로 나뉜다   부분 배낭 문제 Fraction Knapsack Problem 물건을 쪼개서 넣을 수 있다 가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는..

1. 문제두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다예를 들어, ACAYKP 와 CAPCAK 의 LCS 는 ACAK 가 된다 2. 요구사항시간 제한 0.1초메모리 제한 256MB 3. 알고리즘 분류* 다이나믹 프로그래밍* 문자열 4. 접근 방식 ㄷㅎ님이 기깔나게 설명해 주신 LCS 알고리즘을 이용하여 풀었다 LCS 알고리즘 정리한 내용 문제에서 문자열 A "ACATKP" 과 문자열 B "CAPCAK" 을 비교한 내용을 표로 정리하면 아래와 같다  0ACAYKP00000000C0011111A0112222P0112223C0122223A0123333K0123344 0 인 행렬을 추가한 이유는 비교 과정에서 대각선 +1 과 왼쪽/ 위쪽 비교를 위해서 추가했고,그렇기 때..

LCS 알고리즘Longest Common Subsequence 최장 공통 부분 수열 또는 Longest Common Substring 최장 공통 부분 문자열  Longest Common Substring두 개 이상의 문자열에서 연속적으로 나타나는 가장 긴 부분 문자열 찾기 부분 문자열은 주어진 문자열의 연속된 부분을 의미한다원래 문자열에서 특정 시작 위치에서부터 특정 끝 위치까지의 모든 문자를 포함한다이는 문자들이 연속적으로 이어져 있어야 하며, 반드시 전체 문자열의 일부분이어야 한다ex. 문자열 abcde 에서 bcd 는 부분 문자열이지만 acd 는 부분 문자열이 아니다 Longest Common Substring 찾는 방법 1. 문자열 A, 문자열 B 를 한 글자씩 비교해 보기2. 두 문자가 다르다면..

1. 문제계단에 쓰여 있는 점수가 주어질 때 점수의 최댓값 구하기1. 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다 2. 연속된 세 개의 계단을 모두 밟아서는 안 된다3. 마지막 도착 계단은 반드시 밟아야 한다2. 요구 사항* 계단의 개수는 300 이하의 자연수 * 계단에 쓰여 있는 점수는 10,000 이하의 자연수 3. 알고리즘 분류* 다이나믹 프로그래밍 4. 접근 방식계단을 올라가는 것만 생각하지 말고, 이미 올라간 상태에서 이전에 내가 어떤 계단을 밟고 올라올지를 생각하는 방식으로 접근한다1) 직전 계단 (n-1) 을 밟고 올라온 경우는 세번 연속 계단을 오를 수 없으므로 그 이전 계단은 n-3 번째 계단이다2) 두 칸 전 (n-2) 계단을 밟고 올라온 경우  i 번째 계단까지 올라왔을 때까지의..

그리디 알고리즘 Greedy Algorithm 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자는 알고리즘 설계 기법 항상 최적의 값을 보장하는 것이 아니라 최적의 값에 '근사한 값'을 목표로 한다  예시) 경로1 이 [ 1 - 1 - 1 - 100 ] 이고 경로2 가 [ 3 - 10 - 3 - 10 ] 일 때경로1 에서는 첫 세 단계에서 최적의 답을 선택했지만 최종 가중치는 103이고경로2 에서는 각 단계에서의 선택이 더 나은 결과를 가져와 최종 가중치가 더 작아진다이 때 경로1 에서의 선택이 그리디 방법론의 예시 그리디 알고리즘 주요 속성탐욕 선택 속성 Greedy Choice Property각 단계에서 '최선의 선택' 을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 ..

1. 문제2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오 2. 요구사항시간 제한 1초메모리 제한 256 MB1 3. 알고리즘 분류* 다이나믹 프로그래밍4. 접근 방식이것도 n = 7 까지 모든 경우의 수를 계산해 봤는데 아니나 다를까 피보나치였고n= 1 는 1, n = 2 는 2 를 초기값으로, n = 3 이상은 n-1 과 n-2 합으로 계산했다4. 코드 구현# 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 # 10,007 로 나눈 나머지를 출력한다 # 1