전체 글 (21) 썸네일형 리스트형 2022년 코포 정리 ● Codeforces Round #805 (Div. 3) - 2022.07.10 - 2 solve ● Codeforces Round #806 (Div. 4) - 2022.07.12 - 4 solve ● Codeforces Round #817 (Div. 4) - 2022.08.30 - 3 solve ● Codeforces Round #818 (Div. 2) - 2022.09.02 - 0 solve ● Educational Codeforces Round 135 (Rated for Div. 2) - 2022.09.08 - 2 solve ● Codeforces Round #820 (Div. 3) - 2022.09.12 - 2 solve ● Codeforces Round #823 (Div. 2) - 2022.0.. [백준 16197] 두 동전 ● 문제 : 백준 16197번 : 두 동전 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net ● 알고리즘 - 백트래킹 ● 문제 풀이 백트래킹을 이용하여 문제를 풀었다. 보드판의 정보를 입력받을 N과 M 그리고 이차원문자열벡터 arr, 처음 동전 2개의 좌표를 입력받을 coin1과 coin2, 동전을 상하좌우로 이동시키므로 이동방향을 저장하는 배열 dir, 문제의 조건에 만족하는 최소의 답을 저장하는 ans를 전역변수로 선언하고 시작한다. 처음 보드판의 정보를 입력받고, 동전의 위치를 나타내는 'o'를 입력받았다.. [백준 2630] 색종이 만들기 ● 문제 : 백준 2630번 : 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net ● 알고리즘 - 분할정복 ● 문제 풀이 입력받는 길이가 최대 128이므로 130*130 크기의 이차원 배열과 정답으로 출력할 하얀색 종이의 개수를 나타내는 white, 파란색 종이의 개수를 나타내는 blue를 선언한 후 시작한다. 가장 큰 색종이부터 차근차근 분할해가며 정답을 구한다. 현재 색종이가 모두 0으로 이루어져있다면 white를 1 증가시키고 1로 이루어져있다면 blue를 1 증가.. [백준 9663] N-Queen ● 문제 : 백준 9663번 : N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ● 알고리즘 - 재귀함수 - 백트래킹 [백트래킹] 백트래킹이란 경로를 탐색하다가 올바르지 않은 경로라면 계속해서 탐색하는 것이 아니라 이전 단계로 돌아가 다시 올바른 경로를 향해 찾아가는 알고리즘이다. 모든 경로를 탐색하는 알고리 kinngife.tistory.com ● 문제 풀이 처음에 체스판을 표현하고자 이차원 배열을 사용하였는데, 일차원 배열만으로도 문제를 해결할 수 있다는 것을 깨달았다. 입력받는 N의 크기가 최대 15이므로.. [백준 15652] N과 M (4) ● 문제 : 백준 15652번 : N과 M (4) 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ● 알고리즘 - 재귀함수 - 백트래킹 [백트래킹] 백트래킹이란 경로를 탐색하다가 올바르지 않은 경로라면 계속해서 탐색하는 것이 아니라 이전 단계로 돌아가 다시 올바른 경로를 향해 찾아가는 알고리즘이다. 모든 경로를 탐색하는 알고리 kinngife.tistory.com ● 문제 풀이 백준 15650번 N과 M (2) 코드에서 조금만 수정하면 된다. [백준 15650] N과 M (2) ● 문제 : 백준 15650번 .. [백준 15651] N과 M (3) ● 문제 : 백준 15651번 : N과 M (3) 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ● 알고리즘 - 재귀함수 - 백트래킹 [백트래킹] 백트래킹이란 경로를 탐색하다가 올바르지 않은 경로라면 계속해서 탐색하는 것이 아니라 이전 단계로 돌아가 다시 올바른 경로를 향해 찾아가는 알고리즘이다. 모든 경로를 탐색하는 알고리 kinngife.tistory.com ● 문제 풀이 백준 15649번 N과 M (1) 코드에서 조금만 수정하면 된다. [백준 15649] N과 M (1) ● 문제 : 백준 15649번 .. [백준 15650] N과 M (2) ● 문제 : 백준 15650번 : N과 M (2) 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ● 알고리즘 - 재귀함수 - 백트래킹 [백트래킹] 백트래킹이란 경로를 탐색하다가 올바르지 않은 경로라면 계속해서 탐색하는 것이 아니라 이전 단계로 돌아가 다시 올바른 경로를 향해 찾아가는 알고리즘이다. 모든 경로를 탐색하는 알고리 kinngife.tistory.com ● 문제 풀이 백준 15649번 N과 M (1) 코드에서 조금만 수정하면 된다. [백준 15649] N과 M (1) ● 문제 : 백준 15649번 .. 백트래킹 (Backtracking) 백트래킹이란 경로를 탐색하다가 올바르지 않은 경로라면 계속해서 탐색하는 것이 아니라 이전 단계로 돌아가 다시 올바른 경로를 향해 찾아가는 알고리즘이다. 모든 경로를 탐색하는 알고리즘인 DFS를 이용하지만, 조건에 맞지 않는 경로는 제외시킨다는 점에서 조금 더 효율적이다. 여기서 경로를 제외시키는 것을 가지치지(pruning)이라고 한다. 가지치기를 하기 위한 조건을 얼마나 잘 설정하느냐에 따라 시간복잡도가 천차만별이다. 백트래킹 알고리즘은 대표적으로 순열, 조합을 구하는 것에 이용된다. 1. 순열 (중복x) ● 코드 #include #include #include #include #include #include #include #include #include #include #include #includ.. 이전 1 2 3 다음
