승코딩당당당

문제[C++] 백준 2178: 미로 탐색 SILVER 1https://www.acmicpc.net/problem/2178 접근 방법이 문제는 미로에서 시작점 (0, 0)부터 도착점 (N-1, M-1)까지 이동할 때 지나야 하는 최소 칸 수를 구하는 문제이다.각 칸은 이동 가능(1) 또는 불가능(0)으로 주어지며, 상하좌우로만 이동할 수 있다. 큐에는 현재 위치 (0, 0)를 넣고, 이동 가능한 다음 칸으로 확장하면서 방문 처리와 함께 maze 배열에 (0, 0)이전 칸 값 + 1을 저장해 거리 정보를 누적한다.최단 거리를 구해야 하므로 BFS(너비 우선 탐색) 를 사용한다.DFS보다 BFS가 적합한 이유는 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문이다. BFS는..

그래프 문제를 풀다 보면 깊이 우선 탐색(DFS)와 함께 반드시 등장하는 탐색 알고리즘이 너비 우선 탐색(BFS)이다.BFS 역시 그래프의 모든 노드를 빠짐없이 방문하기 위한 완전 탐색 알고리즘 중 하나로, 시작 노드를 기준으로 가까운 노드부터 차례대로 탐색하는 방식이 특징이다.이번 글에서는 BFS의 개념과 특징, 구현 방식, 시간 복잡도, 그리고 DFS와 다른 점까지 간단히 정리해보려고 한다. ✍️ DFS 관련 내용은 다음 링크를 참고하면 좋습니다!https://xeungcoding.tistory.com/25 DFS(depth-first search) 깊이 우선 탐색그래프 문제를 풀다 보면 가장 먼저 접하게 되는 탐색 알고리즘이 깊이 우선 탐색(DFS)이다.DFS는 그래프의 모든 노드를 빠짐없이 방문하..

그래프 문제를 풀다 보면 가장 먼저 접하게 되는 탐색 알고리즘이 깊이 우선 탐색(DFS)이다.DFS는 그래프의 모든 노드를 빠짐없이 방문하기 위한 완전 탐색 기법 중 하나로, 구현이 비교적 직관적이어서 알고리즘 입문 단계에서 자주 사용된다.이번 글에서는 DFS의 개념, 특징, 시간 복잡도, 그리고 어떤 문제들에 활용되는지까지 간단히 정리해보려고 한다. ✍️ 깊이 우선 탐색이란?그래프의 시작 노드에서 출발하여 한 방향으로 끝까지 깊게 탐색한 뒤,더 이상 갈 곳이 없으면 이전 분기점으로 돌아가 다른 경로를 탐색하는 방식의 알고리즘이다. 즉,한 노드를 방문하면그 노드와 연결된 노드 중 하나를 선택해최대 깊이까지 탐색을 먼저 수행하고이후 다른 분기를 차례로 탐색한다.이러한 동작 방식 때문에 DFS는 “깊게..

문제[C++] 백준 13023: ABCDE GOLD 5https://www.acmicpc.net/problem/13023 접근 방법이 문제는 사람 관계가 주어졌을 때, 서로 연속으로 연결된 5명(A–B–C–D–E) 이 존재하는지를 판단하는 문제이다.처음에 이 부분을 이해 못 해서 헤맸다;;즉, 그래프에서 길이 4의 경로(간선)가 하나라도 있으면 1, 없으면 0을 출력한다. 무방향 그래프이므로 친구 관계 (a, b)는 양방향으로 저장한다.각 정점을 시작점으로 삼아 DFS를 수행하면서,현재까지 연결된 사람 수(cnt)가 4가 되는 순간 4개의 조건을 만족한 것이므로 탐색을 종료한다. 간선이 4개 = 노드가 5개 → 조건 만족if (cnt == 4) // 4가지 조건 모두 만족 시{ flag = true;..

문제[C++] 백준 2023: 신기한 소수 GOLD 5https://www.acmicpc.net/problem/2023 접근 방법이 문제는 N자리 소수를 찾는 문제이다. 완성된 N자리 수가 소수여야 할 뿐만 아니라, 앞에서부터 잘라 만든 모든 자리 수가 전부 소수여야 한다.즉,4자리 수라면 👉 1자리 → 2자리 → 3자리 → 4자리모든 단계에서 소수 검사를 통과해야 한다.그래서 단순히 N자리 수를 전부 만들고 검사하는 방식이 아니라,자리수를 하나씩 늘려가며(DFS) 매 단계마다 소수인지 확인하고 진행하는 방식으로 풀었다. 1자리에서 시작 가능한 소수는 2, 3, 5, 7뿐이라 이 값들로 DFS를 시작한다.다음 자리로 확장할 때는 짝수나 5로 끝나면 소수가 될 수 없으므로, 뒤에 붙일 숫자를 1, 3,..

