O'bin and the Chocolate Factory

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net sol1) stack 배열에 열린 괄호는 추가, 닫힌 괄호는 열린 괄호 있으면 pop으로 제거 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 while True: stack = [] line = input() if line == '.': # 종료조건 break for i in line: i..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 n = int(input()) # 5kg 봉지 최대 가능 수 부터 시작 for i in range(n//5, -1, -1): # 만약 5kg 봉지 최대 가능 수의 나머지가 3으로 나누어떨어지면 if (n - (i * 5)) % 3 == 0: # 5kg 봉지 수 + 3kg 봉지 수의 합 출력 print(i + (n - (i * 5)) // 3) break # 루..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 1234567891011121314import sys n = int(sys.stdin.readline()) # input()으로 입력 시 시간초과 nums = [0] * 10001 for _ in range(n): nums[int(sys.stdin.readline())] += 1 # 입력 값을 인덱스로 하는 위치에 1 더하기 for i in range(10001): if nums[i] != 0: # 입력 값이 있으면..

이진 검색 정렬된 배열에서 효율적으로 검색할 수 있는 알고리즘, 선형 검색보다 빠름 배열의 중앙을 기준으로 검색값과 비교해서 대소에 따라 검색 범위를 절반씩 줄이는 알고리즘 시간복잡도 O(log n) 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 # 이진 검색 알고리즘 from typing import Any, Sequence """시퀀스 a에서 key와 일치하는 원소 이진 검색""" def bin_search(a: Sequence, key: Any) -> int: high = 0 # 검색 범위 맨 앞 원소 index lo..

- 배열 검색방법 중 가장 기본 - 직선 배열에서 검색하는 경우에 원하는 데이터를 찾을때까지 맨 앞부터 순서대로 검색하는 알고리즘 목차 선형 검색의 종료 조건 보초법 1. 선형 검색의 종료 조건 2. 보초법(sentinel method) 선형검색의 종료 조건 검사 비용 감소 방법 원본 데이터 맨 끝에 검색할 값(보초)를 추가 종료 조건 1번이 필요 없으므로 판단 횟수 반으로 감소 스캔 종료 시 찾은 데이터가 원본 데이터인지 보초인지 구별 필요 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 from typing import Any, Sequence import copy """ 시퀀스 seq에서 key와 ..

얕은 복사(shallow copy) - copy() 리스트 복사 시 사용하는 copy() 함수는 얕은 복사 실행 원본 값 변경 시 복사본 값도 변경됨 원본과 복사본이 같은 주소를 참조하기 때문 1 2 3 4 5 6 7 x = [[1,2],3,4] y = x.copy() # x를 y로 얕은복사 print(f'y = {y}') x[0][1] = 7 # x배열의 값 2를 7로 수정 print(f'x = {x}') print(f'y = {y}') cs 깊은 복사(deep copy) - copy.deepcopy() copy 모듈의 deepcopy() 함수 사용 참조값 뿐만 아니라 참조하는 객체 자체를 복사 원본 수정해도 복사본에 영향 X 1 2 3 4 5 6 7 8 9 import copy x = [[1,2],3..

탐욕법(Greedy Algorithm) 매 순간 최선의 경우만 선택 -> 모든 경우 확인하지 않아 완전탐색보다 빠름 다른 경우는 고려하지 않음 -> 그리디로 풀면 반드시 틀리는 문제 존재 반례가 없는지 신중히 고민해야함 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 ..

브루트 포스(Brute Force) 시간 제한에 걸리지 않을 것 같거나, 풀이 방법이 바로 떠오르지 않는 문제의 경우 완전탐색으로 풀이를 시작하는 것도 방법 순열(permutation) 모든 경우의 수를 순서대로 살펴볼 때 용이 1 2 3 4 5 6 from itertools import permutations v = [0,1,2,3] for i in permutations(v,4): print(i) cs 조합(combination) 배열에서 특정 n개를 뽑아야 하는 경우(순서 상관 x) 1 2 3 4 5 6 from itertools import combinations v = [0,1,2,3] for i in combinations(v,2): print(i) cs

배열 - 배열 탐색 속도 : O(1) 배열은 임의접근(random access)를 통해 빠르게 탐색 가능 => 탐색 속도 O(1) ex) arr[2]에 접근 위해서는 => arr 배열 시작 주소 + 2(인덱스)*4byte(int 크기) = arr[2]의 메모리 주소값 - 배열 삽입/삭제 속도 : O(N) 삽입/삭제는 O(N)으로 탐색보다 느린데 왜냐하면 삽입/삭제를 위해서는 나머지 인덱스의 값들을 움직여야 하기 때문에 최소 0개~최대 N개를 미뤄야 하므로 시간복잡도가 O(N) 연결리스트(Linked List) - 연결리스트 탐색 속도 : O(N) 연결리스트는 배열과 달리 임의접근 불가 n번째 인덱스에 가기 위해서는 n개의 노드를 거쳐야 하므로 O(N)으로 탐색 속도 느림 - 연결리스트 삽입/삭제 속도 :..

NVD - CVE-2023-6977 악성 사용자가 우회를 통해 서버의 민감 파일을 읽을 수 있다. [ 취약점 분석 ] (참고한 Writeup) 함수 is_local_uri 내부에 취약점이 존재한다. uri 값을 //proc/self/root라고 넣는 경우, urlparse가 파싱하는 hostname이 proc이 되어 is_local_uri가 False가 return된다. //proc/self/root가 local URI가 확실하더라도 리눅스에서는 //가 /로 인식 되기 때문이다. 이 취약점을 이용하면 공격자가 서버의 민감한 파일에 접근해 파일을 읽을 수 있다. [ Exploit ] - 환경 설정 취약점이 발견된 버전은 1.0.0 - 2.8.0인데, 현재 pip3 install mlflow로 설치하면 취약..