알고리즘74

• 

  BJ S2 1260 DFS와 BFS - Java [문제링크]https://www.acmicpc.net/problem/1260 [문제]그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.[입력]첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.[출력]첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 .. 알고리즘/DFS_BFS 2025. 1. 12.

• 

  스택(Stack)과 큐(Queue) 스택(Stack) - 스택은 데이터를 한 열로 저장합니다. 하지만 후입선출(Last In First Out) 구조로 나중에 들어간 것이 먼저 나오는 구조입니다.- 링 던지기 게임이 스택의 예시입니다. - 데이터의 추가는 push라고 불리며, 스택 내부에 데이터가 쌓입니다.- 데이터의 삭제는 pop이라 불리며, 스택에 가장 마지막에 들어갔던 데이터가 나오게 됩니다. ex) A만 들어가 있는 스택이 있다. 스택에 B, C를 넣어보자.1) 스택에 B를 push한다. (A-B)2) 스택에 C를 push한다. (A-B-C)3) 스택에서 pop을 한다. (A-B)4) 스택에서 pop을 한다. (A) 예시에서 처럼 가장 나중에 들어간 데이터가 가장 먼저 나오게 되는 구조가 바로 스택이다.스택이 가장 많이 활용되는 부.. CS 지식/자료구조_알고리즘 2025. 1. 8.

• 

  List(리스트)와 Array(배열) List(리스트)- 리스트는 데이터를 일직선으로 줄줄이 정렬한 데이터 구조입니다.장점 : 데이터의 추가, 삭제 쉬움단점 : 데이터 조회 느림 - 데이터들은 각각 포인터를 가지고, 이 포인터는 각각 데이터의 다음 데이터의 메모리 주소를 가리킵니다. - 리스트는 포인터를 이용하므로 메모리상에서 연결된 위치에 있을 필요가 없습니다. 따라서 분산되어 배치됩니다. - 데이터 추가 방법A와 B 데이터 사이에 C라는 데이터를 추가할 때, A의 포인터가 C의 메모리 주소를 가리키게 하고,C의 포인터가 B의 메모리 주소를 가리키게 하면 끝이다. - 데이터 삭제 방법A와 B와 C가 연결되어 있을 때, B를 제거하고자 한다.A의 포인터를 C의 메모리주소를 가리키면 해결된다. 따라서 List에서의 시간복잡도는 다음과 같다.데.. CS 지식/자료구조_알고리즘 2025. 1. 7.

• BJ G4 20040 사이클게임 - Java [문제링크]https://www.acmicpc.net/problem/20040[문제]사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다. C에 속한 임의의 선분의 한.. 알고리즘/유니온-파인드 2024. 10. 13.

• BJ S1 15651 N과M(3) - Java [문제링크]https://www.acmicpc.net/problem/15651[문제]자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.[입력]첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)[출력]한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.[예제 입력 1]3 1[예제 출력 1]123[예제 입력 2]4 2[예제 출력 2]1 11 21 31 42 12 22 32 43 13 23 33 44 14 24 34 4[설.. 알고리즘/백트래킹 2024. 10. 9.

• BJ G4 1043 거짓말 - Java [문제링크]https://www.acmicpc.net/problem/1043[문제]지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다... 알고리즘/유니온-파인드 2024. 10. 9.

• BJ S1 15650 N과M(2) - Java [문제링크]https://www.acmicpc.net/problem/15650[문제]자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.[입력]첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)[출력]한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.[예제 입력 1]3 1[예제 출력 1]123 [예제 입력 2]4 2[예제 출력 2]1 21 31 42 32 43 4[예제 입력 3]4 4[예제 출력 3]1 2 .. 알고리즘/백트래킹 2024. 10. 9.

• 

  BJ S3 2606 바이러스 -Java [문제링크]https://www.acmicpc.net/problem/2606[문제]신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보.. 알고리즘/DFS_BFS 2024. 10. 9.

• BJ S2 11724 연결요소의개수 - Java [문제링크]https://www.acmicpc.net/problem/11724[문제]방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.[입력]첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.[출력]첫째 줄에 연결 요소의 개수를 출력한다.[예제 입력 1]6 51 22 55 13 44 6[예제 출력 1]2 [예제 입력 2]6 81 22 55 13 44 65 42 42 3[예제 출력 2]1 [설명]방향없는 그래프라서 DFS를 이용하여 풀었.. 알고리즘/DFS_BFS 2024. 10. 9.

• 

  BJ S3 9461 파도반수열 - Java [문제링크]https://www.acmicpc.net/problem/9461[문제]오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.[입력]첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)[출력]각 테스트.. 알고리즘/DP 2024. 10. 9.

• BJ S1 15649 N과M(1) - Java [문제링크]https://www.acmicpc.net/problem/15649[문제]자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열[입력]첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)[출력]한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.[예제 입력 1]3 1[예제 출력 1]123 [예제 입력 1]4 2[예제 출력 1]1 21 31 42 12 32 43 13 23 44 14 24 3 [설명]이 문제는 백트래킹 문제이고, 처음엔.. 알고리즘/백트래킹 2024. 10. 9.

• BJ G5 1717 집합의 표현 - Java [문제링크]https://www.acmicpc.net/problem/1717[문제]초기에 n+1개의 집합 {0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.[입력]첫째 줄에 n, m이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.[출력]1로 시작하는.. 알고리즘/유니온-파인드 2024. 10. 9.