https://www.acmicpc.net/problem/1920

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

A 배열을 정렬한 후 이분 탐색으로 값이 존재하는지 검사한다. 

if __name__=="__main__":
    n=int(input())
    a=list(map(int, input().split()))
    a.sort()
    m=int(input())
    b=list(map(int, input().split()))
    for i in range(m):
        lt=0
        rt=n-1
        while lt<=rt:
            mid=(lt+rt)//2
            if a[mid]==b[i]:
                print("1")
                break
            elif a[mid]>b[i]:
                rt=mid-1
            else:
                lt=mid+1
        else:
            print("0")

https://www.acmicpc.net/problem/2869

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

def check(day):
	# day일이 지난 후 도착하는지 체크
    if a*day-b*(day-1)>=v:
        return True
    else:
        return False

if __name__=="__main__":
    a, b, v=map(int, input().split())
    lt=0
    rt=v
    ans=0
    while lt<=rt:
        mid=(lt+rt)//2
        # 도착한다면 날짜를 더 줄여서 검색
        if check(mid)==True:
            ans=mid
            rt=mid-1
        # 도착하지 않는다면 날짜를 더 늘려서 검색
        else:
            lt=mid+1
    print(ans)

https://www.acmicpc.net/problem/10451

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해

로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 20001;

int N, M; // N: 정점의 개수, M: 간선
vector<int> adj[MAX]; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:방문)

int ans = 0;

void dfs(int node) {
	if(visited[node] == 1) ans++;

	visited[node] = 1;

	for(int i = 0; i < adj[node].size(); i++) {
		int next = adj[node][i];
		if(visited[next] == 0) dfs(next);
	}
}

int main(void) {
	int k;
	cin>>k;

	for(int i = 0; i < k; i++) {
		cin>>N;

		for(int j = 1; j <= N; j++) { // 인접행렬 (j, M) (M, j)
			cin>>M;
			adj[j].push_back(M);
			adj[M].push_back(j);
		} 

		for(int j = 1; j <= N; j++)
			if(visited[j] == 0) {
				visited[j] = 1;
				dfs(j);
			}


		cout<<ans<<'\n';

		// 인접 행렬, 방문 노드, ans 초기화
		for(int j = 0; j <= N; j++) {
			adj[j].clear();
			visited[j] = 0;
			ans = 0;
		}
	}
}

https://www.acmicpc.net/problem/1707

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 20001;

int N, M; // N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점
vector<int> adj[MAX]; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:r그룹1, -1:그룹2)

void dfs(int node, int set) {
	visited[node] = set;

	for(int i = 0; i < adj[node].size(); i++) {
		int next = adj[node][i];
		if(visited[next] == 0) dfs(next, -set);
	}
}

bool bipartite() {
	for(int i = 0; i < N; i++)
		for(int j = 0; j < adj[i].size(); j++) {
			int next = adj[i][j];
			// 정점 i와 j가 연결되어 있고 둘의 그룹이 같을 경우 이분그래프가 아님
			if(visited[i] == visited[next]) return false;
		}

	return true;
}

int main(void) {
	int k;
	cin>>k;

	for(int i = 0; i < k; i++) {
		cin>>N>>M;

		int x, y; // 인접 행렬 좌표
		for(int j = 0; j < M; j++) {
			cin>>x>>y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		} 

		for(int j = 0; j <= N; j++)
			if(visited[j] == 0) {
				visited[j] = 1;
				dfs(j, 1);
			}


		if(bipartite()) cout<<"YES\n";
		else cout<<"NO\n";

		// 인접 행렬, 방문 노드 초기화
		for(int j = 0; j <= N; j++) {
			adj[j].clear();
			visited[j] = 0;
		}
	}
}