Python/백준 문제 풀이43 [BOJ] 1260번 DFS와 BFS [BOJ] 1260번 DFS와 BFS 문제 기초적인 DFS와 BFS를 알아보는 그래프 문제다. 문제에 들어가기 앞서 DFS와 BFS를 간략히 짚어보자. DFS는 Depth First Search, BFS는 Breadth First Search로 각각 깊이 우선 탐색, 너비 우선 탐색이다. 이 문제를 풀기 위해서는 노드 간의 관계와 시작하는 정점이 필요하다. 또한 DFS와 BFS는 각각 재귀와 데크(Deque)로 푸는 것이 일반적이라고 알려져 있다. 하지만 DFS를 재귀로 푸는 게 쉽긴 하지만 파이썬은 최대 재귀 한도 에러가 존재해서 위험할 수 있다. 그래서 데크로 DFS를 푸는 방법이 존재하기 때문에 이를 사용해서 공부했다. DFS는 깊이를 우선해서 탐색하는데, 말 그대로 노드를 끝까지 파내는 알고리즘이.. 2022. 8. 4. [BOJ] 10757번 큰 수 A+B [BOJ] 10757번 큰 수 A+B 문제 두 개의 큰 수를 더하는 문제다. 하지만 이 문제는 파이썬에게 너무 쉬운 문제다. 그 이유인즉슨, 다른 언어에서는 long long을 이용해도 기껏해야 $ 2^{64} $까지만 나타낼 수 있는 반면 파이썬은 제한이 사실상 없기 때문이다! 물론 파이썬에서 sys 패키지를 import 한 후 sys.maxsize를 치면 최대 정수가 나오긴 하는데 (32비트 환경에서는 $ 2^{31}-1 $, 64비트 환경에서는 $ 2^{63}-1 $이 나온다) 이는 파이썬이 나타낼 수 있는 기본 최대 정수이며, 메모리가 버텨주는 한 이보다 더 큰 수를 써도 무방하다. 그렇기에 파이썬으로 이런 문제를 푸는 것은 너무나도 쉽다. 그냥 A와 B만 입력받아서 더하기만 하면 끝이다. 당장 .. 2022. 7. 28. [BOJ] 7785번 회사에 있는 사람 풀이 [BOJ] 7785번 회사에 있는 사람 문제 최종적으로 회사에 남아있는 사람들을 역순으로 출력하는 문제다. 여기서는 set 이라는 해시(hash)형 자료구조를 사용한다. set 안의 메서드들 중 추가와 삭제는 둘 다 O(1)의 압도적인 성능을 자랑한다. list의 경우엔 각각 O(1)과 O(N)이다. list로도 풀 수는 있지만, 좋은 자료구조를 썼다고 평가받진 못할 것이다. import sys if __name__ == '__main__': n = int(sys.stdin.readline().rstrip()) now_comp = set() for _ in range(n): now_name, status = sys.stdin.readline().rstrip().split() if status == 'en.. 2022. 7. 21. [BOJ] 1004번 어린 왕자 풀이 [BOJ] 1004번 어린 왕자 문제 문제의 그림과 입력의 줄 수만 보면 정신이 아찔해질 수밖에 없다! 그래도 정신을 차리고 천천히 읽어보자. 이 문제의 핵심은 출발점과 도착점, 그리고 행성계 좌표와 반지름만으로 최소 행성계 진입/이탈 횟수를 구해야 한다는 것이다. 절대로 문제 그림의 곡선에 관하여 물어본 것이 없다! 그렇다면 진입과 이탈은 어떻게 구별해야 하는지를 생각해보자. 예를 들어 하나의 행성계만 존재하고, 그것이 출발점 안에만 있다고 하자. 그렇다면 도착점으로 가려면 이탈을 한번 해야 한다! 반대로 하나의 행성계가 도착점에만 있다면, 행성계를 하나 진입해야 한다. 즉, 이탈 횟수는 출발점이 안에 존재하는 행성계 개수, 진입 횟수는 도착점이 안에 존재하는 행성계 개수다! 문제 중에 아래와 같은 말.. 2022. 7. 21. [BOJ] 25206번 너의 평점은 풀이 [BOJ] 25206번 너의 평점은 문제 20줄에 걸쳐서 입력이 들어오고, 우리는 이 입력에 대한 평점을 계산해야 한다. 사족으로, 본인은 공부를 대충 했기에 3.8/4.3이 학부 최종 평점이 되었다. 이 글을 보는 여러분들은 나처럼 게으르게 살지 말고 하루하루를 의미 있게 살았으면 한다. 각설하고, 이 20줄은 과목 / 학점 / 등급 순으로 들어오고, 이걸 반올림 없이 평점을 구하기만 하면 된다. 이런 문제와 같이 출력에 대한 제한이 없는 경우엔 f-string을 이용해서 출력을 할 필요는 없다. 주어진 오차 내로만 출력하면 된다. import sys if __name__ == '__main__': total_credit, total_score = 0, 0 grade = {'A+':4.5, 'A0':4.. 2022. 7. 15. [BOJ] 4344번 평균은 넘겠지 풀이 [BOJ] 4344번 평균은 넘겠지 문제 각 케이스마다 평균이 넘는 사람의 비율을 구하는 문제다. 파이썬의 기본 함수인 round를 쓰면 무조건 틀리니 우리가 직접 반올림을 구현해야 한다! (참고 - [파이썬 알고리즘 #2] 기본 입출력 - 출력) import sys if __name__ == '__main__': C = int(sys.stdin.readline().rstrip()) for _ in range(C): N_score = list(map(int, sys.stdin.readline().rstrip().split())) now_average = sum(N_score[1:]) / N_score[0] over_average_num = 0 for i in range(N_score[0]): if N_s.. 2022. 7. 15. [BOJ] 2739번 구구단 풀이 [BOJ] 2739번 구구단 문제 입력받은 N에 대해 9단까지 출력하는 간단한 문제다. import sys if __name__ == '__main__': N = int(sys.stdin.readline().rstrip()) for i in range(1, 10): print(f'{N} * {i} = {N*i}') 나는 f-string 방법이 매우 편하기에 이렇게 썼다. 여기서 range(1, 10)은 i에 1부터 9까지의 숫자만을 넣는다! 만약 range(10)이라고 하면, 0부터 9까지의 숫자를 쓰고, 10은 쓰지 않는다. 숫자가 줄어드는 방향으로도 range를 쓸 수 있으며, 이 때에는 range(10, 1, -1) 처럼 쓸 수 있다. 이 때에는 1을 쓰지 않는다. 즉, range는 마지막 숫자를 .. 2022. 7. 15. [BOJ] 25083번 새싹 풀이 [BOJ] 25083번 새싹 문제 10171번 고양이, 10172번 개와 같은 이스케이프 문자를 처리하는 문제다. if __name__ == '__main__': print(' ,r\'\"7') print('r`-_ ,\' ,/') print(' \\. \". L_r\'') print(' `~\\/') print(' |') print(' |') 똑같이 작은 따옴표('), 큰 따옴표(") 그리고 백슬래시(\)를 주의하자. 2022. 7. 15. [BOJ] 10172번 개 풀이 [BOJ] 10172번 개 문제 10171번 고양이와 같이 이스케이프 문자를 아는지를 물어보는 문제다. if __name__ == '__main__': print('|\\_/|') print('|q p| /}') print('( 0 )"""\\') print('|"^"` |') print('||_/=\\\\__|') 똑같이 작은 따옴표('), 큰 따옴표(") 그리고 백슬래시(\)를 주의하자. 2022. 7. 15. [BOJ] 10171번 고양이 풀이 [BOJ] 10171번 고양이 문제 이스케이프 문자를 알고 있는지를 확인하는 문제다. if __name__ == '__main__': print('\\ /\\') print(' ) ( \')') print('( / )') print(' \\(__)|') 작은 따옴표('), 큰 따옴표(") 그리고 백슬래시(\)를 주의하자. 2022. 7. 15. 이전 1 2 3 4 5 다음 728x90
