TY_IT💻

https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net import sys input = sys.stdin.readline x, y = map(int, input().split()) z = int(100 * y / x) if z >= 99: print(-1) else: ans = 0 start = 0 end = 1000000000 while(start

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net import sys input = sys.stdin.readline n = map(int, input()) a = list(map(int, input().split())) pool = {} for k in a: pool[k] = 1 print(pool) m = map(int, input()) b = list(map(int, input().split(..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Dnamic Programming(동적계획법)은 메모이제이션 통해 중복계산값을 저장해 효율을 높여준다. 1) Python 이용 # DP --> 메모이제이션: 중복계산값을 줄여 효율 높여줌 n = int(input()) d = [0] * (n + 1) # d에 계산값 저장 # d[0] = 0, d[1] = 0 for i in range(2, n + 1): d[i] = d[i - 1] + 1 if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) if i % 2 == 0: d[i] = ..

https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 처음에 그래프를 만들어서 재귀를 했는데 시간 제한으로 실패! 실패한 코드 import sys sys.setrecursionlimit(1000000) input = sys.stdin.readline t = int(input()) def dfs(v): visited[v] = 1 for i in range(n + 1): if vi..

연결 요소의 개수 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (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 5 1 2 2 5 5 1 3 4 4 6 예제 출력 1 2 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000,..

이분그래프 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프 이분 그래프인지 확인하는 방법 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)을 이용 → 서로 인접한 정점이 같은 색이면 이분 그래프 X 1. BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다. 2. 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다. 3. 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다. 4. BFS의 경우 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아니다. 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다. ※ 이..

배열(Array) 순차 기억장소에 할당된 유한 개수의 동일 자료형 데이터 원소들 배열명, V: 배열 전체를 일컫는 기호 배열 크기, N: 원소를 저장하는 셀들의 개수 배열 첨자, i: 셀의 순위 = 상대적 위치 배열의 메모리 할당 컴파일 시 배열의 셀들은 베이스(base)라고 불리는 배열의 첫째 셀 위치부터 시작해 차례로 할당됨 각 셀은 베이스로부터 오프셋(offset)만큼 떨어짐 행 우선 순서 = 저차원 우선 순서 2차원 배열 테이블이라고도 불림 1차원과 2차원은 각각 행, 열로도 불림 연결리스트(linked list) 동적 메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터 원소 노드들 연결리스트 명: L, 연결리스트의 시작 위치, 첫 노드의 주소 연결리스트 크기: n, 연결리스트 내 노드의 수..

복습 그래프: 노드와 노드 사이에 연결된 간선 정보를 가지고 있는 자료구조 서로 다른 개체가 연결되어 있다 --> 가장 먼저 그래프 알고리즘 떠올려야함. [그래프와 트리 자료구조 비교] 그래프 트리 방향성 방향 그래프 or 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노트 X 루트 노드 존재 노드 간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 그래프의 구현 방법 1. 인접 행렬(Adjacency Matrix): 2차원 배열 사용 2. 인접 리스트(Adjacency List): 리스트 사용 노드의 개수가 V, 간선의 개수가 E인 경우 인접 행렬과 인접리스트 구현 비교 인접행렬 이용 인접리스트 이용 간선 정보 저장 O(V^2)..