본문 바로가기
[백준][파이썬] 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.
[파이썬][백준] 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.
[파이썬][백준] 9466 텀프로젝트 - 시간초과 시간초과가 발생했다. 그 이유는 이중포문떄문일까...? 아직 잘 모르겠다. import sys numtest =int(sys.stdin.readline()) count =0 for i in range(numtest): numstu = int(sys.stdin.readline()) check = [False]*numstu stu_sel =list(map(int,sys.stdin.readline().split())) for j in range(numstu): # 매칭시 True로 만들기 stack=[j] if check[stu_sel[j]-1] == False: while True: if check[stu_sel[j]-1] == False: stack.append(stu_sel[j]-1) j = stu_se.. 2020. 3. 27.
[파이썬][백준] 에라토스테네스의 체 골드바흐의 추측 문제를 풀려다보니, 에라토스테네스의 체의 소수를 구하는 방법을 공부하기 위해 풀었다. 생각보다 너무 간단했다. 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.
[백준][파이썬] 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.
[파이썬][백준] 2609번 최대공약수와 최대공배수 A,B = map(int,input().split()) if A>B: num = B num2 =A else: num = A num2 = B for i in range(1,num+1): if num2 % i ==0 and num % i==0: total = i print(total) print(int(A*B/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.

티스토리툴바