판교의 메타몽

문제 링크 : https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 풀이는 다음과 같다. 1. 먼저 필요한 변수들을 선언해주고 값을 저장해준다. int n,m,t,p,pn,ans=0; bool ch[51]; // 진실을 아는지 여부 bool res[51]; // 과장된 이야기를 할 수 있는 파티 여부 cin >> n >> m; vector party[m+1]; queue q; memset(ch,false,sizeof(ch)); // 배열 초기화 memse..

문제 링크 : www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 풀이는 다음과 같다. 1. 먼저 다음과 같은 배열들을 생성한다. (1) 2차원 bool문 배열 (입접행렬 : 서로 연결이 되어있는지 아닌지를 판단) (2) 2차원 int형 벡터 (입접리스트 : 연결된 *노드들을 저장) (3) pair int형 벡터 (간선리스트 : 연결된 *간선들을 저장) *노드(N) : 그래프의 정점 *간선(E) : 그래프의 간선 (선분, 연결선) 2. n과 m을 입력받고 m의 크기만큼 시작지점과 끝지점을 입력 받는다. 친구관계로 저장받지만, 편의상 나는 시작지점과 끝지점이라고 ..

용어 정리 정점 : Node, Vertex 간선 : Edge G = (V,E) 1. 인접행렬 정점의 개수를 V라고 했을 때 V*V 크기의 이차원 배열을 이용 A[i][j] = w (i->j의 간선이 있을때, 그 가중치), 0(없을때) 알고리즘 테스트에서 거의 사용되지 않는데, 비효율적이어서 그렇다. 예를들어 간선이 정점이 10만개이고 간선이 100만개 이면 행렬은 100억개의 공간을 가지게 되는데, 쓰지 않을 공간까지 자리를 할당해주니 비효율적일 수 밖에 없다. 정 사용할거면 연결이 되어 있느냐 없느냐 정도만 활용하기 위해 bool문으로 선언할 것을 권장한다. 2. 인접 리스트 리스트를 이용해서 구현 A[i] = i와 연결된 정점을 리스트로 포함하고 있음 효율성 : O(V의 차수). 정점 V에 연결된 정..