본문 바로가기

프로그래밍/PS

 (80)
[C++] 백준 2630번: 색종이 만들기 문제 바로가기 처음 이 문제를 풀 때는 재귀함수를 사용하지 않으려고 했다. 재귀함수를 사용하지 않고 반복문을 사용하여 잘게 쪼개는 방식으로 하려고 했지만, 마음처럼 되지 않아 재귀함수로 돌아왔다. int area = N * N; int* square = new int[area]; for (int i = 0; i > square[i]; N * N 크기의 int 배열을 동적으로 할당하여, 종이의 색을 저장했다. int count[2] = { 0, 0 }; // { W, B } int sides[2] = { N, N }; count 배열의 첫 번째 요소는 흰 색종이의 갯수를, 두 번째 요소는 파란 색종이의 갯수를 저장한다. sides는 한 변의 길이를 저장하는 배열로, 첫 번째..
[C++] 백준 2667번: 단지번호붙이기 이제 어느정도 너비 우선 탐색 유형에 익숙해졌다. 이 문제에선 단지 수를 나타내는 변수 max_block와 단지별 집의 수를 저장할 house_count를 선언하고, 처음부터 스캔을 하며 1인 칸부터 탐색을 실시했고, 탐색을 시작할 땐 max_block에 1씩 더해주었다. 그리고 지나가는 칸 마다 max_block - 1의 값을 대입하고 house_count의 max_block - 1번 인덱스에 1을 더해준다. 이를 새로운 칸을 발견하지 못 할 때까지 반복하면 금방 끝난다. 마지막 출력을 할 땐, house_count를 오름차순으로 정렬해주고 출력하면 끝난다. #include #include #include using namespace std; int main() { int N; scanf("%d", &..
[C++] 백준 7576번: 토마토 문제 바로가기 이 문제도 2178번: 미로탐색처럼 BFS(너비 우선 탐색)을 활용하는 문제다. 미로탐색의 코드를 활용해서 이 문제를 해결하고자 했는데, 시간초과가 발생했다. 처음에는 현재 박스와 하루가 지나 변화된 박스를 구별하여 두개의 배열을 이용했다. 변화된 박스 배열을 현재 박스 배열에 덮어쓰는 방식으로 했더니 연산량이 과했나보다. 그래서 처음부터 다시 생각했다. 박스를 두 개 생성하는게 아니라, 큐를 두 개 생성했다. 하나는 오늘 익을 토마토들(today), 나머지 하나는 내일 익을 토마토들의 좌표들(tomorrow)이다. 처음에는 각 칸의 상태를 입력받으며 tomorrow에 1인 칸을 담는다. int M, N; scanf("%d %d", &M, &N); int* tomatos = new int[..
[C++] 백준 2178번: 미로 탐색 문제 바로가기 그래프 탐색이라는 개념이 아직은 낯설어서 응용하기가 어렵다. 이 문제에서는 행렬구조가 입력되는데, 각 boundary를 처리하는데 애를 좀 먹었다. 문제를 풀면서 좌표를 활용할 생각을 못 했는데, 질문 검색을 통해 힌트를 좀 얻었다. 또한, 인터넷 검색을 통해 이 문제에 대한 답을 살펴봤다. 나는 다음 몇가지를 생각해내지 못 해서 이 문제를 푸는데 어려움이 있었다. 행렬을 좌표로 표현하기 해당 칸까지의 누적거리를 저장하는 배열 아래 코드에서 BFS를 실행하는 while문의 구조는 대략 아래와 같다. 우선, while문은 BFS가 비어있지 않으면 계속 동작한다. 그 이후엔 이미 방문한 칸이 아닐 때까지 pop을 반복한다. mileage(누적거리)의 값이 -1일 경우 방문하지 않은 경우이다. ..
[C++] 백준 2840번: 행운의 바퀴 문제 바로가기 이 문제에서 주의할 사항들 바퀴에 같은 글자는 두 번 이상 등장하지 않는다. 새로 지정할 칸에 ?가 아닌 다른 글자가 있으면 안 된다. ?는 두 번 이상 등장해도 괜찮다. 나는 1번을 늦게 파악했다. 문제를 제대로 읽어봤어야 했다. 3번은 어쩌면 당연한 것이지만, 1번을 처리하는 과정에서 A???와 같은 결과가 !로 바뀐다. 이를 주의해야 했다. 나는 이 문제를 vector를 이용해 풀었다. 코드 자체는 간단하다. #include #include using namespace std; int main() { int N, K; scanf("%d %d", &N, &K); vector wheel(N, '?'); auto iter = wheel.begin(); for (int i = 0; i < K..
[C++] 백준 1260번: DFS와 BFS 문제 바로가기 이 문제를 풀기 전에는 DFS, BFS에 대해서 아는 것이 거의 없었다. 유튜브 강의 여럿을 참고했는데, 다음 영상이 도움이 많이 됐다. 나는 위 영상에서 처럼 클래스를 생성해서 이 문제를 풀기로 다짐했다. Node 클래스와, Graph 클래스를 정의했다. 모든 멤버들은 public으로 선언하여 외부에서 자유롭게 접근할 수 있도록 했다. Node에는 출력했음을 기록하는 mark, Node의 번호를 나타내는 number, 간선의 갯수인 relations를 선언했다. 간선을 저장하는 lines에는 대상이 되는 Node의 주솟값을 저장했다. Graph에는 저장하고 있는 Node의 갯수와 Node의 배열을 선언했다. class Node { public: bool mark; int number; i..
[C++] 백준 1463번: 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 개요 이 문제는 "다이나믹 프로그래밍" 알고리즘으로 분류돼 있다. 관련하여 찾아보니, 재귀함수를 활용하는 것과 많이 비교된다. 한 번 계산한 것은 다시 계산하지 않는 것이 목표인 것이다. 이 문제에서도 마찬가지다. 틀린 풀이 어떤 수 X가 3으로 나누어 떨어지면, X / 3에 대한 계산은 이미 저장돼 있을 것이라 기대할 수 있다. 만약 X == 10일 경우, X가 2로 나누어 떨어지지만 2로 나누기 시작하여 1로 만드는 것보다 1을 뺀 이후 3으로 나누는 것이 더 적은 횟수의 연산을 할 수 있음을 알 수 있다. 따라서, X가 2 또는 3으로 나누어 떨어진다면, X - 1일 때..
[C++] 백준 18111번: 마인크래프트 문제 바로가기 이 문제 걸핏보면 어려워 보이지만 처음 구현했을 때는 술술 나올 정도로 어렵진 않았다. 알고리즘 분류가 브루트포스 알고리즘으로 돼 있길래, 맘 편하게 코드를 짰다. worst case도 입력해주며 코드를 고쳐나갔다. 누락됐던 블럭을 부수면 인벤토리에 블럭을 추가하는 것도 추가시키고, 블럭이 지금 모자르다고 바로 break를 걸었던 것도 최종 결과에 따라 반영했다. 인벤토리에 블럭을 증가/감소시킨 양 만큼 변화하도록 수정하는 등 다양한 수정을 거쳤다. 코드에 주석까지 하나하나 달아가며 검토했지만, 제출한 코드의 결과는 "틀렸습니다" 아래가 해당 코드다. #include #include int main() { int N, M, B; scanf("%d %d %d", &N, &M, &B); int..

티스토리툴바