문제 링크 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 트리가 주어졌을 때 트리의 루트를 1이라고 하고 각 노드의 부모를 구하는 프로그램을 작성해야 한다. 문제 풀이 입력으로 주어지는 트리를 무향 그래프로 만들어주고 1번부터 bfs를 진행한다. 이 때 parent라는 배열을 미리 만들어두고 어떤 노드를 통해 방문하였는지를 저장해주면 parent배열에는 각 노드의 부모 노드가 저장이 될 것이다. 말로만 설명하면 어려우니 그림을 통해 같이 보자. 위는 문제에서 주어진 예시이다. 예시를 통해 그래프를 그려보면 다음과 같을 것이다. 7 1 6 6 3 3 5 4 1 2..
문제 링크 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 N개의 정점과 M개의 간선으로 이루어진 무향 그래프가 주어졌을 때 DFS로 방문한 정점의 순서와 BFS로 방문한 정점의 순서를 출력한다. (이 때 방문할 수 있는 정점이 여러개면 정점 번호가 작은 것부터 먼저 방문함에 주의하자.) 추가적인 부가 설명없이 코드를 보자. 코드 메모 BFS와 DFS를 공부하고 스스로 코드를 작성해보면서 공부할 수 있는 좋은 문제라고 생각된다.
문제 링크 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 설명 컴퓨터 한 대가 바이러스에 감염되면 같은 네트워크로 연결되어 있는 컴퓨터 모두가 바이러스에 감염된다고 한다. 1번 컴퓨터로 인해 감염되는 컴퓨터의 수를 출력해보자. 풀이 무향 그래프에서 시작 노드가 1이고 방문할 수 있는 노드의 개수를 세면 되는 BFS문제이다.(DFS로도 해결가능 할 것 같다.) 코드
문제 링크 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..
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..
