https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 유형 그래프 탐색 (DFS(깊이 우선 탐색), BFS(너비 우선 탐색)) 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점..
Koala - 13기/코딩테스트 준비 스터디
https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가..
문제 해설 처음에 모든 경우의 수를 검사하는 코드를 작성했는데, 시간초과가 난 문제이다. 모든 경우의 수를 검사하지 말고 각 의상의 종류에 아무것도 입지 않을 경우 1을 더하고, 각 의상의 종류 가짓수를 곱해주고, 아무것도 입지 않을 경우 1을 빼준다. 코드 import sys input = sys.stdin.readline def main(): for _ in range(int(input().strip())): dic = {} ans = 1 for _ in range(int(input().strip())): _, t = map(str, input().split()) dic[t] = dic[t] + 1 if t in dic else 2 for i in dic: ans *= dic[i] print(ans ..
문제 https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net Algorithm 문제에서 상근이의 친구와 친구의 친구를 초대한다고 하였으므로 bfs나 dfs를 상근이를 기준으로 1번한 후에 상근이와 연결된 간선만 탐색하면 되는 문제이다. 문제에서 제시된 입력을 토대로 graph배열을 만들고, 1을 기준으로하여 탐색후 invited배열에 적용한다. 그 후에 1과 연결된 정점을 탐사한 후에 탐색을 종료한다. 이때, 1도 탐사를 하여 1이 된 ..
고등학교때 배웠던 원의 방정식을 활용하여 문제를 해결하였다. 두 원의 위치와 반지름이 주어졌을 때, 두 원이 서로 교차하는지, 접하는지, 겹치는지, 아니면 아무 관계도 없는지를 판별하는 프로그램을 구현하면 된다. 테스트 케이스의 수를 입력받는다. 각 테스트 케이스마다 두 원의 중심 좌표와 반지름을 입력받는다. 두 원의 중심 사이의 거리를 계산한다. 두 원의 반지름의 차이를 계산한다. 두 원의 관계를 판별하고 결과를 출력한다. 결과값(res)은 다음과 같이 설정한다. -1: 두 원이 동심원이고 반지름이 같은 경우 0: 두 원이 아무 관계도 없는 경우 1: 두 원이 서로 교차하거나 한 원이 다른 원을 포함하는 경우 2: 두 원이 서로 접하는 경우 즉, 두 원의 중심 사이의 거리를 계산한 뒤, 각 원의 반지름..
https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; struct Student { string nam; int kor; int eng; in..
11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 문제유형 *깊이 우선 탐색 *너비 우선 탐색 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입출력 예제 (입력 1) 6 5 1 2 2 5 5 1 3 4 4 6 (출력 1) 2 (입력 2) 6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3 (출력 2)..
우선 -1이 나오는 경우는 a 배열을 모두 더했을 경우 = sum(a) 이 합이 0이 되지 않을 경우입니다. 이 외의 경우에는, 트리 구조이기 때문에 트리의 두 정점들을 서로 빼거나 더함으로써 반드시 0을 만들 수 있습니다. 그러면 가장 '최소가 되는' 횟수를 어떻게 찾을 수 있을까요? 이 횟수는 사실 아무런 상관이 없고 그냥 어떤 한 노드를 부모 노드로 정한 후 아래 노드까지 뻗어가서 아래 노드부터 하나씩 0으로 만들어주면 된다. 따라서 아래의 조건을 충족하기 위한 DFS를 구현하였다. 끝에 도달하면 ? -> 자기를 0으로 만들기 위해 부모에게 자기를 더해야 함. => Return 문 활용 그럼 각각의 노드는 무엇을 반환해야 해? -> 자신의 값을 반환 정답은 그 반환하는 전체 횟수가 중요함 -> ab..
문제 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Algorithm 자연수 x를 최대 힙을 사용해 저장한다. 파이썬에서는 최소 힙만 지원하므로 -1을 곱해서 저장하고 출력할 때는 다시 -1를 곱해서 출력한다. Code import sys from heapq import heappush, heappop input = sys.stdin.readline N = int(input()) h = [] for _ in range(..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 요약 에디터를 구현한다. 입력에 따라 커서를 왼쪽 오른쪽으로 움직일 수도있고, 커서의 왼쪽에 문자를 추가하거나 커서의 왼쪽의 문자를 제거하는 기능을 구현한다. 문제 해결 처음에는 cursor의 위치를 변수에 담아 기억해놓았다. 현재 입력된 문자열을 stack에 저장해놓고, 입력과 삭제가 있을 때, cursor의 위치까지 pop을 한 후, 처리를 한뒤 다식 돌려놓는 식으로 구현하였다. 하지만 이..
https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; LL arr[100001]; int main() { cin.tie(NULL); int n = 0; int m = 0; cin >> n >> m; LL..
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 유형 스택 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 ..
