[Algorithm] 백준

Stack은 다음 그림과 같이 후입선출이다. (Last-In, First-Out)이 문제에서 input() 함수를 사용하지 않고 sys.stdin.readline() 함수를 사용한 이유는 시간초과 에러가 뜨기 때문이다.

'('개수를 세는 count라는 변수를 만들어서 '('가 나올때는 +1 해주고 ')'가 나올때는 -1 해준다. 마지막 괄호까지 읽었을 때 count가 0인 경우는 열린 괄호 수 만큼 닫혔다는 뜻이므로 바르게 구성된 문자열이다. 반면, count가 양수인 경우는

input으로 주어지는 수열(순서가 있는 숫자들)을 스택에 숫자를 넣었다 빼는 것으로 만들 수 있으면 push, pop 되는 과정을 출력하고, 만들 수 없으면 "NO"를 출력해라.

일단 스택의 LIFO 개념을 사용하기 위해 '커서 기준 왼쪽', '커서 기준 오른쪽' 이렇게 스택을 두개 만들었다.

Queue는 다음과 같이 먼저 넣은 데이터가 먼저 나오는 FIFO(First-In, First-Out)구조이다. 10828번 Stack을 풀때랑 거의 똑같이 구현했지만 결과를 한꺼번에 출력하는 것만 다르게 구현했다.

join 함수 : 리스트에 있는 요소들을 하나의 문자열로 바꾸어 반환하는 함수 ''.join(리스트): 매개변수로 ['a', 'b', 'c'] 리스트가 들어왔을 때 'abc'의 문자열로 합쳐서 반환

지금까지 리스트를 활용한 문제에서 요소를 추가할 때 뒤에 추가했기 때문에 append(리스트 마지막에 요소 추가)만 사용했었다. 하지만 이 문제에서는 "push_front X: 정수 X를 덱의 앞에 넣는다." 때문에 요소를 리스트의 맨 앞에 추가해야된다.

input을 입력받을때 rstrip()라는 것을 사용했다. rstrip('str'): 문자열의 오른쪽에서 str를 제거 1) str을 입력하지 않았을때 (=인자를 입력하지 않았을때): 문자열 오른쪽에 공백이 있다면 공백을 제거

괄호를 이용해 쇠막대기의 길이?를 결정하고 ()를 이용해 쇠막대기를 자르는 문제

우리가 보통 아는 계산식은 숫자와 숫자 사이에 연산자가 나오는데 ('1+2' 이런식)이 문제는 이름이 후위 표기식인 것처럼 숫자 두개가 먼저 나오고 연산자가 뒤에 나온다고 생각하면 된다. ('12+' 이런식)

사전이 '단어'와 그 단어를 설명하는 '뜻'으로 구성되어 있는 것과 마찬가지로 파이썬의 딕셔너리(Dictionary)도 키(key)와 값(value)의 쌍으로 이루어져 있다. 아래와 같이 딕셔너리를 생성할 수 있다.

이 문제의 포인트는 단어에 (1)포함되어 있는 경우에는 처음 등장하는 위치를, (2)포함되어 있지 않은 경우에는 -1을 출력하는 것이다. 먼저 (2)번은 처음에 딕셔너리를 선언할때 '-1'로 선언하는 것으로 구현했다.

이 문제에서는 한줄씩 입력받을 때 rstrip("\n")로 해야 된다. rstrip("")로 하게 되면 space도 제거되기 때문이다. 공백의 개수를 구해야 되기 때문에 공백은 남겨야 된다!

ord(): 특정한 한 문자를 아스키 코드 값으로 변환해주는 함수 chr(): 아스키코드 값을 문자로 변환해주는 함수 문자를 암호화하는 과정 (1) 해당 문자를 아스키코드 값으로 변환한다. (2) 13칸을 알맞게 움직인다. (3) 아스키코드 값을 다시 문자로 변환한다.

정렬 함수 -sort(): 원본 리스트 자체를 정렬하는 경우 ex) stack.sort() -sorted(): 원본 리스트를 이용해 정렬한 새로운 리스트를 만드는 경우 ex) newStack = sorted(stack)

