본문 바로가기
[백준][파이썬] 1182 부분수열의 합 핵심 1. visited 사용할때 not in stack 이 두개의 차이는 중복된 숫자를 체크 가능한지 여부이다. 2. depth를 다르게 줘야할때는 함수 밖에서 depth를 다르게 설정해서 줄 수 있다. N, S = map(int, input().split()) lit = list(map(int, input().split())) count = 0 visited = [False] * N def per(idx, depth, stack, max): global count if depth == max: total = 0 for sum in stack: total += sum if total == S: count += 1 for i in range(idx, N): if visited[i] ==False: vis.. 2021. 1. 18.
[백준][파이썬] 1759 암호만들기 시간초과가 안났다!!!!!1 일단, 핵심은 N과 M(2)번을 응용한것과 거의 동일하다. (N과 M 시리즈를 계속 반복해야겠다.) 숫자를 알파벳으로, 그리고 리턴하기전에 하나의 조건만 달아주면 끝! L , C = map(int,input().split()) lit = list(map(str,input().split())) s = "s" lit.sort() visited=[False]*C def per(depth,idx,stack,lit): if depth == L: count =0 for check in stack: if check in ["a",'e','i','o','u']: count +=1 if count > 0 and L-count > 1: print("".join(map(str,stack))) f.. 2020. 4. 6.
[백준][파이썬] 11403번: 경로찾기 BFS문제 BFS 문제인 이유: 인접 행렬들을 하나씩 True 해나가는 과정이기떄문. 사실 DFS로 풀어도 될것같긴하다 어차피 False처리를 계속 해주기때문에 메모리나 시간에 있어서도 비슷할것 같다는 생각이 든다. 핵심은 1. 초기값 dfs안에 한번에 stack변수에 저장(배추문제에서도 했다.) 2. collection 이용하여 시간단축 복잡하지 않은 문제였다. import collections num = int(input()) lit =[] visited = [[False for i in range(num)] for j in range(num)] for i in range(num): t = list(map(int,input().split())) lit.append(t) def dfs(stack): stack =.. 2020. 4. 2.
[백준][파이썬] 10973 이전순열 [핵심] 다음 순열과 원리가 반대이다 1. 왼쪽이 큰경우를 찾아주기 2. 그 수 보다 오른쪽에 있는 그 보다 작은 수 찾기 3. 두 개의 숫자 바꾸고 오름차순 정렬 *오름차순 정렬을 할때 이중포문을 해서 하면 시간초과가 난다. 대신 순열 특성상 이미 내림차순이 되어있다는 점을 활용하여 while문으로 뒤집어주면 된다. 사실 위에 말한 내용을 이해하려고 하면 쉽지 않을것이다. 로직을 스스로 작성하면서 봐야지 이해가 쉽다. num = int(input()) lit = list(map(int,input().split())) def recu(lit): n = len(lit) -1 i = n-1 while lit[i] 2020. 4. 2.
[백준][파이썬] 10972 다음순열 https://statssy.github.io/pro/2019/09/03/baekjoon_10972/를 참고했다. [백준 문제] P10972 다음 순열(파이썬) [백준 문제] P10972 다음 순열(파이썬) statssy.github.io def next_permutation(a): n = len(a) - 1 i = n while i > 0 and a[i-1] >= a[i]: i -= 1 if i == 0: # 마지막 순열 return False j = n while a[i-1] >= a[j]: # 오른쪽에 있으면서 a[i-1]보다 큰 수 j -= 1 a[i-1], a[j] = a[j], a[i-1] # SWAP j = n while i < j: a[i], a[j] = a[j], a[i] # a[i]부터.. 2020. 4. 2.
[백준][파이썬] 7569 토마토(2) - 3차원 [핵심] 3차원 리스트를 활용하고 index를 맞게 조절해주느라 조금 헷갈렸다. 나는 기본적으로 z축을 먼저 정렬하여 [z][x][y]구조로 생각했다. 최단거리 문제는 BFS가 어울린다. 왜냐하면 동시에 카운팅을 해주어야 하니까. *한번에 stack를 모두 처리하기 위해 while안에 포문을 한번더 설정해준것. *초기값 모두 한번에 해결하기 위해 dfs안 while밖에 포문으로 stack에 넣어준것 이 핵심이였다. 꼭 반복 연습하자 import collections #dq를 활용 m,n,h = map(int,input().split()) total =[] for i in range(h): lit =[] for j in range(n): t = list(map(int,input().split())) lit.. 2020. 4. 1.
[백준][파이썬] 2178 미로탈출 (최단거리) 처음에는 DFS문제라고 생각했다. 미로를 찾아가면서 결국 (M,N)에 도착한 값들을 list에 넣어주고 정렬시켜준다음에 최소값을 찾으면 되니까!! 결과는 잘 나왔다. 하지만 시간초과가 났다. 이런 최단거리 문제를 푸는 방법은 BFS라고 한다. 처음에 어떻게 하면 최단길을 찾을 수 있을지 고민했다. (왠지 동적프로그래밍에 더 가까워지는듯한....) 답은 생각보다 간단했다. 모든 블록에 값을 넣어주는것..(수학 문제풀떄랑 비슷했다.) 사용한 리스트가 꽤 많았다. visited - 방문여부 파악을 위해 사용 lit - 기존의 정보가 담겨있는 리스트 추가로 거리를 담아주는 리스트가 사용되었다. dlog- 흔적을 남기는 배열이다. DFS는 주로 재귀함수와 스택을 BFS는 주로 while문과 큐를 사용한다. n,m.. 2020. 3. 30.
[백준][파이썬] 2606 바이러스(DFS-Depth First Search) 사실 3번째 도전이였다.. 처음 DFS가 잘 모르는 상태에서 문제를 풀려고 했을때, 너무 어렵게 느껴졌고 DFS 개념을 보고 다시 문제를 풀려했을때도 어려웠다. 근데 분할정복, N과M 시리즈, 별찍기를 풀고 DFS 기본문제인 배추문제와 텀프로젝트 문제를 풀고 다시 돌아왔더니 너무 쉽게 풀려서 당황했다. 역시 지금 단계(실력)에서는 많은 고민 보다는 코드의 구조를 공부하고 변형하는 연습을 많이하는것이 실력 상승에 도움이 될것같다. num = int(input()) case = int(input()) lit = [[0 for i in range(num)] for j in range(num)] for i in range(case): x,y =map(int,input().split()) lit[x-1][y-1].. 2020. 3. 29.
[파이썬][백준] 에라토스테네스의 체 골드바흐의 추측 문제를 풀려다보니, 에라토스테네스의 체의 소수를 구하는 방법을 공부하기 위해 풀었다. 생각보다 너무 간단했다. num,k = map(int,input().split()) lit = [i for i in range(2,num+1)] count = 0 while True: q = lit[0] for i in lit: if i % q ==0: lit.remove(i) count += 1 result = i #마지막 값 저장 if count == k: break if count ==k: break print(result) 그리고 나서, 위의 기법을 활용하여 약수를 출력하도록 변행시켰다. num = int(input()) lit = [i for i in range(2,num+1)] count = .. 2020. 3. 27.

티스토리툴바