문제 링크 : https://www.acmicpc.net/problem/9663문제 요약N×N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 문제다.퀸은 가로, 세로, 대각선 방향으로 모두 공격할 수 있다.결국 조건은 이거다.같은 행에 두 개 있으면 안 되고같은 열에 두 개 있으면 안 되고같은 대각선 위에 있어도 안 된다풀이 사고 과정이 문제는 조금만 생각해보면 형태가 단순해진다.각 행에는 어차피 퀸을 하나씩만 놓으면 된다.그렇다면 문제는 이렇게 바뀐다.각 행에 하나씩 퀸을 두되,열과 대각선이 겹치지 않도록 배치하라. 이제 “행”은 깊이(depth)로 보고,각 depth마다 “어느 열에 둘 것인가”를 결정하면 된다.그래서 자연스럽게 백트래킹을 떠올렸다.첫 번째 행에서 가능한 열에 하나 놓고,두 ..

문제 링크: https://www.acmicpc.net/problem/15686문제 요약도시에는 집과 치킨집이 있고, 치킨집 중에서 M개만 남겨야 한다. 각 집에서 가장 가까운 치킨집까지의 거리(치킨 거리)를 구하고, 그 합이 최소가 되도록 M개의 치킨집을 선택하는 문제다. 결국 핵심은 치킨집을 어떻게 고를 것인가이다.풀이 사고 과정처음에 든 생각은 단순했다.만약 M이 치킨집 개수와 같다면 그냥 전부 사용하면 된다.그런데 M이 더 작다면, 일부를 골라야 한다.결국 “치킨집 중에서 M개를 고르는 문제”이고, 이건 조합 문제다.그래서 백트래킹으로 조합을 만들기로 했다.치킨집의 위치들을 pair 형태로 저장하고, 그 인덱스를 기준으로 조합을 생성한다. 조합이 하나 완성되면 그 조합을 기준으로 도시 치킨 거리를..

https://www.acmicpc.net/problem/1707 문제를 처음 보고 한 착각처음 이 문제를 접근했을 때는이분 그래프가 정확히 뭔지 몰라서 연결 요소의 숫자를 구했었다.로직은 맞는데 정답이 이상하게 나와 이상하다고 여겨이분 그래프가 정확히 뭔지 구글링을 했다.... 구글링을 한 결과 문제를 완전히 잘못 이해했다는 것을 깨달았다. 이분 그래프란 :모든 정점을 두 개의 그룹으로 나누었을 때,같은 그룹에 속한 정점끼리는 서로 연결된 간선이 없느 그래프즉, 한 정점이 그룹 A라면 그 이웃들은 전부 그룹 B여야 한다. 개념만 이해하고 나니까, 로직은 오히려 단순했다.정점을 두 그룹으로 나눌 수 있는가?모든 간선이 서로 다른 그룹을 연결하는가?이 규칙만 지키면 이분 그래프다. 구현 아이디어핵심 아이디..

https://www.acmicpc.net/problem/7576 문제 요약2차원 격자에서 토마토가 익어간다.1: 익은 토마토, 0: 안 익은 토마토, -1: 빈 칸하루가 지나면 익은 토마토의 상하좌우 토마토가 익는다.모든 토마토가 익기까지 걸리는 최소 일수를 구하라.끝까지 익지 못하는 토마토가 있다면 -1 출력문제를 보고 처음 든 생각들문제를 딱 읽고 나서 정리한 생각은 이랬다.0이 고립되어 있으면 → 이건 무조건 fail입력 받을 때 1이 있는 위치는 전부 시작점이 될 수 있음하루 단위로 퍼져나가니까 DFS는 아니고 BFSBFS를 다 돌고 나서 가장 깊은 depth가 정답일 듯? ❌ 처음에 시도한 방법 (실패)내가 처음에 생각한 방식은 이거였다.시작점(1)이 여러 개니까각 시작점마다 BFS를 각각 실..

https://www.acmicpc.net/problem/2667 이 문제는2차원 격자에서 연결된 컴포넌트(Connected Component)를 찾는 전형적인 문제다.겉으로 보면 단순한 BFS 문제처럼 보이지만,막상 구현하려고 하면 다음 지점에서 많이 막히게 된다.BFS를 어떻게 여러 번 호출하지?각 단지가 몇 개의 집으로 이루어졌는지는 어디서 세야 하지?나 역시 이 아이디어를 떠올리는 데 꽤 시간이 걸렸다.문제 핵심 요약1 → 집이 있는 곳0 → 집이 없는 곳상하좌우로 연결된 1들의 묶음이 하나의 단지구해야 할 것전체 단지 개수각 단지에 포함된 집의 수 (오름차순 출력)즉, 이 문제는👉 “BFS 한 번 = 단지 하나” 라는 관점으로 접근해야 한다.접근하면서 가장 어려웠던 점처음에는 이런 생각까지는 ..

문제 핵심 요약무방향 그래프정점 번호가 작은 것부터 방문같은 시작점에서DFS 결과 출력BFS 결과 출력즉, 탐색 알고리즘 + 순서 제어가 핵심입니다. 이 문제를 DFS/BFS 템플릿 문제로 두고,이 구조를 기반으로 다른 그래프 문제들을 풀고 있습니다.DFS / BFS 수도코드 정리DFS 수도코드 (재귀 기반)DFS(node): node 방문 처리 node 출력 for 인접한 정점 next: if 방문하지 않았다면: DFS(next)BFS 수도코드 (큐 기반)queue 생성시작 노드 push시작 노드 방문 처리while queue가 비어있지 않다면: 현재 노드 pop 현재 노드 출력 for 인접한 정점 next: if 방문하지 않..

https://school.programmers.co.kr/learn/courses/30/lessons/12981문제 간단 요약n명이 영어 끝말잇기를 진행한다.이전 단어의 마지막 문자로 다음 단어를 시작해야 한다.이미 사용한 단어를 다시 말하거나,단어 길이가 1이면 탈락이다.👉 규칙을 어긴 사람의 번호와 차례를 구하는 문제👉 끝까지 문제가 없으면 [0, 0] 반환 문제의 핵심 포인트 이 문제는 알고리즘 자체는 어렵지 않다.대신 다음 요소들을 꼼꼼하게 처리해야 한다.이미 사용한 단어인지끝말잇기 규칙이 지켜졌는지단어 길이가 1인지탈락한 인덱스로부터 사람 번호 / 차례 계산 사용한 해결 전략unordered_set→ 이미 나온 단어를 빠르게 확인하기 위해 사용반복문으로 단어를 하나씩 검사규칙을 어기는 순간..

https://www.acmicpc.net/problem/14425문제 간단 요약문자열로 이루어진 집합 S가 주어진다.이후 주어지는 문자열들 중집합 S에 포함된 문자열의 개수를 구하는 문제다.핵심 연산은 반복적인 문자열 존재 여부 확인이다.-> 문자열 비교가 많이 발생하므로,빠른 탐색이 가능한 자료구조를 선택하는 것이 중요하다.문제 접근 아이디어이 문제를 단순하게 풀면 다음과 같다.문자열을 하나씩 저장이후 문자열이 있는지 매번 비교 (==)로 확인하지만 문자열 비교는 길이에 따라 비용이 커지고,전체 시간복잡도는 비효율적으로 커질 수 있다.여기서 관점을 바꾸면 문제는 이렇게 변한다.“이 문자열이 집합에 있는지 없는지만 빠르게 확인하자” 이럴 때 가장 적합한 자료구조가 해시(Hash) 이다.해결 방법: un..