본문 바로가기
반응형

전체 글110

[BOJ 15649] N과M(1) (C++) www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 구현 방법 N과M(1)은 백트래킹을 연습할 수 있는 N과 M시리즈 중 첫 번째 문제입니다. 1부터 N까지 자연수 중, 중복 없이 M개를 고른 수열을 출력해야합니다. 이를 위해 1부터 N까지 탐색하는데, 만약 현재 탐색하는 숫자가 이전에 사용됐으면 스킵하고, 사용하지 않았으면 answer배열에 추가시켜줍니다. 탐색을 하다가, 출력할 개수인 m번 진행되면, answer배열에 들어있는 m개의 원소를 모두 출력해주고.. 2021. 5. 11.
[BOJ 1182] 부분수열의 합 (C++) www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 구현 방법 이 문제는 백트래킹 알고리즘을 적용해야 하는 문제였습니다. 문제의 예제처럼 숫자가 [-7, -3, -2, 5, 8] 이 주어지면, 첫 번째 원소부터 총합으로 더할지 말지 선택하며 차례대로 뻗어나가는 알고리즘입니다. 다음 사진은 백준 문제의 예를 알고리즘에 적용한 설명을 하는 사진입니다. 노드의 값은 탐색하면서 만들어내는 총합을 표시하고, 입력된 수열의 첫번째 원소를.. 2021. 5. 11.
[BOJ 9663] N-Queen (C++) www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 구현 방법 N-Queen 문제는 전형적인 백트래킹 문제입니다. 백트레킹이란 탐색을 진행하면서, 답이 될 수 없는 경우에 도착하면, 다시 되돌아가 다른 경우를 수행하는 탐색 기법입니다. N-Queen 문제에서는 n x n 체스판에 n개의 퀸을 서로 공격하지 않게 두는 경우의 수를 출력하는 문제입니다. 이 문제에서 퀸 같은 경우에는 가로, 세로, 대각선 모두 공격할 수 있으므로, 만약 새로 퀸을 놓으려는 자리가 이전에 있었던 퀸의.. 2021. 5. 10.
[BOJ 1463] 1로 만들기 (2가지 풀이/DP/BFS) (C++) www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 구현 방법 (DP 풀이) 이 문제는 전형적인 DP(Dynamic Programming) 문제입니다. DP문제를 해결하는 순서는 다음과 같습니다. 테이블 정의하기 점화식 찾기 초기값 정하기 이 문제에서 위 순서를 따라 답을 찾아보겠습니다. 테이블 정의하기 이 문제에서 테이블은 "D [i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값"이라고 정의할 수 있습니다. 테이블이란 이 문제에서 사용할 배열과 배열에 들어가는 각 값들의 의미입니다. 즉, 배열 d의 i번째에 들어가는 값은, i를 1로 만들기 위해 필요한 연산 .. 2021. 5. 1.
[BOJ 5904] Moo 게임 (C++) www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 구현 방법 처음에 이 문제를 봤을 때, 재귀를 통해 moo수열 문자열을 만들어서, 입력한 n 번째의 알파벳을 출력하면 되는 줄 알았습니다. 재귀를 통해 Moo 수열을 구현하는 코드를 성공적으로 짜고 기뻐하면서 제출했을때, 결과는 메모리 초과였습니다. 생각해보니 입력 n은 최대 1억 까지 가능한데, 길이가 1억인 수열을 구하려면 재귀를 너무 많이 돌아야 돼서 메모리 초과가 날 .. 2021. 4. 30.
[BOJ 2798] 블랙잭 (C++) www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 구현 방법 이 문제는 쉬운 편에 속하는 완전 탐색(Brute Force) 문제입니다. 완전 탐색에 익숙하지 않아 문제를 해결하는데 고민을 좀 했습니다. 구현 방법은 다음과 같습니다. 3중 for문을 돌면서, n개의 카드 숫자 중 가능한 모든 조합으로 합을 구한다. 그 합이 목표 점수, 즉 m 보다 작거나 같으면, pair 을 저장한다. m-총합의 절댓값, 즉 목표 점수와의 차이가.. 2021. 4. 29.
[BOJ 2437] 저울 (C++) www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 구현 방법 이 문제를 해결하기 위해 긴 시간 고민하다가, 도저히 풀이 방법이 떠오르지 않아 검색을 해서 풀이 방법을 검색해본 문제입니다. 그리디 문제인 것도 알겠고, 정렬을 해서 어떻게 하면 될 것 같았는데 결국 해답을 찾지 못했습니다. 제가 찾은 방법은 다음과 같았습니다. 입력받은 원소를 오름차순으로 정렬하고, 첫 번째 원소부터 더해 주는 누적합을 계산합니다. 누적합을 계산해 나가다가 다음 원소가 누적 합보다 크면 (누.. 2021. 4. 21.
[BOJ 3190] 뱀 (C++) www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 구현 방법 1) 뱀 표현 뱀을 표현하기 위해 큐(Queue) 자료 구조를 사용했습니다. 뱀이 몸길이를 늘려 머리를 다음칸에 위치 시킬때 하나 push 해서 queue를 늘립니다. 만약 해당 칸에 사과가 있었다면 꼬리 이동을 하지않고, 빈칸이면 꼬리를 없애주는 pop을 해줍니다. 머리를 놓은 새로운 자리에 2 라고 뱀을 표기해주고, 꼬리가 사라지는 자리에는 0을 넣어주며 arr배열에 뱀의 몸통 표시를 해주었습니다. 2).. 2021. 4. 12.
[BOJ 14503] 로봇 청소기 (C++) www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 구현 방법 이 문제는 구현 문제였습니다. 문제에 주어진 로직대로 구현하면 되는 문제였습니다. 단 결정적인 아이디어를 떠올린 부분은 다음과 같습니다. 2번의 a번 조건과 b번 조건에서 현재 보고 있는 방향의 왼쪽 칸을 탐색합니다. 문제에 주어진 조건에 의하면 0 = 북쪽(상), 1 = 동쪽(우), 2 = 남쪽(하), 3 = 서쪽(좌) 입니다. 좌측을 구하는 방법은 ( 현재 바라보는 방향 + 3 ) % 4 입니다.. 2021. 4. 9.
[BOJ 7562] 나이트의 이동 (C++) www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 구현 방법 이 문제의 분류는 BFS입니다. BFS문제는 보통 상, 하, 좌, 우로 움직이는데, 이 문제는 나이트의 이동 방식으로 8가지 방법을 확인해야 합니다. 로직 자체는 BFS와 동일하지만, 이동 방향을 8가지로 한다는 차이점 뿐입니다. 보통의 BFS는 이동을 위해 다음과 같은 배열을 선언합니다. int dx[4] = {1, 0, -1, 0} int dy[4] = {0, 1, 0, -1} 하지만 나이트의 이동.. 2021. 4. 9.
반응형

티스토리툴바