Passwd

문제 백준 온라인 저지에서 맞은 문제의 수와 이이디를 그대로 출력하는 프로그램 작성 입력은 없으며, 첫 줄에 맞은 문제의 수, 둘째 줄에 아이디를 출력한다. 풀이 백준 사이트로부터 값을 받아서 출력하는 문제가 아니라, 사용자가 직접 자신이 맞은 문제의 수와 아이디를 확인하여 출력하면 된다. 본인의 아이디와 맞은 문제에 대한 정보는 사이트 오른쪽 상단 아이디를 클릭하면 확인할 수 있다. 임의의 숫자나 문자열을 넣으면 틀린 것으로 채점한다니, 채점 시 출력 값과 실제값을 비교하는 모양이다. 풀이 코드 Python3을 사용했다. 직접 문제 수를 세고 싶지 않아 맞은 문제 목록을 복사하여 문자열로 저장한 뒤, 공백을 기준으로 자른 후 반환 배열의 길이를 출력하도록 했다. quest = "1000 1001 100..

문제 어떤 주식의 특정 기간 동안의 가격 변화가 주어졌을 때, 그 주식 한 주를 한 번 사고팔아 얻을 수 있는 최대 수익을 계산하라. 가격의 최대값과 최솟값을 구한 뒤 계산하는 것으로는 이 문제를 해결할 수 없다. 파는 행위가 사는 행위 후에 발생해야 하기 때문이다. 내 풀이 리스트의 첫번째 값을 빼서 구매금액으로 하고, 리스트의 나머지 값 중 최댓값을 판매금액이라고 한다. 판매금액과 구매금액의 차가 현재 최대 수익보다 크면 최대 수익 금액을 갱신한다. 이 반복은 리스트에 자료가 한 개 남으면 종료한다. def max_benefit(list): benefit = 0; while len(list) > 1: buy = list.pop(0) sell = max(list) if sell - buy > benef..

문제 좌우 무게를 비교할 수 있는 양팔 저울을 이용해 겉보기에 똑같은 동전 n개 중, 싸고 가벼운 재료로 만들어진 가짜 동전을 찾아라. 조건 저울질에 해당하는 부분은 아래 함수와 같다. 구현하고자 하는 알고리즘은 아래의 weight 함수를 통해 가짜 동전의 위치를 찾아야 한다. def weight(a, b, c, d): fake = 29 if a

