L.O.K

https://school.programmers.co.kr/learn/courses/30/lessons/131705 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 N명의 학생 중에 3명의 조합을 찾는 문제이다. 조합의 모든 경우의 수를 완전탐색하는 알고리즘에는 백트래킹(BackTracking)이 있다. DFS와는 다르다. DFS는 모든 '노드'를 방문하는 완전탐색 시, 사용되는 알고리즘이다. 백트래킹은 모든 '조합'을 완전 탐색하는 경우 사용되는 알고리즘이다. 그럼 백트래킹을 사용하여 N명의 학생 중 3명의 조함(삼총사)를 찾는 코드를 구현해..

15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net ◎ 문제풀이 2차원 배열에 존재하는 치킨집들에서 M개의 경우를 선택하여 그중 치킨거리가 최소인 거리를 구하는 것이다. N개중 M개를 뽑는 모든 경우를 탐색하는 가장 좋은 방법은 재귀호출을 이용하는 것이다. 재귀호출을 이용하여 가장 적합한 경우를 구하는 문제는 백트래킹(BackTracking)을 활용하면 좋다. 백트래킹은 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 ..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ◎ 문제풀이 NxN의 체스판에 서로를 잡지 않을 위치에 N개의 퀸을 배치할 수 있는 경우의 수를 구하는 문제이다. 퀸은 행, 열, 대각선 방향으로 이동한다. 그러므로 행을 기준으로 하나의 행에는 하나의 퀸만 위치할 수 있다. ( ROW1, COL1 )에 퀸이 위치한다면 ROW2에는 COL3, COL4, COL5에 퀸이 위치할 수 있다. 모든 경우의 수를 완전탐색하는 방법에는 대표적으로 반복문과 재귀호출이 있다. 재귀호출의 장점은 메소드가 반복 호출되면서 이전의 데이터를 간직한다..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net ◎ 문제풀이 굉장히 어려운 문제였다. 인터넷에서 풀이법을 찾아보았는데 다른 사람들도 노가다 한 사람을 제외하면 대부분 풀이를 참고해서 푼거 같다. 1. DFS 구현 및 발상 2. 최대값 가지치기 ( 백트래킹 ) 두 가지 요소를 구현하기 어려웠다. 1. DFS 구현 및 발상 완전탐색을 할 때 DFS 알고리즘(재귀호출)을 사용해야 한다. 그 이유는 아래 포스팅에 잘 설명되어 있다. 백준 14500 테..