본문 바로가기

브루트포스9

[프로그래머스 Lv3] : 카드 짝 맞추기 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72415 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카드 뒤집기 게임에서 모든 카드의 짝을 맞추는 데 필요한 최소 커서 이동 횟수를 리턴하자. 풀이 어디에 어떤 카드가 있는 지는 이미 알고 있지만, 어떤 카드부터 뒤집어야 가장 적은 횟수로 모든 카드의 짝을 맞출 수 있는 지는 알 수 없다. 그렇기 때문에 모든 경우의 수를 다 해보고 최소 횟수를 구해준다. 보드가 4 X 4 크기로 그리 크지 않기 때문에 모든 경우를 다 해봐도 시간초과가 .. 2022. 7. 25.

[BOJ] 17779 : 게리맨더링 2 문제 링크 17779번: 게리맨더링 2 (acmicpc.net) 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 구역별로 선거구를 나눠서 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구하는 문제. 선거구를 나누는 구현문제이다. 풀이 어떻게 선거구를 나눠야 인구 분포가 고르게 될지는 방법이 따로 없다. 모든 경우를 다 따져봐야한다. 5번 선거구의 경계를 좌표로 나타내보면 위와 같다. 따라서 d1, d2는 다음의 조건을 만족해야한다. y - d1 >= 1 && y + d2 2022. 5. 18.

[BOJ] 17142 : 연구소 3 문제 링크 17142번: 연구소 3 (acmicpc.net) 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 모든 칸에 바이러스를 퍼트리는데 걸리는 시간을 구하는 BFS 문제. 풀이 연구실을 N X N 크기의 칸으로 표현했을 때 각 칸은 0 빈 칸, 1 벽, 2 바이러스 중에 하나로 채워진다. 바이러스에는 활성 바이러스와 비활성 바이러스가 있다. 둘다 바이러스지만 활성 바이러스는 전염성을 가지고 비활성 바이러스는 전염성이 없다. 하지만 활성 바이러스가 비활성 바이러스와 만나면 활성화시킬 수 있다. 2 ~ 10개 .. 2022. 5. 17.

[BOJ] 15686 : 치킨 배달 문제 링크 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 얼핏 보면 그래프 문제처럼 보일 수도 있지만 사실 그냥 구현 문제. 풀이 문제에서 그래프 탐색문제처럼 입력을 줬지만 사실 입력값이 1 또는 2 지점의 좌표만 있으면 된다. 최대 13개의 치킨집 중에 M개의 치킨집을 고르는데. 도시의 치킨거리가 최소가 되도록 M개를 골라야한다. 어떤 치킨집을 M개 골라야 유리한지 단번에 결정할 수 없으므로 브루트 포스 알고리즘으로 모든 경우를 탐색한다.. 2022. 5. 9.

[BOJ] 14529 : Where's Bessie? 문제 링크 14529번: Where's Bessie? (acmicpc.net) 14529번: Where's Bessie? Always known for being quite tech-savy, Farmer John is testing out his new automated drone-mounted cow locator camera, which supposedly can take a picture of his field and automatically figure out the location of cows. Unfortunately, the camera does not in www.acmicpc.net 브루트포스 기법으로 모든 크기의 구역을 탐색하는 그래프탐색 문제. 문제 해석 파파고까지 쓰면서 해석했지.. 2022. 4. 29.

[BOJ] 5901 : Relocation 문제 링크 https://www.acmicpc.net/problem/5901 5901번: Relocation Input Details There are 5 towns, with towns 1, 2, and 3 having markets. There are 6 roads. Output Details FJ builds his farm in town 5. His daily schedule takes him through towns 5-1-2-3-2-1-5, for a total distance of 12. www.acmicpc.net 다익스트라를 활용하는 문제 문제 해석 문제를 그대로 해석한게 아니라 해석해서 정리한 것이다. 농부 존은 그의 일과동안에 최단 경로로 다니기 위해서 농장의 위치를 옮기려고한다. 존.. 2022. 4. 25.

[BOJ] 9874 : Wormholes 문제 링크 9874번: Wormholes (acmicpc.net) 9874번: Wormholes Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 2022. 4. 22.

[BOJ] 15684 : 사다리 조작 문제 링크 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 백트래킹으로 완전탐색하기. 풀이 기존의 사다리에 3개 이하의 새로운 다리를 놓아서 i번 사다리값이 i가 나오도록 만드는 문제. 백트래킹을 통해서 새로 다리를 놓을 위치를 정한다. 여기서 다리의 여부는 is_connected 배열을 이용해서 저장했다. is_connected[높이][막대 번호1][막대 번호2] 이렇게 3차원배열로 만들어주었고 값이 true면 1번 2번 막대 사이에 가로로.. 2022. 4. 14.

[BOJ] 24885 : 주식 문제 링크 24885번: 주식 (acmicpc.net) 24885번: 주식 첫째 줄에 과거에 머무를 수 있는 기간 $N(2\le N \le 10)$, 숭고한이 가지고 간 돈 $M(0 \le M \le 1\,000)$, 대출할 수 있는 한도 $K(1 \le K \le 4)$가 공백으로 구분되어 주어진다. 둘째 줄에 과거로 돌아간 www.acmicpc.net 숭고한 contest C번 문제로 대회 당일에도 나를 괴롭혔던 문제다. 결국 대회시간에 못풀어서 후에 다시 풀게되었다. 풀이 대회때 처음에 브루트포스로 풀어야겠다고 생각했다. 그래서 재귀를 이용해 브루트포스를 시행했다. 하지만 계속해서 ㅡ틀렸고 결국 풀지못했다. 문제가 공개되고 오늘 다시 풀어보게 됐는데, 오늘은 조금 다르게 시작했었다. 문제 주인공인 .. 2022. 3. 29.

이전 1 다음

티스토리툴바