프로그래밍18

• 

  [Do-it! 코딩 테스트-기초편] 011. 스택으로 수열 만들기 문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 접근 데이터 크기: 100,000 시간 제한: 2초 스택을 사용하는 문제이다. 어떤 수열이 입력되면, 스택 동작 push, pop 만으로 만들어질 수 있는 수열인지 알아보는 문제이다. 스택에 push되는 값은 오름차순이어야한다. 코드 N = int(input()) from_list = list(range(N, .. 파이썬/코딩 테스트 2023. 10. 26.

• 

  [Do-it! 코딩 테스트-기초편] 009. DNA 비밀번호 문제 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 접근 코드 import sys S, P = map(int, sys.stdin.readline().split(' ')) DNA = input() DNA_list = list(map(int, sys.stdin.readline().split(' '))) # 1 DNAdict = {"A": 0, "C": 0, "G": 0, "T": 0} start = 0 end = P-1 c.. 파이썬/코딩 테스트 2023. 10. 26.

• 

  [Do-it! 코딩 테스트-기초편] 008. '좋은 수' 구하기 문제 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 접근 데이터 크기: 2,000 시간 제한: 2초 N^2의 연산은 충분히 가능하다. 하지만 N^3가 되면 2초안에 해결이 불가능하다. 2초 = 대략 80,000,000 데이터 반복문은 최대 2개까지 중첩이 가능할 듯 하다. N개의 수에서 자신(K)이 아닌 다른 두 수의 합으로 자신(K)과 같은 수를 만들 수 있다면 K는 '좋은 수'이다. 나(K)를 만들 수 있는 두 수를 찾으려면 투 포인터를 사용하는 것이 좋아보인다. 투.. 파이썬/코딩 테스트 2023. 10. 26.

• 

  [Do-it! 코딩 테스트-기초편] 007. 주몽의 명령 문제 https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 접근 데이터 크기: 15,000 시간 제한: 2초 재료를 2개 골라 합했을 때 갑옷이 완성되는 번호와 같다면 개수 증가 갑옷을 완성시킬 재료 2개를 고르려면 투 포인터를 사용하는 것이 좋겠다. 투 포인터와 정렬. 일반적인 정렬은 O(NlogN)의 시간 복잡도를 가진다. 데이터의 크기가 15,000이기 때문에 정렬은 문제 없다. 하지만 이중 for문을 사용한다면 시간 .. 파이썬/코딩 테스트 2023. 10. 25.

• 

  [Do-it! 코딩 테스트-기초편] 006. 연속된 자연수의 합 구하기 문제 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 접근 데이터 크기: 10,000,000 시간 제한: 2초 반복문을 사용해서 N까지의 숫자중 연속된 합을 모두 구하려면 시간이 초과된다. 이중 반복문을 사용하면 최소 O(N^2)의 시간복잡도를 가진다. 시간을 줄이기 위해서 투 포인터 방법을 사용해야한다. 시작 인덱스와 끝 인덱스를 지정한 후 각각을 조건에 따라 이동시켜 원하는 값인지 확인하는 방법으로 접근한다. 코드 im.. 파이썬/코딩 테스트 2023. 10. 24.

• 

  [Do-it! 코딩 테스트-기초편] 004. 구간 합 구하기 2 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 접근 2차원 합 배열을 구한다. D[x][y] = (0, 0) 부터 (x, y) 까지의 사각형 영역 안에 있는 수의 합 부분 합은 D[x2][y2]에서 어떤 구간의 합을 빼면 구할 수 있다. 코드 import sys input = sys.stdin.readline N, M = map(int, input().split(' ')) D = [[0] * N.. 파이썬/코딩 테스트 2023. 10. 23.

• 

  [Do-it! 코딩 테스트-기초편] 003. 구간 합 구하기 1 문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 접근 데이터 크기: 100,000 * 100,000 = 10억 (?) 시간 제한: 1초 구간마다 합을 매번 계산하면 시간이 초과됨. 구간 합 개념. 구간 합 공식을 그대로 사용하면 됨. 코드 import sys input = sys.stdin.readline N, M = map(int, input().split(' ')) sum = [0] * (N + 1) result.. 파이썬/코딩 테스트 2023. 10. 23.

• 

  [Do-it! 코딩 테스트-기초편] 002. 평균 구하기 문제 https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 접근 데이터 크기: 1,000 * 100 = 100,000 시간 제한: 2초 메모리 제한 128MB 과목의 개수를 입력하고, 개수만큼 점수를 한 줄에 입력한다. 파이썬으로 임의의 개수의 정수를 한 줄에 입력받기 -> map() 함수를 사용, list() 사용 list의 최대값을 구한다. 새로운 리스트에 새로 연산한 점수들 저장한다. 새로운 리스트의 평균을 구한다. 코드 N = int(i.. 파이썬/코딩 테스트 2023. 10. 22.

• 

  [Do-it! 코딩 테스트-기초편] 001. 숫자의 합 구하기 문제 https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 접근 데이터 크기: 100 시간제한: 1초 숫자가 공백 없이 주어진다는 건 (숫자의 개수) = (입력 숫자의 길이) 파이썬은 임의 정밀도 방식을 사용하기 때문에 변수에 저장하는 값의 크기에 제한이 없다. 2023.10.21 - [파이썬/기본] - [파이썬] 임의 정밀도 정수 - 미완 공백없는 숫자를 정수형 리스트로 변경해서 인덱싱하며 합을 구한다. 문자열 인덱싱을 하고 각 문자를 정수형으로 변경하여 합을 구한다. 문자열은 파이썬 내장 시퀀스 자료형중 하나이다. (파이썬 내장.. 파이썬/코딩 테스트 2023. 10. 22.

• 

  [파이썬] 컬렉션 타입, 세트 세트란 중복되지 않는 항목들의 컬렉션이다. set s1 = {} print(s1) print(type(s1)) # {}의 기본형은 딕셔너리 s1 = {1, 3, 5, 7} print(s1) print(type(s1)) set은 파이썬 컬렉션 타입중 하나이다. 쉽게 집합이라고 생각하면 좋다. set의 항목은 중괄호( {} )로 표현하는데 위 코드의 결과를 보면 s1의 타입이 dict로 나오는 것을 볼 수 있다. 사실 컬렉션 타입중 하나인 딕셔너리도 중괄호를 사용한다. 파이썬에서 요소가 없는 중괄호는 딕셔너리로 판단한다는 것을 알 수 있다. s1 = {1, 3, 5, 7} set의 형태는 쉼표(,)로 구분되어지는 요소들로 표현된다. list -> set # list를 set()함수를 통해 set으로 변환 l.. 파이썬/기본 2023. 9. 5.

• 

  [파이썬] 컬렉션 타입, 튜플 튜플이란 여러 항목을 순서대로 저장하는 컬렉션 타입이다. 리스트와 유사하지만 값들이 불변하다는 특징이 있다. 한번 생성된 후에는 요소를 추가, 제거 또는 수정이 불가한 데이터 구조이다. tuple tu1 = (1,) # 요소를 1개만 저장할 때 # tu1 = (1) print(tu1) # tu1[0] = 100 # TypeError: 'tuple' object does not support item assignment tu2 = (1, 3, 5, 7) print(tu2) tu3 = 1, 3, 5, 7 print(tu3, type(tu3)) tu4 = ('apple', 'banana', ('🍍', '🙊')) print(tu4) print(tu4[0]) print(tu4[2][0]) print(type(tu.. 파이썬/기본 2023. 9. 5.

• 

  [파이썬] 컬렉션 타입, 리스트2 2023.09.04 - [분류 전체보기] - 파이썬 6 - 컬렉션 타입, 리스트1 파이썬 6 - 컬렉션 타입, 리스트1 1. 컬렉션이란? 여러 개의 데이터 항목을 하나의 단위로 관리할 수 있게 해주는 데이터 구조를 의미. 여러 개의 데이터를 하나의 변수에 저장하고, 관리할 수 있게 해줌. 리스트, 튜플, 세트, 딕셔 caramelbottle.tistory.com 이전 글은 리스트의 개념과 사용방법에 대해 작성하였다. 이번 글에선 문자열 메서드와 같이 리스트에 사용되는 메서드에 대해 알아보자. 리스트2 len() li1 = [10, 20, 30] # len(): 객체의 길이(항목의 개수)를 반환하는 내장 함수입니다. print(len(li1)) append() li1 = [10, 20, 30] # appe.. 파이썬/기본 2023. 9. 4.