본문 바로가기

전체 글137

DFS와 BFS - 1260번 DFS는 재귀로 구현하고, BFS는 스택으로 구현한다. 먼저 그래프를 만들어준다. DFS 방문했던 곳을 체크하기위한 배열을 준비한다. 방문시 방문했다고 표시한다. 그 다음 방문한 곳의 그래프를 검사하여 방문하지 않은 곳을 DFS함수에 넣어서 재귀적으로 탐색을 진행한다. BFS 방문했던 곳을 체크하기위한 배열을 준비한다. 방문시 방문했다고 표시한다. 방문한 곳을 스택에 넣는다. 스택에서 꺼내서 출력을 한다. 꺼낸 것의 그래프를 탐색하여 아직 방문하지 않은 곳을 스택에 넣는다. 스택이 빌 때까지 반복하면 모든 끝까지 탐색할 수 있다. import queue import sys from collections import deque input = sys.stdin.readline nodes, edges, sta.. 2022. 9. 10.
나무 자르기 - 2805번 이분탐색으로 해결해야 시간초과가 안생기는 문제이다. 처음에 나무 최대 길이에서 1씩 줄여가면서 답에 근접할 때 멈추는 방식으로 풀었었는데 역시나 시간초과가 발생했다. 이분탐색을 이용하여 나무 최대길이를 high, 최소길이인 0을 low로 둔다. 무한루프를 통해 중간길이를 계산하며 나무가 잘린 길이를 계산해준다. 만약, 나무가 잘린 길이가 너무 많다면 low = mid로 해주고, 나무를 덜 잘랐다면 high = mid를 해준다. 나무를 자를 길이는 양의 정수로만 계산되므로 무한루프의 종료지점을 high - low > 1로 해준다. import sys input = sys.stdin.readline n, m = map(int, input().split()) l = list(map(int, input().sp.. 2022. 9. 8.
소수 구하기 - 1929번 최대 범위까지(n) 소수를 다 구한 뒤 하나씩 비교하다보니 시간초과가 떴다. m 부터 n까지 수를 생성하면서 즉시 소수인지 판별하니 됬다. 숫자 n이 소수인지 판별하려면 n의 제곱근이하의 수들을 나눠보면 된다. m,n = map(int,(input().split())) a = [] for i in range(m,n+1): condition = True if i==1: continue for j in range(2, int((n+1)**0.5 + 1)): if i%j == 0 and i != j: condition = False break if condition == True: print(i) 2022. 9. 6.
소수 찾기 - 1978번 유명한 에라토스테네스의 체 방식으로 소수를 찾아준다. 1000이하의 소수를 미리 찾아 둔 후 검사해야하는 숫자들을 하나씩 검사해준다. n = int(input()) l = list(map(int, input().split())) a = [] for i in range(2,1000): a.append(i) for i in a: for j in a: if j%i == 0 and j != i: a.remove(j) cnt = 0 for i in l: if i in a: cnt+=1 print(cnt) 2022. 9. 6.
k번째 수 - 11004번 배열로 숫자들을 입력받고 정렬한다. 정렬된 배열에서 인덱스를 이용해 원하는 수를 뽑아낸다 n, k = map(int,(input().split())) l = list(map(int,(input().split()))) l.sort() print(l[k-1]) 2022. 9. 5.
괄호 - 9012번 올바른 괄호의 형태가 나왔을 때만 판별해야한다. 괄호중 ')'가 먼저 나오게 되면 항상 올바르지 않은 상황이니 'NO'가 나와야하며, 이 경우를 걸러내는 목적으로 코드를 짜면 빠르게 결과를 도출해낼 수 있다. '(' 가 나왔을 경우 체크용 변수에 1을 더해주고 ')' 가 나왔을 경우 -1을 더해준다. (체크용변수는 0부터 시작) 체크용 변수가 음수가 되면 break를 걸어 'NO'가 출력되게 하고 나머지 경우에 대해서는 'YES'를 출력한다. n = int(input()) for i in range(n): check = 0 #괄호 체크용 변수 result = 'YES' #최종 결과 확인용 변수 v = input() for j in v: if j =='(': check+=1 elif j == ')': ch.. 2022. 9. 4.
단어정렬 - 1181번 파이썬 배열의 매소드인 sort는 문자도 정렬해준다. 그냥사용한면 알파벳순으로 정렬해주고 sort(key = len) 처럼 사용하면 길이를 파악할 수 있는 자료형에 한에서 길이순으로 정렬을 해준다. 문제 조건에 맞게 sort()를 먼저한 후, sort(key = len)을 다음에 사용하여 정렬해준다. n = int(input()) l =[] for i in range(n): l.append(input()) l = set(l) l = list(l) l.sort() l.sort(key=len) for i in l: print(i) 2022. 9. 3.
3. Memorize Puzzle 3. Memory Puzzle 모듈 랜덤, 파이게임, 시스템, 파이게임로컬( * ) 변수선언 FPS 창크기 너비, 높이 보여지는 속도 박스크기, 간격 크기 박스 개수 행 열 assert 검사 ( 박스 개수는 짝수) 가로세로 마진 값 계산 색깔 선언 배경색 박스색 모양 선언 색깔 튜플화 모양 튜플화 assert 가능한 모든 도형의 가짓수의 2배가 박스의 개수보다 많아야 한다. main()함수 보여진 박스 데이터 기록 generateReavealedBoxesData( ) 보여진 박스의 정보를 기록하는 하뭇 보드판 랜덤화 getRandomizedBoard( ) icon 리스트 변수를 통해 랜덤 셔플 보드에 배치하고 리스트에서 삭제 splitIntoGroupsOf 2중 배열을 한 배열로 만드는 함수? 보드의 좌.. 2022. 9. 2.
직각삼각형 - 4153번 직각삼각형인지 아닌지 판별하는 방법은 매우 간단하다. 무한루프를 통해 0, 0, 0 입력 받을 때 break를 걸어주면 된다. while True: l = list(map(int, input().split())) if l[0]+l[1]+l[2] == 0: break else: l.sort() if l[2]**2 == l[0]**2 + l[1]**2: print('right') else: print('wrong') 2022. 8. 31.
직사각형에서 탈출 - 1085번 계산해 볼 수 있는 4개의 거리에 대해 계산한 후 min을 씌워 최소값을 출력한다. l = list(map(int, input().split())) ans = [l[0], l[1], l[2]-l[0], l[3]-l[1]] print(min(ans)) 2022. 8. 30.
수 정렬하기 1, 2 수 정렬하기 1 - 2750번 t=int(input()) arr=[] for i in range(t): arr.append(int(input())) arr.sort() for i in arr: print(i) 수 정렬하기 2 - 2451번 1번 문제와 같은 코드를 사용해도 답은 잘 나오지만 수가 커지면 시간초과에 걸린다. 넘파이의 sort기능을 사용하면 빠르게 정렬가능하지만 기본으로 제공되는 모듈이 아니기 때문에 파일을 찾을 수 없어 런타임 에러가 뜬다. import sys input = sys.stdin.readline n = int(input()) l=[] for i in range(n): num = int(input()) l.append(num) l.sort() for i in l: print(i).. 2022. 8. 29.
1로 만들기 - 1463번 n = int(input()) l = [0] * (n+1) for i in range(2, n+1): l[i] = l[i-1] +1 if i%2 == 0: l[i] = min(l[i], l[i//2] + 1) if i%3 ==0: l[i] = min(l[i], l[i//3] + 1) print(l[n]) 2022. 8. 28.

티스토리툴바