helloahram

1. 문제 안에 숫자가 적힌 풍선 N 개가 원형으로 놓여져 있을 때 1번을 터뜨려 안에 적힌 숫자만큼 이동해 풍선을 터뜨리는 문제 숫자가 양수이면 오른쪽, 음수이면 왼쪽으로 이동한다  2. 제한시간 제한 2초 메모리 제한 4MB  3. 알고리즘 분류 * 자료 구조* 덱 4. 접근 방식 풍선들이 원형 구조를 이루고 있기 때문에 Deque 을 사용한다 🐣 정글에서도 많은 칭구들이 처음에 혼란을 겪었지만 Deque 는 디큐가 아니고 덱이라고 읽는다 🐣Deque 는 양쪽 끝에서 삽입과 삭제가 모두 O(1) 이기 때문에 원형 리스트를 다루는 데 효과적이다 풍선을 왼쪽 또는 오른쪽으로 이동해야 하므로, Deque 앞/ 뒤에서 쉽게 풍선을 넣고 뺄 수 있다 풍선을 터뜨린 후에 해당 풍선을 삭제해야 하는데, 이 때..

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# 영문 알파벳, 공백, 소괄호와 대괄호로 이루어져 있는 문자열에서# 소괄호와 대괄..

split()입력 문자열을 공백 (스페이스, 탭, 개행 등) 기준으로 리스트 형태로 반환 사용 예시 word = input().split()# 입력hello world# 결과word = ['hello', 'world'] # 리스트로 저장strip() 입력 문자열의 양쪽 끝에 있는 공백 (스페이스, 탭, 개행 등) 을 제거하고, 문자열로 반환사용 예시 word = input().strip()# 입력hello# 결과word = 'hello' # 문자열로 저장 백준 1181 단어 정렬을 다시 풀어보면서, 나도 모르게 split() 을 썼는데 중복 제거를 하려고 썼던 data_list = list(set(data_list)) 에서 아래와 같은 에러가 나왔다 Traceback (most recent call la..

1. 문제2차원 평면 위의 점 N개를 y좌표 오름차순 기준으로 정렬하는 문제2. 제한시간 제한 1초메모리 제한 256MB3. 알고리즘 분류* 정렬 4. 접근 방식x 좌표 기준 정렬은 points.sort() 를 사용하면 돼서 간단했는데,y 기준은 아직 친하지 않은 lambda 를 활용해 보았다 좌표를 튜플로 입력 받아 리스트에 append 하여 저장하고 (x, y) == (point[0], point[1]) 로 두고 point 를 key 로 정렬하여 출력하였다 5. 전체 코드 # https://www.acmicpc.net/problem/11651# 2차원 평면 위의 점 N개를 y좌표 오름차순 기준으로 정렬하는 문제 n = int(input().strip())points = [] # 입력된 좌표를 저장할..

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),..

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

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

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

1. 문제00과 1로 이루어진 타일을 붙여 길이가 n인 모든 2진 수열의 개수를 구하고그 값을 15746로 나눈 나머지를 출력하는 문제 2. 요구사항시간 제한 0.75초 메모리 제한 256MB1 3. 알고리즘 분류* 다이나믹 프로그래밍4. 접근 방식처음에는 n = 7 까지 모든 경우의 수를 계산해 봤는데, 알고보니 피보나치 수열이었다그리고 같은조 ㅎㅇ님이랑 얘기하며 알게된 내용인데, 아래와 같은 사실을 알게 되었다1) 타일은 00 과 1 로 구분할 수 있다2) 그래서 n == 3 이상일 때◻️◼️◼️ 한 칸만 비어있는 경우는 빈 칸에 1 이 들어가고 ◻️◻️◼️ 두 칸이 비어있는 경우는 빈 칸에 00 이 들어간다고 생각하면n == 3 이상 일 때는 n-1 과 n-2 의 합이다(◻️◼️◼️ / ◼️◼️◻️..

1. 문제n 이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), 0  2. 알고리즘 분류* 수학* 다이나믹 프로그래밍 3. 접근 방식n 이 90까지라서 재귀로 풀면 시간 초과가 뜬다는 말을 듣고,어제 공부했던 Dynamic Programming 의 메모이제이션을 활용하여 구현해 보았다메모이제이션 - 이전 결과 값을 저장하여 중복 계산을 피하는 것  4. 코드 구현 def fibo(n): if n