본문 바로가기

Algorithm76

[알고리즘] 정렬 (Sort) 1. 선택 정렬 (Selection Sort) $O(n^{2})$ 배열에서 가장 큰 원소를 찾아 배열의 끝자리에 있는 원소와 자리를 바꿈(swap) 나머지 원소들에 대해서도 반복 package com.company; public class Main { //원본 배열 (정렬x) static int A[] = {3,5,1,2,8,7,6,10,9,4}; static void selection_sort(int list[]) { //가장 큰 값 찾기 + swap 반복 for(int i=list.length-1;i>=0;i--) { int max_index = 0; int max = list[max_index]; //가장 큰 값 찾기 for(int j=0;j list[j+1]) { swap(list, j, j+1).. 2020. 9. 17.
[알고리즘] 위상 정렬 (Topological Sorting) 위상 정렬 (Topological Sorting) 사이클이 없는 유향 그래프의 모든 정점을 정렬하는 알고리즘 간선 (i, j) 가 존재하면 정점 i는 반드시 정점 j보다 앞에 위치해야한다. → 사이클이 있으면 이 성질을 만족할 수 없다. 시간 복잡도 : O(V+E) 알고리즘 각 노드마다의 진입 간선을 보관하는 배열 in_edge 생성 맨 처음, 진입 간선이 없는 노드들을 queue에 추가 queue가 빌 때까지 반복문 실행 현재 노드 now 출력 now에 연결된 진출 노드들 탐색 진출 노드 next의 진입 간선 줄이기 next의 진입 간선이 0이면 next 앞에 있는 노드들이 모두 출력되었다는 의미이므로 next를 queue에 추가 import java.util.*; public class Main { .. 2020. 9. 17.
[알고리즘] 로봇 청소기 (백준 14503번) 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 시뮬레이션 문제다. 처음에 '되돌아 온다' 는 문장만 보고 DFS로 백트랙킹 하는 건가 했었는데 아닌듯 해서 그냥 BFS로 풀었다. Solution 사실 완전 탐색이랑은 관련이 없다. 조건에 맞는 한 방향으로만 계속 나아가기 때문이다. 다만 문제에서 헷갈렸던 부분이 있었다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 .. 2020. 9. 17.
[알고리즘] 아기상어 (백준 16236번) 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 예전에 푼 적이 있는 문제임에도 생각보다 시간이 더 오래 걸렸다. 그것도 예전에 풀었던 솔루션보다 시간이 더 길게 나오더라..;; BFS + 시뮬레이션 방식의 문제이다. N의 범위가 작아서 시간초과 걱정없이 풀 수 있는 문제이다. Solution fish_count : map에 있는 총 물고기의 수. queue에 맨 처음 상어 위치를 넣는다. fish_count가 1마리 이상 있으면 계속 반복문 진행 bfs 탐색 시작 현재 위치에서 최단 거리에 있는 먹.. 2020. 9. 17.

티스토리툴바