소수인지 아닌지 판단하려면 보통 2부터 비교하는 숫자까지 하나씩 나눠가면서 나머지를 확인해야 된다. 하지만 비교하는 숫자의 제곱근까지의 수만 확인해도 소수인지 아닌지 판단할 수 있다.

변수 E, S, M의 범위가 각각 다르기 때문에 각 변수의 사이클이 다르다는 것에 집중해서 규칙을 찾아보려고 했다. 브루트포스 알고리즘: 완전탐색 알고리즘이다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

일곱 난쟁이들의 키의 합이 100이라는 사실을 통해 입력받은 9명의 난쟁이들에서 정답이 아닌 2명을 제외한 7명의 키의 합이 100이 된다는 것으로 모든 경우의 수를 구하는 문제이다.

이 문제에서 잘 이해해야 되는 부분들이 있다. 1. 완료한 일에 대해 받아야 되는 돈은 완료한 날에 받는 것이 아니라 그 다음날에 받는다. ex) 3일 걸리는 일을 1,2,3일동안 했으면 일을 완료한 3일에 바로 돈을 받는 것이 아니라 4일에 받는 것이다.

DFS (Depth-First Search, 깊이 우선 탐색) : 루트를 시작으로 탐색을 한다면 루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳까지 내려간다. 더 이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 곳이 있으면 즉각 내려간다.

Input을 하기 위해 사용한 함수를 정리해보자.nextInt() : System.in으로 입력 받은 값 중 Int값만 뽑아내 return(엔터) 전까지 반환한다.

String은 immutable(불변) 객체로 값을 수정하면 새로운 객체를 만든다. 따라서 메모리와 시간을 잡아먹는다. StringBuilder는 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식이기 때문에 속도도 빠르고 성능적으로도 부하가 적은 편이다.

원래 '에라토스테네스의 체' 알고리즘은 그 숫자의 배수만 지우는데 이 문제에서는 해당 숫자도 지운다. 예를들어 2의 배수를 지울때 원래는 2는 안지우는데 이 문제에서는 2도 같이 지워야 한다.

1. 소수인지 확인하기 -> 에라토스테네스의 체 : 네 자리 수이기 때문에 1~9999 사이의 모든 소수를 구해놓는다. 2. 최소 횟수 구하기 -> BFS : 현재 숫자에서 숫자 하나만 변경하며 BFS를 수행한다.

MxN 크기의 모눈종이 위에 주어진 좌표의 K개의 직사각형을 그린다. 그 K개의 직사각형의 내부를 제외한 나머지 부분의 각 영역의 넓이를 구한다. 각 영역의 넓이를 오름차순으로 정렬하여 출력한다.

1. 연결되어 있는 노드만 감염된다. 2. '컴퓨터의 수'만 구하면 되니까 BFS

무한의 정수가 들어갈 수 있는 가능성이 있을때 사용하는 BigInteger BigInteger는 문자열 형태로 이루어져 있다. BigInteger는 문자열이기 때문에 사칙연산이 안되므로 BigInteger은 클래스 내부에 있는 메서드를 사용해야 한다.

마지막 계단(n)은 반드시 밟아야 하므로 마지막 계단(n)을 밟기 전에 두가지의 경우의 수가 존재한다. 1) n-3계단을 밟고 두칸을 올라 n-1계단을 밟고 한칸을 올라 마지막 계단n을 밟는 방법 2) n-2계단을 밟고 두칸을 올라 마지막 계단n을 밟는 방법

Queue는 FIFO(First In First Out) 구조이다. 이 문제에 적용해보면, K번째마다 수를 제거하는 것이기 때문에 K번째가 아닐때는 해당 수를 뒤로 보낸다.

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구해야 하는 문제이다. => 1) 저장해야 하는 값이 String형 하나이다. (인덱스같은 다른 정보가 필요하지 않음) 2) 중복값을 제거해야 한다.

사전순 정렬 HashSet에는 정렬 메소드가 없기 때문에 사전순 정렬을 하기 위해 ArrayList로 바꿔서 정렬해주었다. Iterator Iterator는 모든 컬렉션 프레임워크에 공통으로 사용 가능하다. 컬렉션 프레임워크에서 쉽게 값을 가져오고 제거할 수 있다.