백준 14592 - 연구소https://www.acmicpc.net/problem/14592 문제풀이해당 문제에서는 3가지 입력 N, M, 지도 모양이 주어진다. N : 세로 크기 M : 가로 크기 지도 정보 지도 내 상태는 3가지 상태가 존재한다. 0 : 빈칸 1 : 벽 2 : 바이러스 알고리즘 실행계획은 다음과 같이 진행한다. 벽을 세운다. 바이러스 확산 시킨다. 바이러스 영역을 확인한다.
백준 1158 - 요세푸스 문제https://www.acmicpc.net/problem/1158 문제 풀이해당 문제에서는 두가지 입력 N, K가 주어진다. N : 사람 수 K : 원에서 사람이 제거되는 간격 N, K의 최대 5000 이므로, 최대 O(N^2)의 시간복잡도내에서 문제를 해결해야 한다. 전체 소스 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arguments = br.readLine().split(" "); int N, K; N = Integer.parseInt(arguments[0]); K = Integer.parseInt(arguments[1]); List<Integer> list = new ArrayList<>(); for (int i = 0; i < N; i++) { list.add(i + 1); } int index = 0; StringBuilder sb = new StringBuilder(); sb.append("<"); // 사람을 간격에 맞게 하나씩 제거해준다. while (list.size() > 1) { index += K - 1; index %= list.size(); int removedValue = list.remove(index); sb.append(Integer.toString(removedValue)); sb.append(", "); } // 마지막 숫자를 제거한다. index += K - 1; index %= list.size(); int removedValue = list.remove(index); sb.append(Integer.toString(removedValue)); sb.append(">"); System.out.println(sb.toString()); br.close(); }}
https://www.acmicpc.net/problem/1181 백준 3015 단어 정렬문제 풀이자료구조 Set을 사용하기 좋은 문제이다. 다만 Set에서 사용하는 정렬방식을 조건에 맞게 변형해줄 필요가 있다. 소스코드#include <bits/stdc++.h>using namespace std;set<pair<int, string>> s;int n;int main(void) { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); cin >> n; while (n--) { string word; cin >> word; s.insert({word.length(), word}); } for (auto iter = s.begin(); iter != s.end(); iter++) { cout << iter->second << '\n'; } return 0;} 자바 소스 코드Comparator 인터페이스를 이용해 set의 정렬기준을 사용자가 정의한 정렬기준으로 변경할 수 있다. Comparator 인터페이스를 사용하게 되면 compare 메소드를 오버라이딩해 원하는 정렬 기준을 적용할 수 있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Comparator;import java.util.Set;import java.util.TreeSet;public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int count = Integer.parseInt(br.readLine()); Set<String> words = new TreeSet<String>(new Comparator<String>() { @Override public int compare(String o1, String o2) { if (o1.length() < o2.length()) { return -1; } else if (o1.length() > o2.length()) { return 1; } else { return o1.compareTo(o2); } } }); for (int countIdx = 0; countIdx < count; countIdx++) { String word = br.readLine(); words.add(word); } words.stream().forEach(x -> System.out.println(x)); }}
링크https://www.acmicpc.net/problem/1260 문제 풀이그래프탐색에 있어 가장 기본적인 DFS, BFS를 사용해볼 수 있는 유형이다. 좌표 자체가 존재하지 않아 1차원적인 check방식을 통해 탐색해 나간다. cpp 코드#include <bits/stdc++.h>using namespace std;// 점점의 개수 : N, 간산의 개수 M, 탐색을 시작할 정점의 번호 Vint N, M, V;bool check_dfs[1010];bool check_bfs[1010];int graph[1010][1010];void bfs(int start) { queue<int> q; q.push(start); check_bfs[start] = true; while (!q.empty()) { int cnt = q.front(); q.pop(); cout << cnt << ' '; for (int i = 1; i <= N; i++) { if (graph[cnt][i] == 1 && check_bfs[i] == false) { check_bfs[i] = true; q.push(i); } } }}void dfs(int depth, int cnt) { check_dfs[cnt] = true; if (N <= depth) { return; } cout << cnt << ' '; for (int i = 1; i <= N; i++) { if (graph[cnt][i] == 1 && check_dfs[i] == false) { dfs(depth + 1, i); } }}int main(void) { cin >> N >> M >> V; for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; graph[a][b] = 1; graph[b][a] = 1; } dfs(0, V); cout << '\n'; bfs(V); return 0;} java 코드import java.io.IOException;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Main { static int n, m, v; static int map[][]; static boolean bfs_check[]; static boolean dfs_check[]; public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); v = sc.nextInt(); map = new int[n + 1][n + 1]; for (int i = 0; i < m; i++) { int from, to; from = sc.nextInt(); to = sc.nextInt(); map[from][to] = 1; map[to][from] = 1; } bfs_check = new boolean[n + 1]; dfs_check = new boolean[n + 1]; dfs(v); System.out.println(); bfs(v); sc.close(); } static void dfs(int node) { System.out.print(Integer.toString(node) + ' '); dfs_check[node] = true; for (int i = 1; i <= n; i++) { if (map[node][i] == 1 && dfs_check[i] == false) { dfs(i); } } } static void bfs(int start) { Queue<Integer> q = new LinkedList<Integer>(); q.offer(start); bfs_check[start] = true; System.out.print(Integer.toString(start) + ' '); while (!q.isEmpty()) { int cnt = q.remove(); for (int i = 1; i <= n; i++) { if (map[cnt][i] == 1 && bfs_check[i] == false) { bfs_check[i] = true; q.offer(i); System.out.print(Integer.toString(i) + ' '); } } } }} python 코드
링크https://www.acmicpc.net/problem/1012 채점 현황 문제 풀이전형적인 색칠하기 유형히다.이 문제는 testcase문제이기 때문에 각 case마다 데이터를 초기화 해줘야 한다. field를 탐색하면서 배추가 심어져 있는 위치를 찾는다. 배추가 심어져 있는 곳을 찾았다면 이전에 탐색을 했는지 확인한다. 탐색한 적이 없다면 다음으로 넘어간다. 탐색한 적이 있다면 1로 돌아간다. 배추가 심어져 있는 주변에 다른 배추들이 있는지 탐색한다. 탐색횟수가 배추 흰 지렁이의 갯수가 된다. BFS를 이용한 코드