문제 유형 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 +, - 선택 (있거나 없거나) 양자 택일은 dfs 또한, 연산 끝이(depth) 있다. (피연산자 개수만큼) 기저조건을 피연산자를 다 사용했을 때와 count 개수 세는 로직과 분리해야 한다. 만약 if(count === numbers.length && sum === target) 이렇게 설계하면 함수 종료 return과 count 둘 중 하나가 안 돌아간다. (무한 호출 ..

문제 링크 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 접근법 DFS로 원소를 넣는 경우와 넣지 않는 경우를 탐색한다. (조합) DFS로 탐색하면서 입력 개수에 도달하면 원하는 답인지 확인한다. 이렇게 안하고 매 순간마다 if(sum== answer)을 확인하면 return구분이 복잡해진다. 또한 dfs 탐색으로 깊이를 끝까지 탐색해야 이 문제에서 완전 탐색으로 답을 구할 수 있다. private static void dfs(int idx, int sum) { // df..

문제 링크 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 접근법 이 문제는 일반적인 DFS 문제처럼 풀면 조금 어려울 수 있다. DFS의 재귀(스택) 원리를 정확히 이해하고 그래프의 구조를 파악할 수 있어야 쉽게 풀 수 있다. 문제를 정리하면 친구끼리의 관계는 그래프에서 간선으로 나타낼 수 있다. 앞으로 간선 =관계 라는 것을 알고 있으면 다른 문제에도 그래프 탐색을 고려해봐야 한다. DFS로 리스트에 정점을 넣고 DFS로 깊이가 4인 곳을 찾으면 되는데 문제는 입력값이 트리와 그래프 모두 주어진다. 이 문제를 일반적인 트리로 접근하면 입력 테케 2에서 틀린다. 트리는 두 개의 노드 사이에 1개의 경로만을 가지며 ..

문제 링크 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 접근법 노드의 개수 N (1

문제링크 : https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 삼성 역량평가 IM 수준의 대표 문제입니다. 4방탐색과 BFS, DFS를 이용하는 (2차원 배열) 그래프 탐색문제이다. 백준 게시판을 살펴보니, 이 문제의 가로, 세로 입력을 잘못해서 물어보는 경우가 많았다. public class 이차원배열 { public static void main(String[] args) { int N = 4; // 가로 int M ..