BOJ
BOJ 1918 · 후위표기식
알고리즘 분류 : 스택 스택(Stack) 자료구조를 사용하는 전형적인 문제이다. 컴퓨터 과학 전공의 '자료 구조'를 수강하면, 스택을 배우면서 한 번쯤은 후위표기식을 구현해볼 것이다. 때문에 이 문제는 중위표기법을 후위표기법으로 바꾸는 방법을 알면 비교적 쉽게 해결할 수 있다. 중위표기법(infix)은 피연산자A - 연산자 - 피연산자B 순으로 표현한다. 예를 들면, A+B, A+B*C, (A+B)*(C-D) 이다.후위표기법(postfix)은 피연산자A - 피연산자B - 연산자 순으로 표현한다. 예를 들어, AB+, ABC*+, AB+CD-* 이다.후위표기법은 연산자 우선순위 순서대로 수식을 표현하기 때문에, 괄호 ( )가 필요 없다.중위표기법에서 후위표기법으로 바꾸는 방법은 다음과 같다.연산자를 저장할..
BOJ 10825 · 국영수
알고리즘 분류 : 정렬 여러 개의 변수가 있는 리스트를 정렬해야 하는 문제다. 이 문제의 경우 국어, 영어, 수학, 이름 순서로 우선순위를 정해서 정렬해야 한다. 크게 두 가지의 방법으로 해결할 수 있다. 우선순위를 따진 연산자 오버로딩을 통한 정렬, 그리고 Set을 이용한 정렬이다. C++의 경우, struct로 여러 개의 변수를 받고, 각 변수에 대한 우선순위를 정해서 연산자 오버로딩을 하여 정렬할 수 있다.C++의 경우, tuple과 set을 활용하여 간단히 구현할 수도 있다.Python의 경우, 변수의 입력 순으로 우선순위를 따져서 자동으로 정렬해준다.오름차순인지 내림차순인지만 잘 정하면 된다. 기본적으로 정렬 함수가 오름차순으로 작동하므로, 내림차순은 원소를 음수로 처리하면 간편하다. C++ 소..
BOJ 15778 · Yut Nori
알고리즘 분류 : 시뮬레이션 윷놀이 게임을 프로그래밍해야 하는 문제다. 문제에 주어진 조건 그대로 구현해야 한다. 서브태스크 순서대로 설계하면 도움이 된다. 우선 윷놀이 판에 대한 좌표를 분석하는 것이 좋다.말이 놓이는 칸은 일정한 규칙을 가지고 있다. 가장 자리 라인은 6의 배수, 대각선 라인은 5의 배수이다좌표를 (X, Y)라고 했을 때, 규칙은 아래와 같다.↑(X, 30) | ←(0, Y) | ↓(X, 0) | →(30, Y) | ↙(X != Y) | ↘(X == Y)말이 꺾이는 지점인 (0, 30), (0, 0), (15, 15)은 별도로 처리하는 것이 좋다.각 말을 판에 놓을 때는, Aa (X, Y), Bb (X, Y+1), Cc (X+1, Y), Dd (X+1, Y+1)로 두면 된다.A, B,..
BOJ 15653 · 구슬 탈출 4
알고리즘 분류 : BFS 구슬 탈출 시리즈의 네 번째 문제다. '구슬 탈출 2'에서 10번 이동 제한만 없애주면 된다. 자세한 구현 방법은 이전 문제 참조. C++ 소스코드 #include #include using namespace std; struct bead { int rx, ry, bx, by, d; }; int n, m; char a[10][10]; bool check[10][10][10][10]; queue q; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void move(int &x, int &y, int &c, int dx, int dy) { while (a[x+dx][y+dy] != '#' && a[x][y] != 'O') { x +=..
BOJ 15644 · 구슬 탈출 3
알고리즘 분류 : BFS 구슬 탈출 세 번째 문제다. 이전 문제인 '구슬 탈출'과 '구슬 탈출 2'를 해결했으면, 조금만 추가해서 풀 수 있다. 자세한 내용은 이전 문제 참조. 이 문제가 구슬 탈출 시리즈 중에선 가장 까다롭다. 움직인 방향을 출력해야 하기 때문이다. 움직인 방향을 출력하기 위해서는 이전 위치를 저장하는 배열이 필요하다.빨간 구슬 X, Y좌표, 파란 구슬 X, Y 좌표, 방향 정보를 가진 path 배열을 4차원으로 선언한다.현재 위치에서 이전 위치와 이동 방향을 저장하고, 이 과정을 움직일 때마다 수행한다.빨간 구슬이 구멍에 빠져서 답을 낼 수 있을 경우, 현재 위치에서 이전 위치로 되돌아가면서 방향을 저장한다.방향을 마지막에서 처음으로 되돌아가는 것이므로, 역으로 출력한다. C++ 소스..
BOJ 13460 · 구슬 탈출 2
알고리즘 분류 : BFS 구슬 탈출 시리즈 두 번째 문제다. 첫 번째 문제인 '구슬 탈출'을 풀었으면, 이 문제는 쉽게 해결할 수 있다. 출력값만 바꾸면 된다. 자세한 내용은 이전 문제 참조. 10번 이하로 탈출 실패 시, -1을 출력한다.탈출 성공 시, 움직인 횟수를 출력한다. C++ 소스코드 #include #include using namespace std; struct bead { int rx, ry, bx, by, d; }; int n, m; char a[10][10]; bool check[10][10][10][10]; queue q; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void move(int &x, int &y, int &c, in..
BOJ 13459 · 구슬 탈출
알고리즘 분류 : BFS 보드 위에 빨간 구슬과 파란 구슬이 있고, 빨간 구슬만 구멍으로 빠뜨리는 문제다. 구슬 탈출 문제 시리즈는 이 문제를 포함하여, 총 4문제이다.파란 구슬이 구멍에 빠져서는 안되고, 파란 구슬과 빨간 구슬이 동시에 빠져서도 안 된다. 또한 빨간 구슬과 파란 구슬이 동시에 움직이고, 굴리면 벽에 부딪힐 때까지 굴러간다. 구슬 2개가 동시에 움직이기 때문에 4차원 배열을 통해 방문 여부를 체크해주면 편하다. Queue에 빨간 구슬의 (X, Y) 좌표, 파란 구슬의 (X, Y) 좌표를 모두 넣는다.방문 여부를 확인할 check 배열을 4차원 배열로 선언한다. 배열의 인덱스는 [빨간 X좌표] [빨간 Y좌표] [파란 X좌표] [파란 Y좌표] 이다.구슬을 굴릴 때, 구슬의 다음 위치가 벽(#..
BOJ 15657 · N과 M (8)
알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 비내림차순으로 M개를 뽑는 문제다. N과 M (4) 문제의 소스코드를 수정하면 된다. C++ 소스코드 #include #include #include using namespace std; int n, m; int a[8]; vector v; void solve(int index, int cnt) { if (cnt == m) { for (auto k : v) printf("%d ", k); printf("\n"); return; } for (int i=index; i