■ 알고리즘 문제 풀이/BOJ (48) 썸네일형 리스트형 [BOJ] 백준 1074. Z ▶문제설명[BOJ] 백준 1074. Zhttps://www.acmicpc.net/problem/1074 ▶ 설계문제에서 주어진 그림을 관찰해보자. N이 2인 경우 순회하는 순서를 나타내는 그림이다. 변의 길이가 2^2 = 4이다. 4등분하여 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단을 순서대로 방문해야한다.즉, 변의 길이가 2^N인 사각형을 더이상 등분하지 못할 때까지 4등분할 수 있는지를 묻는 문제이다. 변의 길이가 2^N인 사각형을 가능한 한 4등분해서 Z가 시작되는 위치의 좌표와 변의 길이를 2로 나눈 값을 인자로 넣어서 재귀호출 하면 될 것으로 보인다. 규칙을 파악했다면 N이 3인 경우에는 어떻게 되는지 그려보자. 편의상 같은 숫자가 적힌 것으로 붙여넣었지만, 오른쪽 상단은 16~31, .. [BOJ] 백준 2447. 별 찍기 - 10 ▶문제설명[BOJ] 백준 2447. 별 찍기 - 10https://www.acmicpc.net/problem/2447 ▶ 설계별이 찍힌 모습에서 규칙을 찾을 수 있다. N이 3인 경우 N이 9인 경우 N이 27인 경우 규칙이 보이는가? 잘 안보인다면 아래의 그림을 보자. N에 따라서 균등하게 9등분을 해보면 가운데 부분만 비어있는 모습을 볼 수 있고, 각 등분된 조각을 또 9등분 해보면 가운데 부분만 비어있는 것을 볼 수 있다. 더 이상 범위를 나눌 수 없을 때까지 나누면서 가운데 부분을 제외하고 재귀호출하면 문제를 해결할 수 있을 것으로 보인다. ▶ 구현우선 메인문을 작성해보자. 12345678910111213141516int main(){ scanf("%d",&N); for(int i=0; i [BOJ] 백준 1654. 랜선 자르기 ▶문제설명[BOJ] 백준 1654. 랜선 자르기 https://www.acmicpc.net/problem/1654 ▶ 설계현재 K개의 랜선이 있는데 가지고 있는 랜선들을 일정한 길이로 잘라서 N개의 랜선으로 만들어야한다. 랜선을 N개 이상으로 만들 수 있는 랜선 길이의 최대값을 구하는 문제이다. 랜선 길이 len을 먼저 정하고 해당 길이로 N개 이상의 랜선을 만들 수 있는지 판단하는 방식으로 문제를 해결할 수 있을 것으로 보인다. len의 길이는 이분탐색으로 값을 정해주면 빠른 시간에 문제를 해결할 수 있게 된다. left는 가능한 랜선 길이의 최소값, right는 가능한 랜선 길이의 최대값으로 초기화 한다. 그리고 (left+right)/2에 해당하는 mid 값으로 N개 이상의 랜선을 만들 수 있는지 .. [BOJ] 백준 15683. 감시 ▶문제설명[BOJ] 백준 15683. 감시 https://www.acmicpc.net/problem/15683 ▶ 설계NxM 크기의 사무실에 K개의 CCTV가 설치되어있다. (1 [BOJ] 백준 17143. 낚시왕 ▶문제설명[BOJ] 백준 17143. 낚시왕https://www.acmicpc.net/problem/17143 ▶Hint[삼성전자 상시 SW역량테스트-A형] 시뮬레이션 문제이다. 1. 낚시왕을 오른쪽으로 한칸 이동시킴2. 상어를 낚음3. 상어들이 움직임 1~3 과정을 C번(문제에서 주어진 열의 크기만큼) 수행하면 답을 구하게 되는 문제이다. 상어 구조체를 만들고 상어들의 상태와 위치를 2차원 배열로 관리했다. 3번에서 상어들이 움직일 때 예를 들어, 상어의 속력이 5인 경우 5번에 걸쳐 이동시키면서 매번 상어가 범위를 벗어났는지 파악하여 상태를 변경하는 방법으로 구현했다. 문제 해결에 있어 핵심이 되는 부분에 대해 설명하고자 한다. [구조체 선언]1234struct Shark { int s, d, z;}.. [BOJ] 백준 17471. 게리맨더링 ▶문제설명[BOJ] 백준 17471. 게리맨더링 https://www.acmicpc.net/problem/17471 ▶Hint 조합과 DFS를 이용한 부르트포스 문제이다. 문제 해결에 핵심이 되는 두 부분에 대해 설명하고자 한다. 1. 구역 번호 1~N을 두 개의 선거구로 나눈다.[구역 번호를 두 개의 선거구로 나누는 모든 경우의 수]구역 번호 1~N에서 1개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-1개를 선거구 B라고 한다. (nC1가지 경우) 구역 번호 1~N에서 2개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-2개를 선거구 B라고 한다. (nC2가지 경우) 구역 번호 1~N에서 3개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-3개를 선거구 B라고 한다. (nC3가지 경.. [BOJ] 백준 16234. 인구 이동 ▶문제설명[BOJ] 백준 16234. 인구 이동 https://www.acmicpc.net/problem/16234 ▶Hint DFS, 시뮬레이션 문제이다. 인구 이동이 일어났다는 것은 한 시점에 인구 수 변동이 한 번 이상 있었다는 것을 의미한다. 한 번에 모든 연합이 동시에 인구이동을 실시하기 때문에 순차적으로 인구이동을 시키지 않도록 주의한다. [입력]3 5 10 10 15 20 20 30 25 40 22 10이런 입력이 들어왔다고 했을 때 인구 이동이 한 번 일어난 뒤의 상태는 아래와 같다. 20 20 20 20 20 20 40 20 10 ▶SolutionDFS 알고리즘을 이용해 각 연합의 전체 인구 수와 연합을 이룬 칸의 개수를 구해서 평균 값을 구한다. DFS를 수행하면서 좌표 값을 저장해두면.. [BOJ] 백준 1722. 순열의 순서 ▶문제설명[BOJ] 백준 1722. 순열의 순서 https://www.acmicpc.net/problem/1722 ▶Hint 조합론 & DP 문제이다. 입력으로 주어지는 N의 범위가 최대 20이다. 20! = 2,432,902,008,176,640,000 따라서 브루트포스로 접근할 경우 TLE가 발생하며, 결과 값이 int 자료형 범위를 넘어간다. 문제를 해결함에 있어서 중요하게 봐야 할 조건은 순열이 사전 순으로 정렬되어 있다는 것이다. 이 조건 덕분에 우리는 모든 경우를 확인해보지 않고도 K번째 순열을 찾아내거나 주어진 순열이 몇 번째 순열인지를 알아낼 수 있다. N이 4인 경우를 예로 들어보겠다. 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2.. 이전 1 2 3 4 5 6 다음
