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 ..

저번 글에 이어서 PS를 처음 시작하는데에 도움이 되는 팁들을 적는다 PS의 입문에는 입출력에 대해 잘 아는것이 매~~~~~~~~~~~~~우 중요하기 때문에 오늘은 입력을 받는 법에 대해서만 쓰겠다 입력 받는법에도 알아야할게 넘 많기 때문😄 개인적으로는 BOJ의 그대로 출력하기 문제를 풀 수 있다면 입력은 어느정도 숙달된 실력이라고 생각한다 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시작하지 않고, 공백으로 끝나지 않는다. www.acmicpc.net 알고리즘 문제의 입력방법은 크게 두 가지로 나뉜다 입력의 개수가 주어..

알고리즘 문제풀이를 제대로 시작한 지 1년도 안된 초보지만, 그래도 누군가의 시작을 도울 만큼만은 알고 있다고 생각해서 글을 썼다 요즘 기업의 입사테스트에서 알고리즘 코딩 테스트는 거의 필수이고 대회도 많이 열리기 때문에 그 중요성만은 잘 알고 있으리라 생각한다 신입생이라면 술자리에서 선배들이 알고리즘의 중요성과 족같음을 여러 번 언급했을 테니.. 하지만 생각보다 내 주위에는 알고리즘 중요한 거 너무 많이 들었고 해야 된다고 생각은 하는데, 그래서 어떻게 시작해야 되는데?를 모르는 사람이 너무 많았다 아직까지도 과거에 아무것도 몰랐던 내가 헤맸던 것을 위주로 글을 써보려고 한다 가장 접근성이 좋으면서 유명한 사이트는 백준 온라인 저지 BOJ(https://www.acmicpc.net/) 인데 Baekjo..

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];..