N명의 사람을 두 팀으로 나눈다. 두 사람이 같은 팀을 할 때 발생하는 능력치가 데이터로 주어지고, 그 능력치의 총합이 한 팀의 능력치가 된다. 그 때, 양 팀의 능력치 차이가 최소가 되는 경우를 구하고 그때의 값을 출력하는 문제이다. 양 팀이 N/2 명의 선수를 구성하는 모든 경우의 수에 대해 검사하고, 최솟값을 갱신하는 방법을 생각했고, DFS로 선수를...
일반적으로 알고 있는 사다리 게임에 대한 정보를 배열로 주고 사다리를 추가해서 입구와 출구가 같도록 만드는 최소 사다리의 개수를 구하는 문제이다. 사다리의 개수가 4개 이상인 경우는 무시하기 때문에 3개의 사다리를 놓는 모든 경우의 수에 대해 DFS로 탐색하면 되는 문제이다. (머리로는 이해하는데 구현이 쉽게 안되서 na982님의 동영상 강의를 통해 배웠다...
NxM 범위의 자리 중 테트로미노 하나를 알맞게 놓았을 때 놓인 자리값들의 합의 최댓값을 찾아라. 테트로미노 모양과 자리에 따른 모든 경우를 본다. (완전탐색) 이 문제는 ㅗ 모양과 나머지를 구분하여 푸는 것이 포인트인 것 같다. 나머지 모양들은 DFS탐색을 통해 모두 탐색할 수 있기 때문에 ㅗ모양만 따로 계산해주면 간단히 풀린다. //ㅗ 모양을 계산하는 ...
연구소 문제는 지도가 N x M 크기로 주어지고, 0은 안전영역, 1은 벽, 2는 바이러스이며 바이러스는 벽으로 막혀 있지 않은 모든 공간으로 퍼진다고 할 때 벽을 3개만 세울 수 있다고 한다면, 안전영역의 크기가 가장 클 때의 값은 얼마인가를 구하는 문제이다. 나는 DFS를 통해 벽 3개를 세울 수 있는 모든 경우의 수를 만들고, BFS로 바이러스를 퍼뜨...
4월 6일 (토) 에 치뤄진 삼성 S/W 상시테스트 A형 문제의 복기 문제라고 한다. N+1 행에 위치한 궁수 3명이 죽일 수 있는 적의 최대 수를 찾는 문제이다.주어진 값으로는 행과 열의 크기(N, M), 궁수의 사정거리(D) 이다. 먼저 DFS를 이용한 조합으로 궁수의 위치를 정해주고, BFS+시뮬 로 구현하여 턴을 진행한다.따로 2차원 배열을 사용하지...
등산로를 만드는 규칙에 따라 만들 수 있는 가장 긴 등산로를 찾는 문제이다. 등산로를 만드는 규칙① 등산로는 가장 높은 봉우리에서 시작해야 한다.② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다. 즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다. ③ 긴 등산로를 ...
김프로가 1년 동안 각 달의 이용 계획을 수립하고,가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾는 문제이다.(1일 이용권/1달 이용권/3달 이용권/1년 이용권이 있다.) DFS를 통해 이용권을 쓰는 모든 경우에 대해 탐색하고, 각 경우마다 이용권 가격의 합을 계산하면 된다. 테스트 케이스 49/50 에서 잠깐 헤맸는데, 3달 이용권보다 1달 이용권...
보자마자 BFS 느낌이 나서 바로 탐색을 했는데, 터널 구조물에 따라 통과가 안되는 경우가 발생했다. 이걸 효율적으로 처리해주는 방법이 생각이 안나서 if문을 남발했는데 일단 pass는 받아냈다. 근데 더 효율적인 방법이 있을 것으로 보인다. +) 다른 블로그를 참고하니, DFS로 푸는게 더 깔끔하게 보이는 듯 하다.
나중에 다시 푼다!
DFS와 시뮬레이션을 활용하는 문제이다. 보자마자 어떻게 풀 지 생각이 나서 쉽게 풀 줄 알았는데생각보다 너ㅓㅓ무나도 오래 걸렸다. DFS로 계단을 고르는 모든 경우의 수를 골라주고, 각 경우마다 모두 식당으로 내려오는 시간을 계산했다.
개인적으로 극한의 시뮬레이션 경험이었다. 사실 주어진 조건대로 차근차근 따라가다보면 풀 수 있는 문제이기도 하지만, 구현력이 부족한 내가 풀기엔 조금 부족했다. 다른 분의 블로그를 참고해서 해결했더니 찜찜하다. 나중에 다시 풀어야지.
DFS를 활용하여 약품을 넣는 모든 경우에 대해 탐색하고,백트래킹으로 계산하는 값이 현재의 최솟값을 넘을 경우 가지치기를 했다. 성능검사를 하는 부분을 비효율적으로 짜니까 자꾸 시간초과가 떠서 결국 다른 블로그를 참고했다.
프로그래밍 공부 중인 학생입니다.
자유로운 창작이 가능한 기본 포스트
소장본, 굿즈 등 실물 상품을 판매하는 스토어
정기 후원을 시작하시겠습니까?
설정한 기간의 데이터를 파일로 다운로드합니다. 보고서 파일 생성에는 최대 3분이 소요됩니다.
포인트 자동 충전을 해지합니다. 해지하지 않고도 ‘자동 충전 설정 변경하기' 버튼을 눌러 포인트 자동 충전 설정을 변경할 수 있어요. 설정을 변경하고 편리한 자동 충전을 계속 이용해보세요.
중복으로 선택할 수 있어요.