모델링 (모형화) 주어진 현실의 문제를 정형화하거나 단순화하여 수학이나 컴퓨터 프로그램으로 쉽게 설명할 수 있도록 표현하는 것 자연이나 사회현상을 사람의 언어로 표현한 문제를 컴퓨터가 이해할 수 있는 수학식이나 프로그래밍 언어로 번역하는 철차 아래와 같은 그림으로 출발점과 도착점이 주어졌을 때 출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘을 구현하라. 위 문제를 모델링하면 a에서 출발해 p로 도착하는 최단 경로를 구하고, 그 경로를 출력하라. 미로는 그래프를 이용해 정의한다. 각 위치를 꼭짓점으로, 각 위치에서 직접 연결된 위치를 선으로 하는 그래프를 정의하면 된다. 코드 maze_info = { 'a': ['e'], 'b': ['c', 'f'], 'c': ['b', 'd'], 'd': ['..

그래프 (Graph) 꼭짓점(vertex)과, 그 꼭짓점 사이를 연결한 선(edge)의 집합 파이썬에서는 그래프를 표현할 수 있는 다양한 방법이 있지만, 이 글에서는 딕셔너리와 리스트를 이용한다. 꼭짓점을 key로 정의하고, 직접 연결된 꼭짓점 list를 value로 정의한 딕셔너리를 선언하여 그래프를 표현할 수 있다. fr_info = { "Summer": ["John", "Justin", "Mike"], "John": ["Summer", "Justin"], "Justin": ["John", "Summer", "Mike", "May"], "Mike": ["Summer", "Justin"], "May": ["Justin", "Kim"], "Kim": ["May"], "Tom": ["Jerry"], "Je..

딕셔너리(dictionary, 사전) 정보를 찾는 기준이 되는 키(key)와 키에 연결된 값(value)의 대응 관계를 저장하는 자료 구조 key-value 형태의 자료구조를 해시 테이블(Hash Table)이라고 하며, 프로그래밍 언어마다 다르게 불릴 수 있다. C++에서는 unordered_map, Java에선 haspmap이라고 부른다. 코드 # 빈 딕셔너리 선언 d = {} d = dict() # 선언과 동시에 초기화 d = { KEY1: VALUE1, # 키와 값은 콜론으로 구분 KEY2: VALUE2, # 키와 키는 쉼표로 구분 KEY3: VALUE3, KEY4: VALUE4 } # d 자료 개수 확인 len(d) # 값 찾기 d[KEY] # 값 추가. 키 중복 미허용. 기존 값이 있는 경우 ..

회문 回文, palindrome 순서대로 읽어도 거꾸로 읽어도, 그 내용이 같은 낱말이나 문장 낱말 사이에 있는 공백이나 문장 기호 등은 무시한다. 역삼역, wow, 다가가다, God's Dog 등을 예로 들 수 있다. 자료 구조 여러 가지 자료와 정보를 컴퓨터 안에 저장하고 보관하는 방식 주어진 자료를 효율적으로 정리하고 보관하는 것은 알고리즘 문제 풀이의 필수이므로 알고리즘과 자료 구조는 밀접한 관계를 가진다. 큐 Queue 사전적으로 줄, 줄을 서서 기다리는 것을 의미한다. 그 뜻처럼 먼저 저장한 자료를 먼저 빼내는 선입선출(FIFO, First In First Out) 방식의 자료구조다. 큐에 자료를 집어넣는 동작을 enqueue, 큐에서 자료를 빼내는 동작을 dequeue라고 한다. 코드 리스트..

이분 탐색(Binary search) 이분(二分)이란 둘로 나눈다는 뜻으로, 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳을 탐색한다. 이미 정렬되어 있는 자료에서 탐색 범위를 줄여가며 찾고자 않는 값을 찾는 탐색 방법이다. 이진 탐색이라고도 부른다. 계산 복잡도는 \(\mbox{O}(\log{n})\) 이분 탐색을 하기 위해서는 자료가 정렬되어 있어야 하지만, 필요한 값을 여러 번 찾아야 한다면 자료를 한 번 정렬한 후 이분 탐색을 이용하는 것이 효율적이다. 코드 def binary_search(val, list): start = 0 end = len(list) - 1 while start

버블 정렬 (Bubble Sort) 인접한 두 개의 자료를 비교하여 정렬하는 방법 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째 자료와 네 번째 자료 순으로 비교해가면서 마지막 자료까지 자료를 정렬하기를 반복한다. 버블 정렬은 한 회전을 마칠 때 자료 하나가 정렬됨을 보장하므로, 자료의 개수보다 한 번 적게 정렬을 반복한 뒤 완료한다. 또는 한 회전을 수행하는 동안 정렬한 횟수가 없으면 완료한다. 일반적인 경우, 계산 복잡도는 $$ \mbox{O}(n^2) $$ 코드 n - 1번 반복 def bubbleSort(x): length = len(x)-1 for i in range(length): for j in range(length-i): if x[j] > x[j+1]: x[..

퀵 정렬(Quick sort) 기준값과 비교하여 그룹을 나눈 후, 각각 재귀 호출하여 결과를 합치는 정렬 방식으로 분할 정복 알고리즘(Divide and conquer algorithm)의 하나이다. 아래 그림과 같은 방식으로 동작한다. 퀵 정렬은 얼마나 적절한 기준을 정하느냐에 따라 성능이 크게 좌우된다. 평균적인 계산 복잡도는 $$ \mbox{O}(n\log{n}) $$ 코드 (캐시 사용) def quick_sort(a): n = len(a) # 종료 조건 if n