알고리즘/백준 문제풀기 썸네일형 리스트형 콜라한캔 :: BOJ 백준 민균이의 비밀번호<문자열 처리> https://www.acmicpc.net/problem/9933 민균이의 텍스트 파일에 들어 있는 문자열 중에 거꾸로 된 문자열도 함께 존재하는 경우 그것을 비밀번호라고 한다. 예를 들어 power가 비밀번호라면, rewop도 있다는 뜻이다. 중복된 답은 나오지 않는다고 했으므로 비밀번호 발견 시 바로 답을 출력해주면 된다. 이 문제의 경우 set을 이용했다. n번 반복문을 돌면서 입력받은 문자열을 set에 추가해준 뒤 입력받은 문자열을 뒤집어서 set에 존재하는지를 체크해주었다. set의 find 함수를 이용하였는데, find함수의 경우 set에서 찾고자 하는 문자열을 찾지 못했을 때 end()를 리턴한다. 따라서 set.find(문자열) != set.end() 일 때의 문자.. BOJ 백준 1764 듣보잡 <문자열 처리> https://www.acmicpc.net/problem/1764 듣도 못한 단어들과 보도 못한 단어들을 입력 받고 공통된 단어들을 사전 순으로 출력해주면 되는 문제이다. 1. 듣도 못한 단어들을 입력 받는다. 2. 듣도 못한 단어들을 저장한 배열을 sort한다. 3. 보도 못한 단어들을 입력받으면서 듣도 못한 배열에 존재하는지 이진탐색을 한다. 4. 이진 탐색 결과가 존재하는 경우 result 배열에 넣어준다. 5. result 배열을 sort해준 뒤 출력해준다. * binary_search는 값이 존재하는 경우 true, 존재하지 않는다면 false를 리턴해준다. * set의 find는 찾는 값이 없을 시 end()를 리턴한다. * Vector를 이용한 풀이 #include #inclu.. BOJ 백준 1032 명령 프롬프트 <문자열 처리> https://www.acmicpc.net/problem/1032 이 문제는 몇 개의 파일 이름을 받아올 지 입력받은 뒤 그 수 만큼 문자열들을 받아오고, 그 문자열들의 공통된 문자를 제외한 다른 문자를 '?'로 바꿔주면 되는 문제이다. 인덱스 0번 째의 문자열을 기준으로 다른 모든 문자열들과 비교해가면서 하나라도 다를 경우 해당 문자를 '?'로 바꾸어 주면 된다. 1. 0번째 문자열을 기준으로 삼는다 2. 0번째 문자열과 다른 모든 문자열과 비교하여 다른 문자는 '?'로 바꾸어준다. #include #include #include #define SIZE 51 using namespace std; int main() { ios_base::sync_with_stdio(0); cin.t.. BOJ 백준 크로아티아 알파벳 <문자열 처리> https://www.acmicpc.net/problem/2941 크로아티아 알파벳변경čc=ćc-dždz=ñd-ljljnjnjšs=žz= 특정 문자열을 입력 받고 그 문자열에 크로아티아 알파벳이 몇 개 있는 지를 계산한 뒤에 크로아티아 알파벳을 제외한 나머지 알파벳을 각각 한 개로 계산하여 총 몇개의 알파벳으로 이루어져있는지 출력해주는 문제이다. 첫 번째 예시 ljes=njak를 보면, lj, s=, nj 이렇게 세 가지의 크로아티아 알파벳이 있고 이 셋을 제외한 e, a, k 까지 합하여 총 6가지의 크로아티아 알파벳으로 이루어져 있는 것을 알 수 있다. 아직 string에 대한 이해도가 낮아 stirng 관련 함수를 최대한 사용하여 풀어보려 하였다. 단순히 find만 이용하여.. BOJ 백준 1475 방 번호 <문자열 처리> https://www.acmicpc.net/problem/1475 이 문제는 0~9의 숫자카드가 한 개씩 들어있는 숫자카드 세트가 있다고 했을 때 특정 수를 만들기 위해 몇 개의 세트가 존재하는 지 출력해주면 되는 간단한 문제이다. 6과 9는 서로 바꿔쓸 수 있으므로 6과 9를 같은 숫자카드라고 생각하고 풀어도 된다. 입력을 받고 입력된 숫자에 사용된 각 숫자들의 개수를 검사해주고 가장 많이 사용된 숫자에 따르면 된다. arr[10]과 같이 0~9의 개수를 저장할 배열을 만들어 주고 개수를 모두 구한 다음에 마지막에 (arr[6] + arr[9] + 1) / 2를 해주어도 되고 애초에 숫자를 검사하여 배열에 저장해줄 때 9일 경우에 arr[6]에 더해주어도 된다. 간단하게, 1. 0부터 .. BOJ 백준 1152 단어의 개수 <문자열 처리> 이 문제는 C++의 cin과 string을 이용하면 보다 간결하고 짧은 코드로 풀 수 있는 문제이다. 맨 앞과 마지막에도 공백이 들어오므로 단어의 개수를 셀 때 띄어쓰기를 이용하는 방법으로 문제를 푼다면 맨 앞과 마지막의 공백은 고려하지 않도록 하여 문제를 풀어야 한다. C++의 표준 입력 함수인 cin은 표준 입력 버퍼에서 개행 문자를 제외한 값을 가져온다. 이 말은 space(띄어쓰기)를 기준으로 각 단어를 끊어서 입력을 받아오는 것이다. 아래와 같이 코딩을 한다면 string s; while(cin >> s){cout s) { cnt++; } cout BOJ 백준 5719 거의 최단경로 <다익스트라> https://www.acmicpc.net/problem/5719 이 문제는 크게 한번 뻘짓(?)을 했다. 처음 문제를 잘못 이해해서, 최단경로에 사용되는 경로들을 지우지 않고 두 번째 최단경로를 구해주면 되는 줄 알고, 도착점 e와 연결된 노드들의 최단경로들 중에 2번째로 큰 수를 골라 출력해주는 형태로 하려고 했는데, 당연히 이 풀이는 틀렸다. 그 이유는 최단 경로에 사용된 경로들은 모두 제거해주어야 되기 때문이다. 따라서 이 문제는 먼저 다익스트라 알고리즘으로 최단 경로를 구해주고, 모든 최단 경로에 이용된 경로들을 제거해준 뒤 다시 다익스트라 알고리즘을 실행해서 최단경로를 출력해주면 된다. Dijkstra();DeletePath();Dijkstra(); 다익스트라 알고리즘에.. BOJ 백준 1932 정수 삼각형 <DP> https://www.acmicpc.net/problem/1932 7 7 3 8 10 15 8 1 0 -> 18 16 15 2 7 4 4 20 25 20 19 4 5 2 6 5 24 30 27 26 24 삼각형의 크기 n이 주어지고 삼각형의 안의 숫자가 주어진 뒤에 계단을 타고 내려오듯이 수들을 골랐을 때 그 합이 가장 큰 경우를 출력하면 된다. 위의 예시를 보면 크기 n은 5로 주어졌고 위에서부터 5줄 내려오면서 1씩 증가하면서 수가 입력되는 것을 알 수 있다. 위의 답은 7 -> 3 -> 8 -> 7 -> 5 로 30이 최대이고 이를 출력해주면 된다. 평범한 dp문제를 풀듯이, 각 줄에 내려오면서 그 줄의 최댓값들을 dp배열에 적어주면 된다. 점.. 이전 1 2 3 4 5 다음
