나쿠리 개발 메모장

개요 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 실버급 DFS, BFS 문제다. 풀이 재귀를 활용한 DFS로 풀었다. 반복문으로 배열(N*N)을 하나씩 체크하고, 1을 발견하면 DFS로 크기를 체크하고 단지수를 증가시키도록 했다. 단지 수는 재귀가 처음 호출 될 때에만 증가할 수 있도록 isFirst(bool) 변수를 사용했다. 마지막 출력 값(각 단지 크기)을 오름차순 정렬하여 출력해야 함에 주의해야 한다. 정렬 안 해서 몇 번 틀렸다(!..

개요 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 실버급 수학 및 해시 문제다. 풀이 경우의 수를 구할 식만 떠올리면 된다. 분류별 옷의 수 + 1(벗은 상태)를 전부 곱해주면 된다. 주의할 점은 알몸인 상태는 제외라고 나와있으니 이 결과에 -1을 해주어야 한다. map을 사용해 구현했다. 코드 #include #include #include #in..

개요 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 실버급 BFS 문제다. 풀이 가장 빠른 길을 출력해야한다. BFS를 활용한다면 가장 먼저 도착하는 길을 구분할 수 있기 때문에 BFS를 떠올렸다. 구조체로 현재 좌표와 거리를 정의하고, 현재 위치의 상하좌우로 넓혀가며 탐색했다. 입력은 숫자를 붙여서 받기 때문에 scanf("%1d", &array[i][j])와 같은 방식으로 받았다. IDE에서 답은 계속 맞게 나오는데 제출하면 자꾸 틀리는 문제가 있었다. ios_base:..

개요 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 실버급 DFS 및 BFS 기본 문제다. 본문 풀이 연습해 볼 겸 인접행렬로 구현해 봤다. 스택을 활용한 DFS로 풀려고 한참 고민했는데, 카운트하는 부분에서 계속 막혔다. 그래서 재귀로 DFS를 구현했더니 바로 풀렸다,,내 시간 스택으로도 풀 수 있을 것 같은데 조금 더 복잡해질 듯하다. 주의할 점으로는 연결되지 않는 상황(-1 출력)을 고려해야 한다. 코드 #includ..

개요 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 브롱즈급 브루트포스 문제다. 본문 풀이 생각보다 오래 걸렸다,,!! 난쟁이 9명 중 7명을 추려내려고 하니 여간 복잡한 게 아니었는데,, 반대로 생각해 보니 2명만 빼면 되는 것이었다. 브루트포스로 정답을 골라낸 후 1000으로 바꿔주었다.(모든 입력 값은 100 이하) 주의할 점은 값을 오름차순으로 정렬 후 출력해야 한다는 점! 코드 #include #include using namespace st..

개요 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 실버 2급 DFS와 BFS 기초 문제다. 본문 풀이 인접 리스트 기반(vector)으로 구현했다. 각각 DFS는 stack, BFS는 queue를 사용했다. 정점의 번호가 작은 순으로 탐색하라는 조건이 있기 때문에 리스트(vector)를 정렬해주어야 한다. DFS는 스택으로 후입선출이기 때문에 내림차순으로, BFS는 큐로 선입선출이기 때문에 오름차순으로 ..

개요 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 실버 3급 그래프 탐색 문제다. 본문 풀이 그래프 탐색 문제 중 저 난이도 문제인듯하다. 제한이 크게 없어 BFS, DFS 중 어느 것을 사용해도 문제가 없을 것이라 판단했다. queue를 활용한 인접 리스트(vector) 기반 BFS로 풀었다. 1번 컴퓨터는 제외이기 때문에 이 점에 유의해야 한다. 코드 #include #include #include #include using namespace..

DFS(Depth First Search) DFS(깊이 우선 탐색)는 그래프의 탐색 방법 중 한 가지이다. DFS는 크게 세 가지 과정으로 나뉜다. 한쪽으로만 계속 방문 더 이상 방문할 정점이 없으면, 이전 정점으로 이동 처음 정점으로 돌아가면 탐색 종료 DFS의 구현 정점 방문 정보 기록을 목적으로 스택을 활용하면 된다. 방문 여부는 배열에 저장한다. 정점을 방문할 때 출발 정점을 스택에 PUSH 하면 된다. 이때 방문 여부는 출발 정점, 도착 정점 둘 다 처리한다. 더 이상 방문할 정점이 없을 경우 스택에서 POP 하면서 이전 정점으로 돌아가며 다시 확인하면 된다. 모든 정점을 방문했을 경우를 배열로 확인하여 탐색을 종료하면 끝이다. 다음 정점 방문 (스택에 이전 정점 추가, 둘 다 방문 배열 체크)..

개요 그래프는 정점과 정점을 잇는 간선의 모임이며 데이터의 표현 방식이다. 그래프 자체가 알고리즘이라기 보단, 그래프를 근거로한 여러 알고리즘들이 존재한다. 본문 그래프의 종류 그래프의 집합 표현 V = Vertex E = Edge V(G1) = {A, B, C, D} E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)} V(G3) = {A, B, C, D} E(G3) = {, , } 그래프의 구현 인접 행렬 기반 V*V 크기의 2차원 배열을 사용하여 구현한다. 인접 리스트 기반 연결리스트를 기반으로 그래프를 구현한다. 무방향 그래프의 경우 정점 노드를 둘다 연결해야함에 주의 그래프 탐색 알고리즘 대표적으로 DFS와 BFS가 있다. DFS(Depth First Searc..

개요 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 실버급 DP 문제다. 본문 풀이 2차원 배열인 dp에 점수를 저장했다. dp[계단번호][연속이동횟수] 중복되는 부분은 함수로 처리했다. 코드 #include #include #include using namespace std; constexpr int RANGE = 302; int GetMaxDP(int* dp) { int max = (dp[1] > dp[2]) ? dp[1] : dp[2]; return..