문제[C++] 백준 11724: 연결 요소의 개수 SILVER 2https://www.acmicpc.net/problem/11724 접근 방법이 문제는 정점과 간선이 주어졌을 때, 그래프의 연결 요소(Connected Component) 개수를 구하는 문제이다.그래프는 무방향 그래프이므로 간선 (u, v)가 주어지면 u ↔ v 양방향으로 연결한다.인접 리스트(vect)로 그래프를 구성하고, visited 배열로 방문 여부를 관리한다.아직 방문하지 않은 정점을 하나 선택해 DFS를 수행하면, 해당 DFS가 끝날 때까지 방문한 정점들은 모두 같은 연결 요소에 속한다.따라서 DFS를 한 번 시작할 때마다 연결 요소의 개수를 1 증가시키면 된다. 구현 시 주의할 점정점 번호가 1부터 n까지이므로, 인접 리스트..

출판사 서평 주인공은 25세의 미혼여성 안진진. 시장에서 내복을 팔고 있는 억척스런 어머니와 행방불명의 상태로 떠돌다 가끔씩 귀가하는 아버지, 그리고 조폭의 보스가 인생의 꿈인 남동생이 가족이다. 여기에 소설의 중요 인물로 등장하는 이모는 주인공 안진진의 어머니와는 일란성 쌍둥이로 태어났지만 인생행로는 사뭇 다르다. 부유한 이모는 지루한 삶에 진력을 내고 있고 가난한 어머니는 처리해야 할 불행들이 많아 지루할 틈이 없다.주인공 안진진은 극단으로 나뉜 어머니와 이모의 삶을 바라보며 모순투성이인 이 삶을 어떻게 이해해야 하는지 심각하게 고민하기 시작한다. 「모순」이라는 제목처럼이 책은 처음부터 끝까지 모순의 연속이라 지루할 틈이 없었다.사람의 마음, 가족의 형태, 사랑의 방식까지 어느 하나 단순하지..

문제[C++] 백준 1012: 유기농 배추 SILVER 2https://www.acmicpc.net/problem/1012 접근 방법이 문제는 배추(1)가 심어진 위치들이 주어졌을 때, 상하좌우로 연결된 배추 묶음(컴포넌트)의 개수를 구하는 문제이다.즉, 연결 요소(Connected Component) 개수를 세면 되고,한 묶음당 필요한 지렁이 수가 1마리이므로 배추 묶음의 개수가 곧 정답이 된다. 배추밭을 N × M 2차원 배열(graph)로 만든 뒤,전체 칸을 순회하면서 배추가 있는 칸(값이 1)을 만나면 DFS를 실행한다. DFS에서는 현재 위치를 기준으로 상하좌우를 탐색하며 연결된 배추들을 전부 방문 처리한다. (1→0으로 변경)한 번 DFS를 시작했다는 건 “하나의 묶음을 전부 처리했다”는 뜻..

문제[C++] 백준 8979: 올림픽 SILVER 5https://www.acmicpc.net/problem/8979 접근 방법이 문제는 각 국가의 금/은/동 메달 수가 주어졌을 때, 특정 국가 k의 올림픽 순위를 구하는 문제이다.순위 기준은 아래와 같이 정렬한 뒤, k가 몇 번째 그룹에 속하는지 계산하면 된다.금메달 많은 순금이 같으면 은메달 많은 순은도 같으면 동메달 많은 순처음에는 입력을 string으로 저장해서 비교하려고 했는데, 채점이 8점에서 계속 멈췄다.원인을 고민해보니 문자열로 처리하면서 한 자리 수만 고려한 입력 방식이었고,두 자리 이상의 숫자가 들어오는 경우 제대로 읽히지 않아 정렬과 비교가 틀어졌던 것이었다.그래서 입력을 int로 2중 벡터에 받는 방식으로 수정했다. 상세 아이디어..

문제[C++] 백준 2447: 별 찍기 - 10 GOLD 5https://www.acmicpc.net/problem/2447 접근 방법백준 2447은 N(=3^k) × N 크기의 정사각형에 별 패턴을 출력하는 문제로,큰 정사각형을 3×3으로 분할했을 때 아래 규칙을 따른다.가운데 블록은 전부 공백나머지 8개 블록은 같은 패턴을 재귀적으로 반복재귀 호출 중 바로 출력하는 방식으로 도전했다가 실패하고,https://sernan96.tistory.com/122를 참고해 2차원 벡터에 결과를 먼저 저장한 뒤, 마지막에 한 번에 출력하는 방식으로 구현했다. 상세 아이디어1) 전체 배열 초기화vect를 N × N 크기의 2차원 벡터로 선언하고, 초기값을 전부 ' '(공백)으로 설정한다.이렇게 하면 재귀 과정에서는..