본문 바로가기
[백준][파이썬] 10971 원판원 순회2 - 시간초과.. num = int(input()) money = [] for i in range(num): tem = list(map(int,input().split())) money.append(tem) lit = [] ans = 10**8 def permu(visited,k): global ans if k == num: temnum =0 lit.append(visited) tem = visited for j in range(num - 1): if money[tem[j] - 1][tem[j + 1] - 1] == 0: temnum =0 break temnum += money[tem[j] - 1][tem[j + 1] - 1] if money[-1][tem[0]] == 0: temnum = 0 else: temnum +=.. 2020. 4. 6.
[백준][파이썬] 10974 모든 순열 "다음 순열" 방식을 이용해서 코딩을 했다. 하지만 아직 남은 의문이 있다.. 왜 len(lit) == 2를 continue를 추가로 작성해줘야하는지 의문이다. lit가 2일때 넘겨주면 len(lit)에서 타입에러가 발생하여 저렇게 처리해주긴했지만, 왜그런지는 아직 에러를 못잡았다. num = int(input()) def per(lit): n = len(lit)-1 i = n while i>0 and lit[i-1] > lit[i]: i -= 1 if i == 0: return 0 print(*lit) j = n while lit[i-1] > lit[j] and j>0: j -= 1 lit[i-1],lit[j] =lit[j],lit[i-1] j = n while i < j: lit[i] ,lit[j] .. 2020. 4. 5.
[백준][파이썬] 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.
[백준][파이썬] 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.
[파이썬][백준] 2667 단지번호 붙이기 [핵심] 배추문제랑 거의 동일한 문제 차이점은 수를 하나더 카운팅 해주는것뿐 While문을 활용한 del 기억하자!!! num = int(input()) lit = [] dx = [0,0,1,-1] dy = [1,-1,0,0] ans =[] cot =[] def recu(x,y): cnt = 0 stack = [[x,y]] while stack: x = stack[0][0] y = stack[0][1] del stack[0] cnt+=1 lit[x][y] = '0' for i in range(4): X = int(x)+dx[i] Y = int(y)+dy[i] if 0 2020. 3. 28.
[백준][파이썬] 1012 유기농 배추 BFS [핵심] BFS 분류되는 이유는 결국 1과 붙어있는것들을 모두 제거할때 count가 증가하기떄문이다. 연습해야할 코딩 방식 1. dx dy를 이용한 좌표처리 그리고 경계값 -1일때 인덱스 에러 안나게 범위 설정해주는것 2. 재귀함수를 이용한것이 아니라 While문으로 활용 3. [0]*n으로 배열을 만들면 이상하게 다르게 값이 출력된다.. (이유는 아직 모름) 주소값을 공유하는 개념때문인가? 여러번 코딩해서 구조 익힐것 numcase = int(input()) dx = [-1,0,0,1] dy = [0,1,-1,0] def recu(x,y): check = [[x,y]] while check: checka = check[0][0] #x,y값 저장 checkb = check[0][1] del check[0.. 2020. 3. 26.
[파이썬][백준] 1012 GCD [핵심] 이전의 문제와는 달리, 뉴클리드 호제법을 사용하였다. 기존의 FOR문으로 모든경우의 수를 카운팅 하는것보다 훨씬 메모리와 시간을 덜 잡을것같다 case = int(input()) def gcd(x, y): while y != 0: r = x % y x = y y = r return x for i in range(case): total = 0 num = list(map(int,input().split())) for i in range(1,len(num)-1): for j in range(i+1,len(num)): total += gcd(num[i],num[j]) print(total) 2020. 3. 26.
[백준][파이썬] 13015 별찍기(23) [핵심] 상당한 노가다로 푼 느낌이다. 재귀함수로 풀었어도 되긴 했겠지만, 많은 문제를 재귀함수로 풀었어서 이중포문을 활용해서도 풀어보고 싶었다. 앞으로 더 어려운문제는 재귀함수로 풀어야겠다. num = int(input()) print("*"*num,end="");print(" "*(2*(num-1)-1),end="");print("*"*num) for i in range(1,num-1): print(" "*i,end="");print("*",end="");print(" "*(num-2),end="");print("*",end="") print(" "*(2*(num-2)+1-2*i),end="") print("*", end="");print(" " * (num - 2), end="");print("*".. 2020. 3. 23.

티스토리툴바