분류 전체보기
-
[백준/BOJ] 3190번 뱀 (C++)알고리즘 문제풀이/백준 2020. 12. 4. 17:23
www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 삼성 역량 테스트 기출 문제 : 시뮬레이션(구현) 시간이 지남에 따라 바뀌는 뱀 머리 x좌표와 y좌표를 배열에 기록하는 것이 포인트인 문제입니다. 이때 시간을 뱀 꼬리 인덱스로 두어 뱀이 사과를 먹지 못할 때 뱀 꼬리 인덱스로 이전의 머리 좌표에 접근하여 꼬리가 위치한 칸을 비워줄 수 있습니다. #include using namespace std; const int MMAX = 102; const int CMAX = ..
-
[백준/BOJ] 15686번 치킨 배달 (C++)알고리즘 문제풀이/백준 2020. 12. 3. 17:11
www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 삼성 역량 테스트 기출 문제 : DFS(조합) + 시뮬레이션(구현) DFS를 이용하여 조합을 잘 얻어낼 수 있다면 구현도 까다롭지 않아서 어렵지 않게 해결할 수 있는 문제입니다. (next_permutation으로도 조합을 구할 수 있습니다.) 1. 전체 치킨가게의 수에서 m개를 정하는 조합을 구한다. 2. 해당 조합에서 치킨집과 집의 치킨 거리(최소 거리)를 구한다. 3. 이를 더한 값이..
-
[백준/BOJ] 1764번 듣보잡 (C++)알고리즘 문제풀이/백준 2020. 12. 1. 14:04
www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net map 자료구조를 이용하는 쉬운 문자열 문제입니다. 이름을 key값, 이름이 나오는 수를 value로 설정합니다. n과 m만큼 반복문을 돌려 입력받은 문자열을 map의 key로 둬 값을 증가시키고, 이름이 2번 이상 나온경우 듣보잡이므로 해당 값을 벡터에 넣어 정렬 후 출력하면 간단하게 해결할 수 있습니다. #include #include #include using namespace std; int main(..
-
[백준/BOJ] 1941번 소문난 칠공주 (C++)알고리즘 문제풀이/백준 2020. 12. 1. 13:48
www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 새롭게 알게된 점 십자가 모양은 일반적인 DFS + 백트래킹으로 문제를 해결할 수 없다. DFS와 BFS를 같이 쓰는 문제가 존재한다. (이번 문제가 그러했음) 문제를 해결하는 순서는 다음과 같습니다. 1. 학생 25명중 7명을 선택하는 조합을 DFS를 통해 구하기 2. 해당 조합에서 다솜이파 학생이 4명 이상인지 확인하는 isMoreThanFour() 함수 구현 3. 해당 조합에서 선택된 학생이 인접한지 확인하는..
-
[백준/BOJ] 9663번 N-Queen (C++)알고리즘 문제풀이/백준 2020. 11. 30. 22:38
www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 전형적인 DFS + 백트래킹 문제 하나의 행에 퀸을 하나만 넣을 수 있으므로 열마다 퀸을 넣어보고 현재 위치를 기준으로 위, 왼쪽 위 대각선, 오른쪽 위 대각선을 검사합니다. 행이 n에 도달할 때 마다 하나의 경우의 수가 완성되므로 answer 값을 더해줍니다. #include using namespace std; int n,res; bool map[15][15]; bool isPossible(int row, int col) ..
-
[백준/BOJ] 1799번 비숍 (C++)알고리즘 문제풀이/백준 2020. 11. 30. 22:14
www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 난이도 높은 DFS + 백트래킹 문제 처음에 N-Queen 문제처럼 접근했는데 시간초과가 발생했습니다. 시간초과가 발생하는 이유는 입력받은 값이 전부 1일 때 최악의 경우 2^10*10의 시간복잡도를 가질 수 있기 때문이라고 합니다. 따라서 이 문제를 해결하기 위해서는 체스판의 검은 칸, 흰칸을 나누어 DFS를 진행하는 것입니다. 그러면 시간 복잡도가 2^5*5+2^5*5로 확연히 줄어듭니다. 이러한 접근법을 생각해내는..
-
[백준/BOJ] 17071번 숨바꼭질 5 (C++)알고리즘 문제풀이/백준 2020. 11. 29. 13:30
www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 굉장히 난이도가 있는 BFS 문제, 일반적인 BFS 접근으로는 위의 문제를 해결할 수 없습니다... 문제를 해결하기 위한 포인트는 수빈이가 짝수초에 접근한 위치는 짝수초에 또 방문할 수 있고, 홀수초에 접근한 위치는 홀수초에 또 방문할 수 있다는 것입니다. 그러므로 현재 수빈이의 위치를 중심으로 시간이 지날 때 마다 몇초에 해당 위치를 최초로 방문하게 되는지 기록하고, 시간..
-
[백준/BOJ] 13913번 숨바꼭질 4 (C++)알고리즘 문제풀이/백준 2020. 11. 29. 13:29
www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기존 숨바꼭질 문제에 최소 시간이 걸리는 경로의 기록까지 구해야하는 문제입니다. 경로를 기록하기 위해서 배열 record를 선언하였고, 큐가 진행될때 마다 다음 위치에 이전 위치가 기록됩니다. 수빈이가 동생을 만나면, traceBack() 함수를 통해 현재 수빈의 위치에서 부터 처음 위치까지 역으로 추적하도록 구현했습니다. #include #include #include #in..