Doby's Lab

https://www.acmicpc.net/problem/1990 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 솔루션 1) 에라토스테네스의 체를 통해 입력받은 b보다 작거나 같은 소수들을 구한다. 2) a와 b 사이의 범위를 만족시키기 위해 이분 탐색을 통해 시작과 끝 범위를 찾는다. 3) bool 타입의 팰린드롬 판별 함수를 통해 소수 중에 팰린드롬을 찾는다. 4) -1 출력, 종료 >> 다음 솔루션은 메모리 초과 발생 >> 게시판 질문 글에서 10,000,000을 넘어가는 팰린드롬인 소수는..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 이번 문제는 학교에서 자료구조 과제로 나왔던 키워드이지만 그 당시에 안 했어서 이번 기회에 구현을 해보려 했다. 솔루션 [1] 식을 문자열로 받아서 피연산자인지 연산자인지 구분을 한다. [2] 연산자나 괄호를 스택에 우선순위로 처리해야 하는 *, / 의 조건과 +, -의 조건, (, ) 두 괄호의 조건을 따로따로 처리를 해줘야 한다. A+B*C 다음 경우를 예로 들어보자. 답으로는 ABC+*가..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음엔 BFS를 돌려서 큐에다가 현재의 위치와 벽을 부술 수 있는지에 대한 힘의 여부를 담았다. 그리고, 한번 방문했다면 방문할 수 없게끔 했다. (무한 루프 방지) [처음 코드] #include #include #include #include using namespace std; int n, m; int map[1001][1001] = { 0, }; int temp[10..

https://draw-code-boy.tistory.com/101 [알고리즘] 백준 2407번: 조합 (C++), Combination, Permutation https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 이번 문제는 (https://jaimemin.tistory.com/682)을 참고한다. 개념 학생.. draw-code-boy.tistory.com 이 문제를 풀면서 솔루션을 참고하다가 공부하게 된 내용이다. 우선 &를 쓴다는 점에서 포인터라고 생각했지만 전혀 다른 개념을 사용된다. 변수의 의미는 '메모리 공간에 이름을 붙인 것'이다. 참조자는 똑같은 메..

https://www.acmicpc.net/problem/14562 14562번: 태권왕 첫째 줄에 테스트 케이스의 수 C(1 ≤ C ≤ 100)이 주어진다. 둘째 줄부터 C줄에 걸쳐 테스트 케이스별로 현재 점수 S와 T가 공백을 사이에 두고 주어진다. (1 ≤ S < T ≤ 100) www.acmicpc.net 이번 문제를 풀면서 저번에 포스팅했던 리모컨 문제가 떠올랐었다. (https://draw-code-boy.tistory.com/99) 솔루션 간단한 BFS 문제였다. S와 T의 점수가 주어지면 두 가지 방법으로 S의 점수를 올려준다. S의 점수가 2배가 된다. 단, T의 점수에는 3점이 추가된다. S의 점수에 1점이 추가된다. 두 가지 경로를 가지고 BFS를 짜주면 된다. 단, 이번 문제에서 주..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 이번 문제는 (https://jaimemin.tistory.com/682)을 참고한다. 개념 학생 때 배웠던 nCr 개념이 등장한다. 정확히는 n Combination r이라고 부른다. 이와 같이 따라오는 게 nPr로 이는 n Permutation r이라고 부른다. 이 둘은 조합론으로 둘 다 공식이 존재한다. 솔루션 1 (실패) 이 공식을 활용하여 두 개의 팩토리얼 함수를 구현하여 풀려고 했다. [조금 다른 방식의 팩토리얼 함수] 각각 n!, (n - r)!, r! 은 시간이 오래 걸릴뿐더러 숫자까지 너무 커질 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이번 문제는 TC를 보고 나서 점화식을 어떻게 짜야할지 혼란을 가져다주는 문제였다. 하지만, TC를 간단하게 생각해보면 쉽게 풀 수 있었다. 솔루션에 도달하는 과정 5 50 10 100 20 40 30 50 70 10 60 다음 TC가 문제를 다시 생각해보게 했었다. 그 전의 코드는 이렇다. #include #include using namespace std; int T; int cac..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이번 문제는 어떠한 논리라기보다 너무 복잡한 생각을 필요하지 않은 문제다. 오히려 간단해지기 위해 복잡한 생각을 해야 했던 문제(?)였다. 처음에는 어떻게 최솟값을 도출할지를 생각하는 과정에서 두 가지로 나뉘었다. 한 번에 최솟값을 도출하는 방법(?) 모든 채널을 대입해보면서 최솟값을 찾는 방법 1번 방법은 생각만 해도 반례가 너무 많을 거 같았다. 주어진 수가 500,000이라면..