https://www.acmicpc.net/problem/1929
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
소수를 구하는 알고리즘짜기
처음 접근했을때는 멋도 모르고 그냥 for문 덕지덕지 썼다가 시간 초과로 컷당했다
알고보니 소수를 접근할때는 에라토스테네스 체라는 방법을 사용하는 것이었다
그래서 나에게 이 문제는 에라토스테네스 체의 알고리즘을 코드로 구현하는 문제였고
그 과정은 그리 어렵지 않았다.
이 문제에서 배운건 앞으로 소수를 접근할때는 이 알고리즘을 떠올릴 것 이라는 배움을 얻었다
정답률이 낮은 문제였지만 이 알고리즘만 이해한다면 50%는 넘을것같다
코드
https://www.acmicpc.net/problem/2846
2846번: 오르막길
상근이는 자전거를 타고 등교한다. 자전거 길은 오르막길, 내리막길, 평지로 이루어져 있다. 상근이는 개강 첫 날 자전거를 타고 가면서 일정 거리마다 높이를 측정했다. 상근이는 가장 큰 오르
www.acmicpc.net
위 문제는 본인이 대학에서 c프로그래밍을 배울때 과제로 내줬던 문젠데 그 당시엔 못풀었었다
지금 좀 공부하고 보니 쉬운 문제였는데 지금이라도 풀 수 있는게 그래도 뿌듯하다
배열로 푼 문제 설명은 코드 주석으로
https://www.acmicpc.net/problem/2941
2941번: 크로아티아 알파벳
예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z=
www.acmicpc.net
문자열 문제
이번 문제는 좀 생각할 시간이 필요했다 어떻게 문자를 크로아티아 알파벳으로 인식하게 하는지에 대해서
코드를 짤 때 나는 배열에 문자열을 넣고 0번째 인덱스부터 참조하는데
참조할 때 만나는 문자가 크로아티아 알파벳의 시작 문자이면 다음 인덱스의 문자가 크로아티아 알파벳의 그 다음 문자이면 알파벳 수를 1개 증가시키고 배열의 인덱스 값인 i를 그만큼 증가시켜서 중복 카운트가 되지 않게 만들었다
좀 설명하기 복잡한 그런 문제인것같다
코드
https://github.com/soonsoo3595/algorithm/blob/main/2941.c
https://www.acmicpc.net/problem/5622
5622번: 다이얼
첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다.
www.acmicpc.net
쉽게 푼 문제 안올리려 했는데 그냥 정답률 50%대니까 올리겠다
푼 방법은 각 문자마다 정해진 숫자가 있으므로 문자열의 0번째 인덱스에 있는 문자가
ChartoNum 함수의 인자로 전달돼서 switch문을 이용해 걸리는 시간을 반환하게 만들었다
1번 누르는데 2초 걸리니까 +2 더한거는 말 안해도 알듯
https://www.acmicpc.net/problem/1152
1152번: 단어의 개수
첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한
www.acmicpc.net
문자열 문제인데 정답률이 28%이다 그렇게 어렵진 않은것 같은데
단순하게 그냥 문자열안에 있는 공백의 개수를 구해서 거기서 +1을 해주면 단어의 수가 되는데
여기에는 문자열 처음에 공백이 있을 경우와 마지막에 공백이 있을 경우에는 단어의 수가 증가하지 않으니까
첫 for문에서 더해준 count수 만큼 빼줘야된다
처음 제출했을때 count가 증가가 안하길래 뭔가 했는데 if문에서 공백을 찾을경우에
str[i]의 경우에는 각 인덱스마다 문자열이 아니고 문자이기 때문에 " " 가 아닌 ' '를 해줬어야 했다
정답률에 비해 생각하기 쉽던 문제였다
https://www.acmicpc.net/problem/1157
1157번: 단어 공부
알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.
www.acmicpc.net
문자열을 다룰수있는지를 테스트 하는 문제
정답률이 낮길래 조심해서 풀었는데 알고리즘 자체는 풀었었는데 처음에 아무리 해도 시간초과가 자꾸 뜨는거였다
그래서 질문게시판에 올리려했는데 공지사항을 보니까 문자열의 길이를 반환해주는 strlen 함수의 시간복잡도가
O(N)이라는걸 보고 아 이게 for문 안에 있으면 시간초과가 되겠구나라고 느껴서 따로 변수에다가 strlen함수를 써줬더니 바로 문제가 해결됐다
이 문제를 통해 배운점
>> strlen함수는 따로 변수에 저장해주자 시간을 위해
코드
https://www.acmicpc.net/problem/4673
4673번: 셀프 넘버
셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때,
www.acmicpc.net
난 그냥 배열만들어서 셀프 넘버가 아닌 수를 구해 그 수를 배열의 인덱스로 사용해 0으로 초기화되어있던거를
1로 바꿔준다 그럼 배열에는 0과 1이 반복되는데 값이 0인게 셀프넘버라서 값이 0이면 출력하고 1이면 그냥 넘어가는 방법으로 했다
쫌 찝찝했던게
배열의 인덱스를 1부터 시작했던것
배열크기를 좀 넉넉하게 잡았던것
함수가 적절한지
이런게 좀 거슬리긴한다. 좀 더 프로그래밍 실력이 향상되면 나중에 와서 좀 건들여봐야겠다
함수를 어떻게 정의해야 할지에서 시간이 좀 걸렸다
지금 나로선 난이도를 중으로 하고싶다
코드
| 백준 1152 (0) | 2021.06.28 |
|---|---|
| 백준 1157 (0) | 2021.06.27 |
| 백준 1158(실패) (0) | 2021.06.21 |
| 백준 10845 (0) | 2021.06.21 |
| 백준 1874(실패) (0) | 2021.06.21 |
https://www.acmicpc.net/problem/1158
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
문제를 풀긴 풀었는데 제출이 안된다. 뭐가 문제가 있다는건데 진짜로 모르겠다..
질문게시판에 올려놔야겠다... 나중에 다시 도전하기로...
#include <stdio.h>
typedef struct _que {
int data[5001];
int begin;
int end;
}Que;
void Qinit(Que* q);
void push(Que* q, int data);
void pop(Que* q);
int front(Que* q);
int main()
{
Que q;
Qinit(&q);
int N, K,i,j;
scanf("%d %d", &N, &K);
for (i = 0;i < N;i++)
{
push(&q, i + 1);
}
printf("<");
for (i = 0; i < N - 1;i++) {
for (j = 0;j < K - 1;j++) {
push(&q, front(&q));
pop(&q);
}
printf("%d,", front(&q));
pop(&q);
}
printf("%d>\n",front(&q));
return 0;
}
void Qinit(Que* q)
{
q->begin = 0;
q->end = 0;
}
void push(Que* q, int data)
{
q->data[q->end] = data;
q->end += 1;
}
void pop(Que* q)
{
if ((q->begin) == (q->end))
{
printf("-1\n");
}
else
{
q->begin += 1;
}
}
int front(Que* q)
{
return q->data[q->begin];
}