문제 링크 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 설명 컴퓨터 한 대가 바이러스에 감염되면 같은 네트워크로 연결되어 있는 컴퓨터 모두가 바이러스에 감염된다고 한다. 1번 컴퓨터로 인해 감염되는 컴퓨터의 수를 출력해보자. 풀이 무향 그래프에서 시작 노드가 1이고 방문할 수 있는 노드의 개수를 세면 되는 BFS문제이다.(DFS로도 해결가능 할 것 같다.) 코드
Github에 등록된 이메일 주소를 확인한다. 1. Github 접속, 로그인 2. 우측 상단에 있는 둥근 아이콘 클릭 3. your profile 클릭 4. 왼쪽 큰 둥근 아이콘 클릭 5. Emails 클릭 6. 등록된 이메일 주소 확인 현재 로컬에 저장된 이메일 주소를 확인한다. git bash 실행하고 아래 명령어를 입력한다. $ git config --global --list 그럼 위와 같이 user.name, user.email이 나온다. Github 이메일 주소와 로컬 이메일 주소를 일치시킨다. 아마 로컬에 저장된 이메일 주소와 github에 저장된 이메일 주소가 다를 것이다. $vim ~/.gitconfig 위의 명령어를 작성하여 gitconfig파일을 연다 그러면 위와 같은 파일이 나오고 ..
문제 링크 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net 문제 설명 1부터 N까지 순서대로 써놓았는데 몇 개의 숫자가 지워진 상태다. 이 상태가 주어질 때 N의 최솟값을 구하는 문제이다. 아무것도 지워지지 않았을 수도 있다. 풀이 방법 주어지는 수의 최대 길이가 3,000자리 이고, 0~9까지 10개이기 때문에 30,000 이내에서 찾을 수 있다. 문제를 풀기 위해 두 가지 변수를 사용할 것이다. 하나는 입력 받은 문자에서 현재 보고 있는 index를 저장할 pointer변수, 다른 하나는 현재 값을 의미..
문제 링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 설명 한나는 자신의 땅에 배추를 군데군데 심어놓은 상태다. 아래는 현재 한나의 땅 상태고, 1은 배추가 심어져 있는, 0은 배추가 심어져 있지 않은 땅을 나타낸다. 배추를 해충으로부터 보호하기 위해 배추흰지렁이를 놓을 계획이고 배추흰지렁이는 인접한 땅을 옮겨가며 배추를 보호할 수 있다. 최소의 배추흰지렁이 마리 수를 구하자. 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0..
이번 방학에는 머신러닝에 대해 공부도 조금 해보려고 한다. 그에 앞서 아나콘다와 텐서플로우를 설치하여 jupyter notebook을 사용하는 중이다. github에 올리는 방법은 다양하기도 하고 구글링을 하면 정말 많이 나오지만 수업시간에 배웠던 내용도 상기하면서 정리해두면 다음에 찾는 수고를 덜을 수 있을 것 같아 정리해놓으려고 한다. (아래 코드블럭에 들어가있는 명령어는 git bash에서 작성하였다.) 컴퓨터에 로컬 저장소 만들기 $ cd ~ $ mkdir workspace $ cd workspace $ git init cd ~ : home directory로 이동 mkdir workspace : workspace이름의 폴더 생성 (폴더 이름은 개인이 바꿔도 된다) cd workspace : 방금..
Quick Sort 정렬 알고리즘 중 하나로 분할 정복(Divide and Conquer) 전략을 사용하는 알고리즘이다. C++ algorithm 헤더에 있는 sort함수는 퀵 소트로 구현되어 있고, 이러한 이유는 평균 수행시간이 빠르기 때문이다. (수행 시간에 대한 분석은 아래에 정리할 것이다.) 퀵 소트에서 중요한 부분은 피벗(pivot)과 파티션(partition)이고, 간단하게 피벗을 뽑고 파티션한다! 라고 생각할 수 있다. 피벗은 비교를 진행하기 위한 기준이 되는 원소를 말한다. 이 때 피벗은 가장 앞에 있는 원소로 선택할 수 있고 구현하는 방법에 따라 random하게 선택할 수도 있다. (여기서는 가장 앞에 있는 원소를 피벗으로 설정할 예정이다.) 다른 모든 원소들을 피벗과 비교하며 피벗보다 ..
백트래킹 백트래킹은 해가 될 수 있는 경로에 대해 탐색을 진행하다가 해가 아니라는 것을 알게 되면 더 이상 탐색을 진행하지 않고 종료한 뒤 다른 경로에 대해 탐색하여 해를 찾는 방법이다. 백트래킹의 개념을 잡을 때 백준에 있는 N과 M시리즈를 풀어보면 도움이 많이 된다. 그 중 첫 번째 문제를 가지고 설명을 진행하며 백트래킹에 대한 개념을 이해해보도록 하자. 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제의 내용 자체도 길지 않으나 요약하면 1~N까지의 수 중 중복 없이 길이가 M인 수열을 모두 찾아 출..
문제링크 17829번: 222-풀링 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22 www.acmicpc.net 풀이 한 변의 길이가 2가 아니라면 한 변의 길이를 N/2로 만들어 다시 함수를 호출하는 식으로 분할정복을 이용하여 풀이할 수 있다. 나는 4개의 숫자중 두 번째로 큰 수를 고르기 위해 임시로 vector를 만들어서 넣어주고 algorithm 헤더의 sort함수를 사용하여 정렬해준 뒤 인덱스로 직접 접근하였다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..
