KimMinJun
Coding Note
KimMinJun
전체 방문자
오늘
어제
  • 분류 전체보기 (502) N
    • ALGORITHM (11)
      • 정렬 (6)
      • 최단경로 (1)
      • 자료구조 (1)
      • 슬라이딩 윈도우 (1)
      • etc (2)
    • Git (5)
    • Web (24)
      • Vanilla JS (13)
      • TS (2)
      • React (7)
      • ETC (1)
    • React 공식문서 (번역, 공부) (11)
      • Quick Start (2)
      • Installation (0)
      • Describing the UI (9)
      • Adding Interactivity (0)
      • Managing State (0)
      • Escape Hatches (0)
    • Next.js 공식문서 (번역, 공부) (3)
      • Getting Started (2)
      • Building Your Application (1)
    • PS (432)
      • 백준 (187)
      • Programmers (105)
      • CodeUp (21)
      • STL (3)
      • 제코베 JS 100제 (50)
      • SWEA (0)
      • LeetCode (65)
    • IT (1)
    • Docker (14) N
    • CS (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 관리

공지사항

인기 글

태그

  • string
  • C
  • recursion
  • 정렬
  • 다이나믹 프로그래밍
  • 제코베 JS 100제
  • Level 1
  • Level1
  • 그래프
  • 수학
  • 문자열
  • Level 2
  • LeetCode
  • programmers
  • tree
  • js
  • 백준
  • codeup
  • C++
  • Level 0

최근 댓글

최근 글

hELLO · Designed By 정상우.
KimMinJun

Coding Note

PS/백준

백준 / String(문자열) / 2902번 / KMP는 왜 KMP일까? / C

2021. 2. 25. 22:09

문제

KMP 알고리즘이 KMP인 이유는 이를 만든 사람의 성이 Knuth, Morris, Prett이기 때문이다. 이렇게 알고리즘에는 발견한 사람의 성을 따서 이름을 붙이는 경우가 많다.

또 다른 예로, 유명한 비대칭 암호화 알고리즘 RSA는 이를 만든 사람의 이름이 Rivest, Shamir, Adleman이다.

사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다.

  • 첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예를 들면, Knuth-Morris-Pratt이다. 이것을 긴 형태라고 부른다.
  • 두 번째로 짧은 형태는 만든 사람의 성의 첫 글자만 따서 부르는 것이다. 예를 들면, KMP이다.

동혁이는 매일매일 자신이 한 일을 모두 메모장에 적어놓는다. 잠을 자기 전에,

오늘 하루 무엇을 했는지 되새겨 보는것으로 하루를 마감한다.

하루는 이 메모를 보던 중, 지금까지 긴 형태와 짧은 형태를 섞어서 적어 놓은 것을 발견했다.

이렇게 긴 형태로 하루 일을 기록하다가는 메모장 가격이 부담되어 파산될 것이 뻔하기 때문에,

앞으로는 짧은 형태로 기록하려고 한다.

긴 형태의 알고리즘 이름이 주어졌을 때, 이를 짧은 형태로 바꾸어 출력하는 프로그램을 작성하시오.

입력

입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만

이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드시 대문자이다. 그 외의 모든 문자는

모두 소문자이다.

출력

첫 줄에 짧은 형태 이름을 출력한다.

예제 입력 1

Knuth-Morris-Pratt

예제 출력 1

KMP

 

#include <stdio.h>
#include <string.h>

#define MAX_LENGTH 100

int main() {
	char str[MAX_LENGTH];

	scanf("%s", str);

	for (int i = 0; i < strlen(str); i++) {
		if (str[i] >= 'A' && str[i] <= 'Z')
			printf("%c", str[i]);
	}

	return 0;
}
#include <stdio.h>
#include <string.h>

#define MAX_LENGTH 100

int main() {
	char str[MAX_LENGTH];

	scanf("%s", str);

	char* ptr = strtok(str, "-");

	while (ptr != NULL) {
		printf("%c", ptr[0]);
		ptr = strtok(NULL, "-");
	}

	return 0;
}

2가지 방법으로 접근해보았다.

  1. 성의 맨 첫글자는 대문자이기 때문에, 입력받은 문자열에서 대문자만 출력한다.
  2. 문자열을 '-'로 나눈다음, 각각 나눠진 문자열에서 첫글자만 출력한다.

첫번째방법은 간단하다.

입력받은 문자열에서 if문으로 단순히 대문자만 출력해주면된다.

 

두번째방법은 string 라이브러리의 strtok를 써야한다.

'-'로 나눠준뒤 각각의 문자열의 첫번째 글자를 출력한다.

strtok에 대한 이해하기 쉬운 설명은 밑의 사이트를 참고했다.

dojang.io/mod/page/view.php?id=376

 

C 언어 코딩 도장: 45.1 문자를 기준으로 문자열 자르기

45 문자열 자르기 지금까지 문자열을 복사하거나 붙이는 방법을 알아보았습니다. 이번에는 주어진 문자열을 자르는 방법을 알아보겠습니다. 참고로 문자열 자르기는 포인터를 이용하는 방식이

dojang.io

 

저작자표시 (새창열림)

'PS > 백준' 카테고리의 다른 글

백준 / String(문자열) / 10798번 / 세로읽기 / C  (0) 2021.02.27
백준 / String(문자열) / 1100번 / 하얀 칸 / C  (1) 2021.02.25
백준 / String(문자열) / 10987번 / 모음의 개수 / C  (1) 2021.02.25
백준 / String(문자열) / 2743번 / 단어 길이 재기 / C  (0) 2021.02.25
    'PS/백준' 카테고리의 다른 글
    • 백준 / String(문자열) / 10798번 / 세로읽기 / C
    • 백준 / String(문자열) / 1100번 / 하얀 칸 / C
    • 백준 / String(문자열) / 10987번 / 모음의 개수 / C
    • 백준 / String(문자열) / 2743번 / 단어 길이 재기 / C
    KimMinJun
    KimMinJun

    티스토리툴바