본문 바로가기
[C++] 백준 1193번: 분수찾기 문제 바로가기 문제에서 주어진 표는 다음과 같다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 각 대각선에서 분모는 ↗ 방향으로 증가하고, 분자는 ↙ 방향으로 증가한다. 주어진 표에서 방문 순서대로 값을 메기면, 1 2 6 7 15 … 3 5 8 14 … … 4 9 13 … … … 10 12 … … … … 11 … … … … … … … … … … … 사실 나는 문제를 제대로 읽지 않아, 아래처럼 생각했었다. 1 2 4 7 11 … 3 5 8 12 … … 6 9 13 … … … 10 14 … … … … 15 … … … … … … … … … … … 하지만 결정적으로 이러한..
[C++] 백준 2941번: 크로아티아 알파벳 문제 바로가기 처음에는 문자열 입력을 받고, 각 크로아티아 알파벳 마다 문자열 내에서 찾아, 0 등의 임의문자로 대치한 후 총 알파벳 수를 세아리려고 했다. 하지만, 그렇게 하면 반복을 많이 하기 때문에, 문자열의 첫 글자부터 시작하여 한 글자씩 크로아티아 알파벳에 해당하는지 확인하기로 했다. 그러기 위해 switch-case를 이용했다. 큰 틀에서 for문으로 각 문자를 확인한다. 문자에 도달하면 일단 수를 세어준다. 이제, 크로아티아 알파벳에 해당하는지 검사하는데, 크로아티아 알파벳에 해당하면 그 길이만큼 인덱스를 건너 뛴다. 예를 들어 dz= 같은 경우는 인덱스를 두 문자 건너 뛰는 방식이다. 이 문제를 풀며 두 번의 실수가 있었다. 아래 코드는 첫 번째 실수이다. switch-case의 이해 부족..
[C++] 백준 1074번: Z 문제 바로가기 이 문제를 재귀함수를 통해 풀 수 있을 것이라 생각했다. 큰 영역에서 시작해서 한 변의 길이를 절반씩 줄여나가며 그 길이가 2가 됐을 때, 네 칸에 Z 순서로 방문하여 순서를 저장하는 방식으로 코드를 구현했다. 다음 코드가 이 방식을 나타낸 코드 전문이다. #include using namespace std; // pivot: [r, c], interval : [2^N, K] void move(int* table, int* pivot, int* interval, int& order) { // Step 1. If interval is minimum, Mark. if (interval[1] == 2) { int delta[4][2] = { {0, 0}, {0, 1}, {1, 0}, {1, 1}..
[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는 한 변의 길이를 저장하는 배열로, 첫 번째..
[Tip.] VS에서 오류나 경고없이 빌드 실패 오류가 뜰 때 1. 도구 - 옵션 - 프로젝트 및 솔루션 - 빌드 및 실행에서 MSBuild 프로젝트 빌드 출력의 세부 정보 표시를 매우 자세히로 설정 2. 솔루션 탐색기에서 솔루션에 우클릭 후 파일 탐색기에서 폴더 열기 클릭. 파일탐색기 옵션 중 보기 - 숨김 항목에 체크 후 .vs 폴더 삭제 후 비주얼 스튜디오를 재시작 하면 된다.
[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..
[Tip.] Visual Studio에 WSL 연결하기 과제를 리눅스 환경에서 해야 한다던가, 백준의 채점환경에서 컴파일을 하고자 할 때 WSL에 코드를 붙여넣어 테스트를 해보곤 한다. 하지만 복사, 붙여넣기가 깔끔하게 되지 않아 주석을 모두 지우고 붙여넣어야 하는 수고로움이 있는데, 아에 비주얼 스튜디오에 WSL을 연동시키면 깔끔하지 않을까 싶어서 알아보니 방법이 있었다. * 실은 1학년 전공 수업 때 배웠던 기억이 있다. 우선, 제어판에서 WSL 기능을 켜야 한다. 제어판에 들어간다. "프로그램" 메뉴를 클릭한다. "Windows 기능 켜기/끄기"를 누른다 Linux용 Windows 하위 시스템"에 체크가 안 돼 있다면 체크를 한다. 이제, WSL을 설치한다. 이는 Microsoft Store에서 검색해 설치하면 된다. 여러가지 버전이 나열되어 있을텐데,..
[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일 때..

티스토리툴바