본문 바로가기

Algorithm/BOJ54

[BOJ] 1058. 친구 (python) ✏️ 문제 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오. A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다. [입력] 첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다. [출력] 첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다. 🤯 풀이 방법 .. 2023. 4. 10.
[BOJ] 13023. ABCDE (python / java) ✏️ 문제 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 🤖 알고리즘 #그래프 #백트래킹 🤯 풀이 방법 친구 관계를 가진 A, B, C, D, E가 있냐는 말인데, 그냥 그래프를 순회해서 다섯 단계까지 갈 수 있냐는 뜻이다. 자바로 생각할 때는 금방 풀어서 구현했는데 몇 주 뒤에 파이썬으로 하려니 시간초과 나고 난리도 아니었다. 일단 그래프 관계를 리스트로 만들고, 함수를 만들어서 .. 2023. 4. 9.
[BOJ] 11724. 연결 요소의 개수 (python / java) 백준 11724. 연결 요소의 개수 (파이썬 / 자바) DFS를 이용해서 하나의 그래프를 끝까지 탐색하고, 끝난 후에도 아직 방문하지 못한 새로운 시작점이 있다면 그래프의 개수를 추가한 후 그 그래프도 끝까지 탐색해 방문 표시를 한다. 파이썬 setrecursionlimit 적용하지 않을 경우 recursionError 발생 # [BOJ] 11724. 연결 요소의 개수 import sys input = sys.stdin.readline sys.setrecursionlimit(10000000)# 추가 안해주면 틀림 def DFS(v): visited[v] = 1 for n in L[v]: if visited[n] == False: DFS(n) N, M = map(int, input().split()) L .. 2023. 3. 21.
[BOJ] 11725. 트리의 부모 찾기 (python / java) 백준 11725. 트리의 부모 찾기 (파이썬 / 자바) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 파이썬 양방향 모두 저장한 후 접근 아직 탐색하지 않은 값이 있다면 그 인덱스의 자식에 해당 import sys sys.setrecursionlimit(10**6)# 안하면 recursionError input = sys.stdin.readline def search(v): visited[v] = True for n in tree[v]: if visited[n] == False:# 아직 탐색하지 않은 값이 있다면 자식에 해당 ans[n] = v search(n) retur.. 2023. 3. 20.
[BOJ] 11478. 서로 다른 부분 문자열의 개수 (python) 백준 11478. 서로 다른 부분 문자열의 개수 (파이썬) 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net # [BOJ] S3> 11478. 서로 다른 부분 문자열의 개수 import sys from itertools import combinations input = sys.stdin.readline s = input() idx = [x for x in range(len(s))] comb = list(combinations(idx, 2)) ans = set() for c in comb: a = s[c[0]:c[1]] ans.add(a) print(len(ans)) ans에 저장하.. 2023. 3. 20.
[BOJ] 9742. 순열 (python / java) 백준 9742. 순열 (파이썬 / 자바) 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 파이썬 EOF 어떻게하는지 아주 까먹었었다 입력이 정렬되어 주어져서 순열 구현만 하고 카운트만 제대로 해 주면 됨 def perm(r): global cnt if r == len(a): cnt += 1 if cnt == int(b): print(''.join(selected)) return for i in range(len(a)): if visited[i]: continue selected[r] = a[i] visited[i].. 2023. 3. 19.
728x90

티스토리툴바