버러범의 개발이야기

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/CANADATRIP

각 도시마다 도시에 도착하기 거리 m전에 g간격으로 표지판들이 나열되어있다. 각 도시들의 갯수와 위치가 주어지고 도시들마다의 m과 g가 주어질때 k번째 표지판의 위치를 찾는 문제이다.

전체 거리가 8030000이기 때문에 완전탐색에는 무리가 있다.

해결 방법으로는 출발점부터 도착점까지 각각을 lo와 hi로 설정하고 이분법을 이용하여 중간지점까지 갔을때 지나친 표지판의 갯수를 계산하는 것이다.

만약 계산한 표지판의 갯수가 k보다 적으면 lo를 높이고 많으면 hi를 낮추면 된다.

표지판의 갯수를 셀때는 출발점부터 해당지점까지와 각 도시들의 표지판이 놓여져 있는 영역들의 겹치는 부분을 계산해서 g로 나누고 +1 해주면 된다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/12.%20DecisonProblem/CANADATRIP.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/ARCTIC

기지들의 위치가 좌표형태로 주어진다. 무전기가 거리 D안에서 통신 가능하고 각 기지국들이 간접적으로 연락할 수 있다고 할때 모든 기지들이 통신할 수 있는 최소 D를 찾는 문제이다.

최적화 문제이지만 D가 가질 수 있는 최대 최소를 시작으로 이분법을 사용하여 범위를 줄여나가면 최적해 D를 찾을 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/12.%20DecisonProblem/ARCTIC.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

BOJ 문제 링크: https://www.acmicpc.net/problem/14503

로봇 청소기가 청소할 방에 벽과 청소가 안되있는곳을 각각1, 0으로 표현한 2차원 배열이 주워진다.

조건에 맞게 로봇청소기가 움직였을때 청소한 칸의 갯수를 출력하는 문제이다.

문제에 주어진 경우들을 switch문으로 나누어서 재귀호출하는 형식으로 문제를 해결할 수 있었다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314503.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/KAKURO2

정사각형 모양의 게임판을 주어진 힌트에 알맞게 숫자(1~9)로 채워야 하는 문제이다.

비트마스크 기법을 수월하게 다룰줄 알아야하고, 게임판과 힌트에 대한 정보들을 여러가지 2차원 배열들로 표현하여 문제를 풀여야 하기 때문에 무척 까다로운 문제였다.

어떤 정수를 비트단위로 쪼개서 부분집합을 만들때 해당 정수를 -1한 값을 해당정수와 비트연산 & 하기를 반복하면 모든 부분집합을 순회할수 있다는게 흥미로웠다. 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/11.%20CombinatorialSearch/KAKURO2.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

알고스팟 문제 링크: https://algospot.com/judge/problem/read/ALLERGY

n명의 친구들 각자가 m개의 음식중 먹을 수 있는 음식들이 입력으로 주어졌을때 한개의 음식도 먹지 못하는 친구가 발생하지 않게끔 하는 음식갯수의 최소값을 구하는 문제이다.

해결방법으로는 음식을 한개도 먹지 못하는 친구를 찾아 그 친구가 먹을 수 있는 음식을 추가하고 재귀호출 하는 방식이 있다.

이때 친구들이 문자열로 주어지기 때문에 canEat이나 eaters 같은 벡터 배열에 접근하기 어려우므로 map을 사용하여 친구들에 해당하는 문자열들을 정수형태로 바꿔서 index접근이 수월하도록 하였다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20CombinatorialSearch/ALLERGY.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

알고스팟 문제 링크: https://algospot.com/judge/problem/read/BOARDCOVER2

게임판과 블럭이 입력으로 주어졌을때, 불규칙하게 부분적으로 채워진 게임판에 회전가능한 블럭을 놓을수 있는 최대값을 구하는 문제이다.

먼저 게임판에 채워진 부분을 1, 비어있는 부분을 0으로 표현한다. 그리고 주어진 블럭을 90도로 회전시켜가며 가능한 모양들을 좌표 형태로 저장한다.

이제 게임판에 빈칸들을 찾아내서 블록을 놓을 수 있으면 놓고 재귀호출 한다.

만약에 빈칸에 놓을 수 있는 블록의 모양이 없다면 해당 빈칸을 막아놓고 재귀호출한다. 그렇지 않으면 재귀호출을 했을때, 해당 빈칸에서 또 블록을 놓을 수 있는지 없는지 다시 계산을 반복하는식으로 무한루프에 빠진다.

이때 (현재 게임판에 놓은 블럭수) + (남은 빈칸들을 블럭크기로 나눈값) 이 지금까지 찾은 최적해보다 작다면 현재 탐색이 최적해가 될 수 없으므로 탐색을 그만둔다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20CombinatorialSearch/BOARDCOVER2.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

BOJ 문제 링크: https://www.acmicpc.net/problem/9251

두 수열이 주어졌을때, 모두의 부분 수열이 되는 수열 중 가장 긴 것(LCS)을 찾는 문제이다.

두 수열을 순회하면서 두 수열중 하나가 다음 문자로 넘어가거나, 두 수열을 가르키는 문자가 서로 같으면 LCS에 추가하고 둘다 다음 문자로 넘어가는 재귀 호출을 하면서 가장 큰 값을 리턴하는 경우를 찾는다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%239251.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/2812

N자리 숫자가 주어졌을때, K개의 숫자를 지워서 얻을 수 있는 가장 큰 수를 구하는 문제이다.

문제 유형은 그리디였지만 덱을 이용하면 문제를 쉽게 풀 수 있어서 자료구조의 중요성을 더 깨닫게 되었다.

먼저 주어진 숫자들을 순회하면서 현재 숫자가 덱에 있는 숫자보다 크면 덱에 있는 숫자들을 꺼내고 해당 숫자를 넣는다. 얼핏보면 스택구조를 이용해서도 문제를 풀 수 있을거 같지만 마지막에 삭제하고 남은 숫자들을 출력하는 과정에서 스택으로 치면 맨 밑에 있는 숫자부터 출력 해야하기 때문에 덱 구조가 더 문제에 적합하다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%232812.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!