CS/Algorithm18 [ 백준 - 1043 ] 거짓말 - java 난이도 : G4Link : https://www.acmicpc.net/problem/1043Tag : 그래프, BFS 문제 탐색하기 - 지민이는 각 파티에 모두 참석해서 진실, 혹은 거짓된 이야기를 합니다.- 지민이는 거짓말 쟁이가 되면 안됩니다. 즉, 이미 진실된 이야기를 한 사람들에게는 항상 진실된 이야기를, 거짓된 이야기를 한사람들에게는 항상 거짓된 이야기를 전달해야합니다. - 이미 이야기를 들었었던 사람이 있다면 그사람이 알고있는대로 진실 or 거짓을 이야기해야합니다. 즉 해당 파티에 참여한 모든 사람들은 진실 혹은 거짓된 정보를 통일되게 알아야합니다.문제는, 그 후에 서로다른 이야기를 들은 사람들이 파티에 참석하면 거짓말 쟁이가 되어버립니다. 즉 처음부터 진실된 이야기를 할 사람들, 거짓된 이.. 2025. 6. 6. [ 백준 - 11403 ] 경로 찾기 난이도 : S1Link : https://www.acmicpc.net/problem/11403Tag : 그래프, BFS 문제 탐색하기 - 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점에서 i에서 j로 가는 경로가 존재하는지 여부를 파악하는 문제입니다. 시도 1 ( 성공😲)떠오른 문제 해결 방법각 정점을 기준으로 bfs를 진행한뒤, 방문한 노드들은 경로가 존재하므로, 이를 바탕으로 출력하면 해결할 수 있다고 생각했습니다.시간복잡도⏰bfs시간복잡도 O( V + E)에 각 정점마다 이를 실행해야하므로 V * O( V + E).노드의 총 개수 N (1 ≤ N ≤ 100).간선의 최대 개수는 자신을 제외한 모든 노드에 간선이 있을 경우, 즉 99*99 = 9801 100*9801 = 980,100 으.. 2025. 5. 29. [ 백준 - 11724 ] 연결 요소의 개수 with 그래프 그래프 구현 방법 인접 행렬인접 리스트공간 복잡도O( V^2 )O( V+E )정점 u, v가 연결되어있는지 확인하는 시간 복잡도O( 1 )O( min(deg(u), deg(v) )정점 v와 연결된 모든 정점을 확인하는 시간 복잡도O(V)O( deg(V) )효율적인 상황두 점의 연결여부를 자주 확인할 때E가 V^2에 가까울 때특정 정점에 연결된 모든 정점을 자주 확인할 때E가 V^2보다 훨씬 작을 때 백준 문제 : 11724번. 연결 요소의 개수 난이도 : S2Link : https://www.acmicpc.net/problem/11724Tag : Graph 문제 탐색하기 - 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하여라시도 1 ( 성공 😲)떠오른 문제 해결 방법이번 문제에서는 연결리스.. 2025. 5. 12. [ 백준 - 2579 ] 계단 오르기 난이도 : S3Link : https://www.acmicpc.net/problem/2579Tag : DP 문제 탐색하기 - 마지막 계단까지 도착했을때 얻을 수 있는 최댓값을 구하여야한다.- 계단은 한번에 한계단, 두계단씩 오를 수 있다.- 세개의 계단은 모두 밟아서는 안된다.시도 1 ( 실패 😓)떠오른 문제 해결 방법먼저 테이블은 D[i] = 해당 계단까지 도착했을 때의 최댓값 으로 정의하였습니다.식은 k = stairs[i-1], stairs[i-2] 중 더 큰값인 계단의 인덱스. D[i] = D[k] + stairs[i] 입니다. 이유는 i번째의 계단을 오르기 위해서는 연속해서 3계단을 오를 수 없기 때문에 i-1, i-1계단중 하나를 선택해야합니다. 두계단을 모두 선택한다면 i번째 계단을 오를.. 2025. 5. 10. 이전 1 2 3 4 5 다음
