문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 풀이 외부와 2개의 면이 맞닿아 있는 치즈를 매 턴 제거하는 문제이다. 만약 '외부' 지점을 알 수 있다면, 모든 '외부' 지점을 탐색하며 자신의 상,하,좌,우 에 치즈가 있을 경우, 표시를 하여 2번의 표시가 담긴 치즈 블럭이 존재한다면, 2개의 면이 외부에 노출된 것으로 보고 제거하면 된다. 그렇다면 '외부' 지점을 어떻게 알 수 있을까? 이 문제에서 '모눈종이의 ..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49191# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 보고 플로이드 와샬이 떠올랐다. A >B 이고, B> C 라면 A>C라는 것은 곧, A 가 1 다리만 걸친다면 B만 이기는 것이지만, 'B' 를 거치면 C 를 이기는 경우의 수를 찾을 수 있기 때문이다. 따라서, i 번 사람이 j 번 사람과 붙어서 이기는가? 에 대해서 아래와 같이 규정하였다. dp[i][j] 1: i가 j에게 이긴다 0: i와 j의 승패는 모른다 -..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12952# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 이 문제는 dfs를 통한 완전탐색 과정에서, 백트래킹으로, 불가능한 트리의 가지를 가지치기 하여 수행 시간을 감소시켜야만 시간초과가 발생하지 않는다. 나는 이를 위해, 퀸이 8방향 모든 칸으로 이동하는 특성 중 좌, 우 모두 이동 가능한 특성을 활용하여 각 dfs(depth) 에서, depth 번째 행에 퀸을 놓을 수 있는 위치를 찾는 것으로 문제를 해결했다. 퀸을 놓을 행은..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 dfs의 특성을 활용하여 사전순으로 완전 탐색을 진행할 수 있다. 따라서, 탐색 순서에 따라 진행하던 중, 찾고자하는 string이 나오면 해당 string의 순서를 리턴하면 된다. dfs를 통한 사전순 완전탐색으로 순서 계산 #include #include #include using namespace std; string words="AEIOU"; string ans_str..
이번 글에선, c++ 에서 순열과 조합을 재귀를 통해 구현하는 포맷에 대해 알려드리겠습니다. 혹시 next_permutation을 통한 풀이가 궁금하시다면, 아래 글을 참고해주세요. 순열과 조합 (C++) — 코딩이랑 이것저것 (tistory.com) 순열과 조합 (C++) [ n개의 숫자를 전부 사용해서 만들 수 있는 모든 순열의 갯수] ex) 1,2,2 가 input으로 들어오면 1,2,2 2,1,2 2,2,1 3가지가 나온다. 여기서 중요한 점은 "중복된 순열은 제거" 된다는 점이다. 1,2( 1th ) , 2( 2 codenme.tistory.com 1) 순열 nPm, 즉 n개의 값들 중, m개를 처럼 순서를 고려해서 선택한다. ex: (1,2) != (2,1) 입출력 예시 4 2 //4P2 12..
dfs로 전선 연결이 필요한 모든 프로세서 들이 전설을 이을 모든 경우의 수를 따져서 구했다. 여기서, 만약 해당 프로세서가 벽으로 도달하지 못하는 경우를 계산하여 백트래킹( 가지치기) 를 수행하였다. 추가로, 이 문제에선,'모두 연결 가능 할시의 최단 거리' 가 아니라, '최대한 많은 개수를 연결할 시 의 최단거리' 를 구해야한다. 따라서, dfs를 통해 해당 프로세서를 '상','하','좌','우' 로 연결하는 가능성에 더해, '해당 프로세서를 연결하지 않는 가능성' 도 체크해야한다. 예시 위와 같이 입력이 들어온 경우, 우리가 전선으로 연결해줘야하는, 파란 동그라미 표시를한 프로세서에 대해 전선의 연결 가능성을 확인해야한다. 하지만, 맨위의 파랑 원은, 다른 전선들이 연결되면, 필연적으로 벽에 닿을 ..
시작하기에 앞서, 기초적인 구현 방식, 정보들은 최대한 글에서 다루지 않을 예정이고, 혼동되거나 헷갈리는 부분들, 놓치고 넘어가기 쉬운부분들만 설명할 것임을 유의해주세요..! 그래프 탐색이 필요한 이유는 바로 선형적인 탐색 (for문을 통한 i:1~n) 으로 탐색하지 못하는 문제들을 탐색하기 위해서이다. 예를들어 그래프 탐색이 필요한 문제중 하나인 백준 2178 "미로 탐색" 을 보자. 우리는 점차 증가하는 인덱스를 통한 탐색이 아닌, 갈 수 있는 위치로 향하는 탐색을 해야하는데, 이는 for문과 적합하지 않다. 그렇기에 우린 이러한 갈 수 있는 방향을 "그래프" 로 만들어나가며 탐색을 해나가는 것이다. 그래프의 대략적인 정의는 정점, 그리고 간선으로 이루어진 대충 아래 그림 같은 친구들을 말한다. 그래..
