다은하게

☞ 문제 1629번 : 곱셈 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net ☞ 풀이 ♤ A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. ♤ 곧이곧대로 알고리즘을 설계한다면, 런타임 에러를 직면하게 될 것이다. ♠ OverflowError : A를 B번 곱하여 정수에서 요구하는 범위를 벗어나는 결과값을 도출할 경우 ♠ MemoryError : 주어진 128 MB 메모리 제한을 넘길 경우 ♠ 시간 초과 : 주어진 0.5초 시간 제한을 넘길 경우 ♤ 분할정복 알고리즘을 적용하여 문제의 알고리즘을 설계하자. ☞ study ▷ 분할정복(Divide and Conquer) 알고리..

☞ 문제 14405번 : 피카츄 14405번: 피카츄 피카츄는 "pi", "ka", "chu"를 발음할 수 있다. 따라서, 피카츄는 이 세 음절을 합친 단어만 발음할 수 있다. 예를 들면, "pikapi"와 "pikachu"가 있다. 문자열 S가 주어졌을 때, 피카츄가 발음할 수 있는 문 www.acmicpc.net ☞ 풀이 문자열 s에서 "pi", "ka", "chu" 문자열을 제거하여 남은 문자열 tmp이 있다면, 피카츄가 발음할 수 없는 문자열이다. 반면에 tmp이 없다면, 피카츄가 발음할 수 있는 문자열이다. 문자열 tmp의 존재 유무는 tmp의 길이가 0인지 아닌지로 판별함을 의미한다. ☞ study ▷ sys.stdin.readline().strip()을 사용한다. sys.stdin.readl..

☞ 문제 13305번 : 주유소 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net ☞ 풀이 인접한 두 도시 사이의 도로의 길이에 대한 (n-1)개의 road 리스트와 주유소의 리터당 가격에 대한 n개의 oilPrice 리스트를 입력받는다. 제일 왼쪽 도시의 기름 금액을 cheap_oil(저렴한 금액)로 선언 및 초기화한다. 총 금액, total(출력값)은 각 도로의 길이와 지불한 기름 금액(cheap_oil)의 곱의 합이다. oilPrice 리스트에서 각 도시의 기름 금액을 비교하면서 cheap_o..

☞ 문제 주식가격 바로가기 ☞ 풀이 prices 리스트 각각의 값(가격)들이 떨어지는데 걸리는 시간(몇 초)을 출력한다. 자료구조 스택을 이용하여 시간 효율성을 높인다. 스택안에 prices 리스트의 인덱스를 push하여, 적절한 조건(가격이 이전 시간의 가격보다 떨어지는 경우)에 맞으면 pop하여 시간을 측정한다. 끝까지 떨어지지 않은 주식가격에 대한 인덱스 모두를 pop하여 시간을 측정한다. ☞ study ▷ 리스트 생성 시 value의 초기화 값과 리스트 크기를 같이 선언한다. ▶ 참고 파이썬에서 특정 크기의 목록을 만드는 방법 ▷ 파이썬에서 스택 자료구조는 따로 제공하지 않는다. list로 대체하여 스택을 표현한다. ▶ 참고 [Python] Stack 사용하기 ☞ 코드 def solution(pr..

☞ 문제 1920번 : 수 찾기 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net ☞ 풀이 n 크기의 n_list를 입력받아 오름차순 정렬한다. m 크기의 m_list를 입력받는다.이분탐색 알고리즘을 적용한 재귀호출을 통해 m_list 리스트의 원소값들이 n_list에 존재하는지 판단한다. ☞ study ▷ 런타임 에러를 막기 위해 input() 대신 sys.stdin.readline()을 사용한다. ▶ 참고 [Python 문법] 파이썬 입력 받기 ▷ 이분탐색 알..

파이썬으로 문제를 처음 풀어봐서 다소 시간이 걸렸다. ☞ 문제 1764번 : 듣보잡 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net ☞ 풀이 듣도 못한 사람 n명의 no_listen 리스트와 보도 못한 사람 m명의 no_see 리스트를 서로 비교하여 같은 사람의 이름을 받는다. 이때 같은 사람의 이름을 set 자료형을 이용하여 no_all 리스트에 저장한다. ☞ study ▷ 런타임 에러를 막기 위해 input() 대신 sys.stdin.readline()을 사용한다. ▶ 참고 [Python 문법] 파이썬 ..