조던을좋아하는코린이

- 선택 정렬 - 정렬을 배우기 전 간단하게 프로그래밍 언어에서 몇개의 정렬 알고리즘 종류가 있는지 살펴보았다 다음과 같은 정렬의 종류가 있다는 것을 위키피디아를 통해서 알 수 있었다. 아직 버블,선택,삽입,병합,힙,퀵 이정도의 정렬에 대해서 배운적은 있으나 그 이하의 나머지 정렬은 처음들어본다. 앞으로 알고리즘 공부를 통해서 하나씩 배워보려고 한다. 먼저, 정렬의 가장 기본적인 선택정렬에대해서 정리를 하겠다. - 선택 정렬이란 - 주어진 배열에서 최소값을 찾고 그 값을 배열의 맨 앞에 위치한 값과 바꿔주는 것이다. " 1 10 5 8 7 6 4 3 2 9 " 을 오름차순으로 구현을 한다면 1부터 10까지 10개의 수에서 가장 작은 숫자를 먼저 찾고 해당 위치의 인덱스를 기억한 이후에 맨 앞의 값과 자리..

- 문제 - - 입력 / 출력 - - 예제 입력 - - 풀이 (1) - 문제를 처음 보자마자 생각한 방법은 그래프를 이용하여 탐색을 진행하면 된다고 생각을 하였다. 처음에는 모든 방문해야하는 도시들을 방문할 때 까지 반복하여 문제를 해결하려고하였다. --- 생각을 잘못함. 결국 다시 문제를 풀었고 처음 방문해야하는 도시를 dfs에 입력으로 넣어주었다. 이 두가지를 구현을 하면 쉽게 문제를 해결할 수 있다. 1) dfs로 그래프를 탐색 -> 방문한 노드는 방문 처리 2) 방문처리한 위치와 방문해야할 목적지를 비교 - 전체 코드 - - 풀이 (2) - 다른 사람의 풀이를 찾다보니 분리 집합 알고리즘을 활용하여서도 이 문제를 더 쉽게 풀수있다는것을 알게되었다. 분리집합 알고리즘에 대해서 처음 들었기에 먼저 알..

분리 집합은 서로소 집합이라고도 부른다. 분리 집합의 특징으로 - 전체 집합 U에 대해, U의 분리집합은 A, B는 다음을 만족한다. 1) A,B 는 U의 부분집합이다. 2) 집합 A,B는 같은 원소를 가지지 않는다. 3) A,B의 합집합이 곧 전체집합(U)이다. ( A,B에 속하지 않는 원소는 U에도 속하지 않는다 ) - 그림 (1)과 같은 경우를 제외한 나머지 (2) (3) 번의 경우는 될 수없다. - 집합이 3개 이상의 경우에도 똑같이 적용된다. - Union Find 알고리즘 - 분리 집합을 구현하는 알고리즘으로써, 트리의 형태로 표현이 된다. 배열을 이용하여 보통 구현이 된다. 다음과 같은 집합들이 존재할 때 연결정보를 입력할 때 값이 작은값을 기준으로 갱신을 한다. 따라서 그림 은 ..

문제) 먼저 이문제를 보자마자 생각이 든것은 1) BFS를 이용하고 2) 먹을 수 있는 생선을 찾으면 바로 생선의 크기 증가를 위한 cnt +1증가 시키고 3) cnt == fish_size(생선의 현재 크기) 같으면 생성 크기 증가시키고 cnt =0으로 셋팅 4) 방문한 모든 자리는 다시 0처리 먹은 생선 0으로 처리하기 이렇게 생각하였다. 방향을 무시하고 했던것은 애초에 방향을 움직일 때 상 좌 우 하 순서로 움직인데만 주어진 조건을 만족하는줄 알았다. 하지만 이 예제에서 답이 잘못나오게 되었다. 여기서 문제는 상좌우하 순서로는 조건을 만족하지 못한다는것이였다. 가장 멍청한건.. 내 생각이 맞다고 생각하고 컴퓨터의 답을 무시한것.. 그렇게 시간을 버리고 같은 방법으로 코드를 다시 짜기 시작했다.. 그..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 백준 문제 연구소 3을 풀었다. 처음에 문제를 보자마자 bfs 랑 브루트포스 알고리즘을 이용해서 풀게 되면 쉽게 해결할 수 있을것이라고 생각했다. 요즘 solved라는걸 친구가 백준이랑 연동시켜줘서 보는 재미가 솔솔하다 ㅎㅎ 그래서 가끔 문제 풀기전에 난이도를 보고 쫄기도하고 자신감있게 풀기도 한다 그래서 이번에도 한번 어느정도 난이도인지를 찾아보았다. 골드4였다. 골드 4정도야~라고 생각하고 문제를 읽었..

위상정렬이란? : 순서가 정해져있는 작업을 차례로 수행해야 할 때, 그때 그 순서를 정해주는 것. 예를 들어서 작업의 순서가 1 - (2,3) - 4 - 5 이떄 괄호 안에는 둘다 무엇이 먼저 가든 상관이 없다. 즉 1과 2, 1과3이 연결되어있고 2와4 3과4가 연결이 되어있다고 생각하면된다. 위상정렬에서 중요한것은 시작점과 정점 즉, 끝점이 존재한다는것이다. 만약에 시작점과 끝점이 존재하지 않으면 계속 무한으로 돌기 때문이다. 그래서 위상정렬은 DAG라고 한다. DAG : Directed Acyclic Graph 즉, 사이클이 존재하지 않는 방향 그래프이다. 위상 정렬의 원리는 1) 각 노들의 진입 차수를 계산 즉 몇개의 노드들과 연결되어있는지. 2) 진입 차수 (연결된 노드가 ) 없다면 즉 0 인 ..

일반적으로 string 에서 cin 으로 입력을 받으면 띄어쓰기를 기준으로 읽게 된다. 그런데 문자열 전체를 받기 위해서는 띄어쓰기를 무시하고 한 문장을 띄어쓰기 기준으로 할 땐 std::getline()함수를 사용하면된다. 사용법은 다음과 같다. #include using namespace std; int main(){ int n; string s; cin >> n; cin.ignore(); getline(cin,s); cout

구간안에 있는 배열, 벡터의 최대, 최소 값을 구하는 함수입니다. 이 함수는 계산된 값을 리턴하지 않고 주소값을 리턴한다. 따라서, 값을 보고 싶을 땐 *을 이용하여 값을 참조한다.