다시 시작

https://www.acmicpc.net/problem/13900 13900번: 순서쌍의 곱의 합 첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000) 두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다. www.acmicpc.net 시간복잡도 - 풀이를 바꿔가면서 풀어봤는데도 계속해서 시간초과가 발생하여 챗gpt한테 물어봤다. for 문법 → O(N) sum(list) 연산 → O(N) for문 안에서 sum(list) 연산을 반복하면 → O(N^2) 쓸데없이 반복하던 연산을 없애고, 한 번만 계산하여 변수에 저장하여 활용하는 방식을 알려줘서 해당 방법대로 다시 접근하여 풀어봄 [풀이 과정 - 통과한 코드] ''' 풀이 6. su..

https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 수학 개념 구현 --- 음.. 기본적인 수학 개념으로 푸는 문제였지만, N진수에 대한 개념이 부족한 나를 위해 정리함 10진수를 N진수로 변환하는 과정은 10진수의 수를 N으로 나누어 나오는 나머지를 연산의 역순(가장 마지막의 수가 가장 앞에 온다)으로 나열하면 됨 (이 간단한 개념을 헷갈려 했다는게 너무 부끄럽...) --- [ 사용한 함수 ] - list.insert(값을 넣을 위치_인덱..

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 자료구조 - 스택(stack) --- 수많은 오답의 향연.. python으로 풀었을 때 시간초과 잡는 법 새로 공부하기 (pypy3로 통과 얌시 씀) 그런데 틀렸다고 한 것도 결과값에 NO라고 출력해야 하는걸 대충보고 no라고 써서 그런 것 어쩐지 반례를 아무리 넣어도 vscode에서는 전부 정답으로 나오더라니.. ..

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 자료구조 - 스택(stack) + 정규표현식 --- 1. 스택(리스트)의 인덱스 슬라이싱 범위 제대로 이해하기 2. 문제 제대로 이해하기 처음엔 괄호, 대괄호를 구분하여 각자의 쌍이 맞으면 된다고 접근했으나, 한 문장 안에서 쌍이 맞아야 함. (), [] 만 인정되고, 똑같은 구성이더라도 (], [) 이면 틀린 것 3. stack이 후입선출 이므로 괄호를 넣으면서 쌍을 이루면..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 자료구조 - 큐(queue) 파이썬에서 자료형 큐를 사용할때는 deque 로 사용하면 된다. deque는 collections 라이브러리에 내장되어 있어 from collections import deque로 사용 가능하다. - queue는 '선'입 '선'출 형태 자료구조이고, deque의 경우 양방향 큐로 선입,후입 어느쪽으로든 뺄 수 있다. --- deque는 rotate(회전)이 가능한데 음수를..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 다이나믹 프로그래밍 다이나믹 프로그래밍 : 필요한 계산 값을 저장해두었다가 재사용 하는 알고리즘 설계 기법 ● top-down 방식 큰 문제부터 시작해서 작은 문제로 분할해 가면서 푸는 것 ● bottom-up 방식 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것 ● 메모이제이션(캐싱) 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법 메..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 자료구조 - 스택(stack) 파이썬에서는 따로 stack이라는 라이브러리? 모듈은 없고, 리스트를 사용하면 된다. stack은 '후'입'선'출 형태의 자료구조이며, 차곡차곡 쌓인 것을 위에서부터 덜어낸다고 생각하면 된다. --- 문제를 풀 때 함수(def)를 만들거나, class를 생성하여 작성하고 싶었는데 가변적인 파라미터를 받을 때 적용 방법이나, class 생성 등에서 부..