2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 삼성 SW역량테스트 A형에 나왔던 문제이다. 전형적인 브루트포스 문제!! 이 문제를 풀 때 고민했던게 궁수의 위치 조합은 DFS로 금방 되겠는데 적의 위치 탐색은....? 첫번째 구현할 때는 한 칸씩 이동할 때 마다 BFS로 탐색을 한 뒤 1. 거리, 2. x좌표 순으로 정렬을 했었다 그그런데 왠지 시간낭비같아서 그냥 아예 처음에 궁수별로 적의 모든 좌표에 대해 거리와 x좌표 순으로 정렬하고, 시간이 지날 ..

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1) (1, j)는 ( www.acmicpc.net 이것도 역량테스트 기출인 단순 구현문제다 원판돌리기를 비롯한 많은 회전 문제들은 실제로 회전하지 않아도 인덱스를 활용하면 아주 깔..

https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 www.acmicpc.net 삼성 역량테스트 기출문제이면서, 주어진 요구사항대로 코딩하면 되는 단순 구현문제이다. 이 때, 문제에 명시되어 있는 조건들을 헷갈리..

대표적인 백트래킹 문제인 N-Queen( https://www.acmicpc.net/problem/9663 ) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 크기가 N*N인 체스판에 퀸 N개를 서로 공격할 수 없게끔 놓을 수 있는 방법의 수를 구하는 문제 퀸이 무조건 N개가 놓여야 하기 때문에 같은 열이나 같은 행에는 절대 퀸이 같이 올 수 없다 이렇기 때문에 나는 move 함수와 func 함수를 만들었는데, move 함수는 좌표를 인자로 넘겨받아 그 좌표에서의 퀸의 이동경로를 체크하고 이동가능한 칸의 수를 반환 func ..

https://www.acmicpc.net/problem/15353 15353번: 큰 수 A+B (2) 첫째 줄에 A와 B가 주어진다. (0 < A,B < 1010000) www.acmicpc.net 단순히 a+b를 계산하면 되는 문제이지만, a와 b의 범위가 정수형 자료형이 저장할 수 있는 범위를 한~참 넘기 때문에 일반적인 더하기 기호를 쓰면 안된다. 대신에 아주 고전적인 더하기 방법을 사용해야 함 ㅎㅎ 각각의 숫자를 문자열에 저장하고, 맨 마지막 숫자부터 더하기 연산을 해준다 각 자리수의 덧셈 결과가 10 이상이면 다음 자리수에 +해주기 두 숫자의 자리수가 각각 다른 경우까지 고려해줘서 조건을 추가해줘야 한다 #include #include int main() { int n1, n2, idx=0, ..

BFS 혹은 DFS 입문자가 풀면 좋을 기초 문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 방향 그래프가 주어졌을 때, 임의의 정점 (i,j)의 경로 조합을 인접행렬을 사용해서 출력하는 프로그램 bfs의 핵심은, ① 큐를 사용한다 ② 이동 가능하다면 바로 방문 체크 인데, BFS를 잘 모르는 초심자가 풀기 좋은 문제라고 생각한다. #include #include #include using namespace std; int n; bool g[101][101], visit[101];..

https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다. x번째 에너지 구슬을 제거한다. Wx-1 × Wx+1의 에너지를 모을 수 있다. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다 www.acmicpc.net 난이도 쉬운 백트래킹 문제이다 백트래킹 문제의 특성은 주로 두 가지인데 ① 조합&완탐을 이용한다 ② 재귀함수를 이용하여 함수 호..

https://www.acmicpc.net/problem/17254 17254번: 키보드 이벤트 첫째 줄에 연결된 키보드의 개수 N과, 키보드를 누르게 될 횟수 M이 주어진다. (1 ≤ N, M ≤ 1,000) 다음 M개의 줄에 정수 a, b와 문자 c가 주어진다. 이는 a번 키보드로, b초에 문자 c가 적힌 키를 누를 것이라는 의미이다. (1 ≤ a ≤ N, 0 ≤ b ≤ 1,000,000) 키보드에는 알파벳 대문자와 숫자키만 존재한다. www.acmicpc.net 문제는 길지만, 정렬을 응용하여 풀 수 있는 간단한 문제였다 입력은 키보드 넘버 N, 키보드 입력 횟수 M과 각 M개의 입력에 대한 A번 키보드로 B초에 문자 C가 적힌 키를 누를 때, 화면에 출력될 글자는? 우선순위는 시간>키보드번호(오름..