본문 바로가기
[백준][파이썬] 1992번 쿼드 트리(분할정복2탄) [핵심] 핵심은 분할정복이였다. 활용 포인트: -x,y좌표 활용 -()를 어디다가 넣어줄지 생각 결국 분할정복1문제와 거의 유사한 패턴이다. 다만, ()로 어디다가( 혹은 )를 넣어줄지 재귀함수 특성을 이용하여 넣어주어야한다. 분할정복은 부분적으로 나눠서 검사할때 쓰인다. num = int(input()) lit= [] for i in range(num): t =list(input()) lit.append(t) stack = [] def tree(x,y,size,wnt,bnt): for i in range(x,x+size): for j in range(y,y+size): if int(lit[i][j]) == 0: wnt += 1 else: bnt +=1 if wnt == size*size: stack.a.. 2020. 3. 18.
[백준][파이썬] 2630번 색종이 만들기 [핵심] 분할정복 문제였다. 재귀함수를 활용하고, 시작점 끝점을 변수로 넘겨주는것이 중요하다. num = int(input()) lit = [] count = 0 counf = 0 for i in range(num): t = list(map(int,input().split())) lit.append(t) def go(num,num2,cnt,tnt,n): global count global counf for i in range(num,num+n): for j in range(num2,num2+n): if lit[i][j] == 1: cnt = cnt+1 elif lit[i][j] == 0: tnt = tnt+1 if cnt == n*n: count += 1 return elif tnt == n*n: cou.. 2020. 3. 16.
[백준][파이썬] #15649번 N과 M (1) [핵심] 이 문제는 n,m이 8로 제한되어 있어 재귀함수를 이용하지 않아도 상관없다. 하지만 이후에 문제들이 재귀함수를 활용해야 풀리기 때문에 이 문제도 그런 방식으로 공부했다. 재귀함수안에는 1. 일정 조건이 충족되면 출력하는 if문(M개가 쌓이면 출력된다) 2. 사용여부를 체크하고 사용되지 않았으면 stack에 값을 넣어주는 함수 3. 재귀함수 선언 후에, checklist를 다시 False로 바꿔주는 선언문 출력과정을 정리해보자 stack에 1저장 -> stack에 2저장 -> [1,2]출력 후 함수 하나 종료 -> checklist[2] False선언 -> stack에 3저장 -> [1,3]출력 이 구조를 여러번 그려보자 n,m= map(int,input().split()) checklist = .. 2020. 3. 15.
[백준][파이썬] 4763번 셀프넘버 for k in range(1,10000): count = 0 for i in range(1,k): sum =0 litt = list(str(i)) for j in litt: sum = int(j)+sum sum = sum + i if sum == k: count +=1 if count == 0: print(k) 위의 코드와 같이 이중포문을 작성하여 모든 수를 계산하는 방식을 했다. 하지만 시간초과가 발생했다. 이후에 재귀함수로 했지만 10000번이 넘게 돌아서 그런지 오버플로우가 발생했다 이를 해결하기 위해선 set수를 활용한 생각의 전환이 필요했다. num = set(range(1,10001)) generated_num = set() for i in range(1,10001): for j in str.. 2020. 3. 13.
[백준][파이썬] 2164번 카드2 [핵심] 큐의 기능을 공부하고 배운대로 큐를 만들어서 하면 오류가 난다. 밑의 코드와 같이 Collection코드를 이용해야 한다 import collections card_num = int(input()) card_deque = collections.deque([i for i in range(1, card_num +1)]) while len(card_deque) != 1: card_deque.popleft() card_deque.rotate(-1) print(card_deque[0]) 2020. 3. 12.
[백준][파이썬] 4949번 균형잡힌 세상 [핵심] 스택을 활용한 괄호 검사 문제이다. 이전에 단순(())를 검사하는 문제와 거의 유사하지만 조금의 차이점이 있다. "("와 "["를 구별해주어야 한다는 점이다. 또한 "(" 다음에 "]"가 아닌 ")" 오는지를 검사해주어야하는데 이를 비교하기 위해 change함수를 추가로 도입했다. 나중에 이런 유형의 문제에서 다양한 변수 혹은 기호가 쓰여도 check해주는 부분에 함수를 활용하면 될것같다. def change(str): if str == "]": t = "[" return t elif str == ")": return "(" while True: tmp = 0 str = input() stack = [] if str == ".": break lit = list(str) for i in lit: .. 2020. 3. 12.
[백준][파이썬] 17478번 재귀함수가 뭔가요? 재귀함수를 정확히 이해 할 수 있는 문제이다. 재귀함수의 구성큰 크게 3부분으로 나눌 수 있다 1. 탈출을 위한 조건문 특정조건을 설정하여 return을 해주지 않으면 재귀함수에서 영영 빠져나올수 없다 탈출조건문은 한번 시행되며, 마지막 작업을 입력해야 한다. 2. 함수 시작~ 재귀함수호출문 전 재귀함수가 반복될때 순서를 잘 파악하며 코드를 작성해야한다. +1 +2 +3 3. 재귀함수 호출 이후 ~ 함수의 끝 2번은 +1 +2 +3 순으로 작동된다면 3번은 +3+2+1 역순으로 함수가 작동된다. *정답을 맞았지만, 제출하자 틀렸다고 나왔다. 이런 출력형식이 복잡한 문제는 ""나 마침표 등을 조심하자! num = int(input()) print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.. 2020. 3. 11.
[백준][파이썬] 1181번 단어정렬 [핵심] 1. 2차원으로 형성된 리스트는 set으로 중복제거가 불가능하다. *리스트안에 튜플형식을 이용하면 set으로 중복제거가 가능하다. 2. 길이가 각각 다른 알파벳의 오름차순/내림차순 비교는 각각의 리스트로 비교하지말고 str형식으로 저장하여 비교하자. lit = [] for i in range(int(input())): t = input() tnum = len(t) lit.append((t,tnum)) lit = list(set(lit)) lit.sort(key = lambda x:(x[1],x[0])) for i in lit: print(i[0]) 2020. 3. 11.
[백준][파이썬] 1874번: 스택 수열 Stack을 연습할 수 있는 좋은 문제 num_list = [] plus_minus = [] count = 1 possibility = True for i in range(int(input())): num = int(input()) while count 2020. 3. 11.

티스토리툴바