2530번: 인공지능 시계
첫째 줄에 종료되는 시각의 시, 분, 초을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수이며, 분, 초는 0부터 59까지의 정수이다. 디지털 시계는 23시 59분 59초에서 1초가 지나면 0시 0
www.acmicpc.net
시간에 대한 문제도 좀 많이 풀어봐야 하는데
맨날 나올때마다 대강 생각하고 풀고 넘어가버려서
시간에 관련된 어려운 문제가 나오면 풀 수 있을지
| 백준 1759 : 암호 만들기 (0) | 2020.10.22 |
|---|---|
| 백준 7576 : 토마토 (0) | 2020.10.22 |
| 백준 13023 : ABCDE (0) | 2020.10.22 |
| 백준 1009 : 분산처리 (0) | 2020.10.22 |
| 백준 11723 : 집합 (0) | 2020.10.22 |
| 백준 7576 : 토마토 (0) | 2020.10.22 |
|---|---|
| 백준 2530 : 인공지능 시계 (0) | 2020.10.22 |
| 백준 1009 : 분산처리 (0) | 2020.10.22 |
| 백준 11723 : 집합 (0) | 2020.10.22 |
| 백준 1337 : 올바른 배열 (0) | 2020.10.22 |
1009번: 분산처리
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)
www.acmicpc.net
예전에 이런 문제에 대해 규칙을 찾기가 귀찮아 건너뛴 적이 많았는데
귀찮으면 안되겠지
코드가 좀 이상한 부분이 있다. 나중에 이 기록을 다시 본다면 함 보고 잘 생각해볼것
| 백준 2530 : 인공지능 시계 (0) | 2020.10.22 |
|---|---|
| 백준 13023 : ABCDE (0) | 2020.10.22 |
| 백준 11723 : 집합 (0) | 2020.10.22 |
| 백준 1337 : 올바른 배열 (0) | 2020.10.22 |
| 백준 1874 : 스택 수열 (0) | 2020.10.22 |
11723번: 집합
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
www.acmicpc.net
비트마스크란 이런 것이다?
| 백준 13023 : ABCDE (0) | 2020.10.22 |
|---|---|
| 백준 1009 : 분산처리 (0) | 2020.10.22 |
| 백준 1337 : 올바른 배열 (0) | 2020.10.22 |
| 백준 1874 : 스택 수열 (0) | 2020.10.22 |
| 백준 1182 : 부분수열의 합(비트마스크, dfs) (0) | 2020.10.22 |
1337번: 올바른 배열
첫째 줄에 배열의 크기 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수
www.acmicpc.net
처음에 접근을 잘못해서 이상하게 생각했는데
겁나 쉬운 문제였다
와 이걸 네시간동안 봤다고
이걸
| 백준 1009 : 분산처리 (0) | 2020.10.22 |
|---|---|
| 백준 11723 : 집합 (0) | 2020.10.22 |
| 백준 1874 : 스택 수열 (0) | 2020.10.22 |
| 백준 1182 : 부분수열의 합(비트마스크, dfs) (0) | 2020.10.22 |
| 백준 15666 : N과 M(12) (0) | 2020.10.22 |
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
하라는대로 따라하면 풀리는 문제
코드
| 백준 11723 : 집합 (0) | 2020.10.22 |
|---|---|
| 백준 1337 : 올바른 배열 (0) | 2020.10.22 |
| 백준 1182 : 부분수열의 합(비트마스크, dfs) (0) | 2020.10.22 |
| 백준 15666 : N과 M(12) (0) | 2020.10.22 |
| 백준 6588 : 골드바흐의 추측 (0) | 2020.10.22 |
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
비트를 이용해 완전탐색을 돌리는 이런 방법도 있구나
비트연산이 사실 아직까지 좀 겁나긴 하는데
이렇게 간단한 정도라면 괜찮은 것 같다
이건 간단하게 재귀 dfs로 풀어본 방식
근데 웃긴건 재귀 dfs가 훨씬 빠르다ㅋㅋㅋㅋ
음, 왜지...?
| 백준 1337 : 올바른 배열 (0) | 2020.10.22 |
|---|---|
| 백준 1874 : 스택 수열 (0) | 2020.10.22 |
| 백준 15666 : N과 M(12) (0) | 2020.10.22 |
| 백준 6588 : 골드바흐의 추측 (0) | 2020.10.22 |
| 백준 10972, 10973 : 다음 순열, 이전 순열 (0) | 2020.09.09 |
15666번: N과 M (12)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
dfs로 짜는건 일반적인 방법이라 할말이 없는데
다만 이터레이터의 사용을 좀 열심히 해봤다
결론은 그냥 하던대로 하는게 좋을것같다
| 백준 1874 : 스택 수열 (0) | 2020.10.22 |
|---|---|
| 백준 1182 : 부분수열의 합(비트마스크, dfs) (0) | 2020.10.22 |
| 백준 6588 : 골드바흐의 추측 (0) | 2020.10.22 |
| 백준 10972, 10973 : 다음 순열, 이전 순열 (0) | 2020.09.09 |
| 백준 9095 : 1, 2, 3 더하기 (0) | 2020.09.09 |
6588번: 골드바흐의 추측
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰
www.acmicpc.net
하
에라토스테네스를 하도 오래전에 봐서 규칙만 보고 다시 짠다는 마음으로 만들어봤더니
계속 틀렸다고 나와서... 다 잘 만들어놓고 무려 한시간이나 고민했다
여기서 처음엔 unsigned int만 집어넣고 썼는데
i * i 에서 오버플로우가 터져버리는걸 몰랐던거다
매우 기본적인걸 놓쳐서 너무 화가난다
| 백준 1182 : 부분수열의 합(비트마스크, dfs) (0) | 2020.10.22 |
|---|---|
| 백준 15666 : N과 M(12) (0) | 2020.10.22 |
| 백준 10972, 10973 : 다음 순열, 이전 순열 (0) | 2020.09.09 |
| 백준 9095 : 1, 2, 3 더하기 (0) | 2020.09.09 |
| koi : 타일 채우기(DP아님) (0) | 2020.08.19 |
https://www.acmicpc.net/problem/10972
10972번: 다음 순열
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
https://www.acmicpc.net/problem/10973
10973번: 이전 순열
첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
| 백준 15666 : N과 M(12) (0) | 2020.10.22 |
|---|---|
| 백준 6588 : 골드바흐의 추측 (0) | 2020.10.22 |
| 백준 9095 : 1, 2, 3 더하기 (0) | 2020.09.09 |
| koi : 타일 채우기(DP아님) (0) | 2020.08.19 |
| 동적 계획법 (0) | 2020.08.19 |
https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
| 백준 6588 : 골드바흐의 추측 (0) | 2020.10.22 |
|---|---|
| 백준 10972, 10973 : 다음 순열, 이전 순열 (0) | 2020.09.09 |
| koi : 타일 채우기(DP아님) (0) | 2020.08.19 |
| 동적 계획법 (0) | 2020.08.19 |
| 백준 1620 : 나는야 포켓몬 마스터 이다솜 (0) | 2020.08.19 |
https://www.acmicpc.net/problem/1620
1620번: 나는야 포켓몬 마스터 이다솜
첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면
www.acmicpc.net
정신나간 푸키먼 문제
어디서 만든걸 번역해온듯 한데
뭐 아무튼 해시 or 맵으로 간단하게 풀수있다.
다만 입력값이 100000개를 넘다 보니
io에 대해서 대비해놔야 한다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
int N, M;
std::unordered_map<std::string, int> pokeHash;
std::vector<std::string> pokeVec;
void input()
{
std::cin >> N >> M;
pokeVec = std::vector<std::string>(N + 1);
pokeHash.reserve(N + 1);
std::string strInput;
for (int i = 1; i <= N; ++i)
{
std::cin >> strInput;
pokeHash[strInput] = i;
pokeVec[i] = strInput;
}
}
void solve()
{
std::string input;
for (int i = 0; i < M; ++i)
{
std::cin >> input;
int pokeNum = std::atoi(input.c_str());
if (pokeNum == 0)
{
std::cout << pokeHash[input];
}
else if (pokeNum <= N)
{
std::cout << pokeVec[pokeNum];
}
std::cout << '\n';
}
}
int main()
{
std::cin.tie(0);
std::cin.sync_with_stdio(false);
std::cout.tie(0);
std::cout.sync_with_stdio(false);
input();
solve();
return 0;
}
|
cs |
이걸 트라이로 푼다면 속도면에서는 통과가 가능하나
100000개의 단어별로 메모리를 확보해놓아야 한다.
메모리 초과가 뜨니 트라이 사용엔 유의할것
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
struct Trie
{
Trie()
{
//memset(next, 0, sizeof(next));
for (int i = 0; i < 26; ++i)
{
next[i] = nullptr;
}
}
~Trie()
{
for (int i = 0; i < 26; ++i)
{
if (next[i])
{
delete next[i];
}
}
}
void insert(const char* word, const int num)
{
if (*word == '\0')
{
_num = num;
return;
}
int idx = *word - 'a';
if (next[idx] == nullptr)
{
next[idx] = new Trie;
}
next[idx]->insert(word + 1, num);
}
unsigned int find_num(const char* word)
{
if (*word == '\0')
{
return _num;
}
if (next[word[0] - 'a'] == nullptr)
{
return 0;
}
return next[word[0] - 'a']->find_num(word + 1);
}
public:
Trie* next[26];
unsigned int _num = 0;
};
Trie trieArr;
int N, M;
std::vector<std::string> pokeVec;
void input()
{
std::cin >> N >> M;
pokeVec = std::vector<std::string>(N + 1);
std::string strInput;
for (int i = 1; i <= N; ++i)
{
std::cin >> strInput;
pokeVec[i] = strInput;
strInput[0] = strInput[0] - 'A' + 'a';
trieArr.insert(strInput.c_str(), i);
}
}
void solve()
{
std::string input;
for (int i = 0; i < M; ++i)
{
std::cin >> input;
int pokeNum = std::atoi(input.c_str());
input[0] = input[0] - 'A' + 'a';
if (pokeNum == 0)
{
std::cout << trieArr.find_num(input.c_str());
}
else if (pokeNum <= N)
{
std::cout << pokeVec[pokeNum];
}
std::cout << '\n';
}
}
int main()
{
input();
solve();
return 0;
}
|
cs |
100000개의 단어, 길이별로 26개씩 할당을 하는데 이게 저마다 죄다 다른 단어면 메모리를 그만큼 많이 할당하니
문제가 생길 여지가 높다. 메모리 파악하는 눈치도 좀 키워야할텐데
일단 cin.tie 등과 같은 FastIO를 사용하면 된다.
혹은 scanf printf만 쓰거나
| koi : 타일 채우기(DP아님) (0) | 2020.08.19 |
|---|---|
| 동적 계획법 (0) | 2020.08.19 |
| koi : combinations(S) (0) | 2020.08.18 |
| 백준 1037 : 약수 (0) | 2020.08.14 |
| 백준 1316 : 그룹단어체커 (0) | 2020.08.14 |
