핀테크 : 금융 + 소프트웨어
ex) 인터넷 은행, 비트코인
computational thinking : 현실 세계의 문제를 분석하여 해결책을 찾는 과학적 사고법
computer programming 은 이렇게 설계한 해결책을 컴퓨터의 명령어로 작성하는 것.
-> 작은 문제로 분해하고, 문제의 패턴을 발견하고, 어떤 데이터를 이용해야하는지 결정하고, 문제를 일반화하고 모델링할 수 있는지를 찾는 과정.
처리하고자 하는 작업/문제 == "요구사항"
so, 프로그램을 작성하는 작업은 요구사항을 만족시키는 일이다.
| 파이썬코딩도장 6 변수와 입력 사용하기 정리 (0) | 2019.12.10 |
|---|---|
| 파이썬코딩도장 5 숫자 계산하기 정리 (0) | 2019.12.10 |
| 파이썬코딩도장 4 기본문법 정리 (0) | 2019.12.10 |
| 파이썬 코딩도장 3 IDLE 이용 정리 (0) | 2019.12.10 |
| 파이썬코딩도장 1.2, 1.3 정리 (0) | 2019.12.10 |
#문제
https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
#작성 코드
|
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
|
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100000;
int n;
int sum[MAX];
int serial[MAX];
void input(){
cin>>n;
for(int i=0; i<n; i++){
cin>>serial[i];
}
}
int solve(){
// 첫 번째 원소로 가장 큰 연속합, 첫 번째 연속합 초기화.
int sumMax=serial[0];
sum[0] = serial[0];
for(int i=1; i<n; i++){
// '현재 원소 < 이전 연속합 + 현재원소' 일 때 더 큰 것을 sum[i]로 저장.
sum[i] = max(sum[i-1]+serial[i], serial[i]);
// 가장 큰 연속합을 갱신한다.
sumMax = max(sumMax, sum[i]);
}
return sumMax;
}
int main(){
input();
cout<<solve();
return 0;
}
|
cs |
##
처음에 2차원 DP를 사용해서 풀려고 코드를 작성했는데,
int sum[100000][100000]; 으로 sum 배열을 선언하고 컴파일하니 컴파일 에러가 발생했다.
구글링해보니, 4*10^10Byte -> 4GB라서 배열의 사이즈가 너무 커서 문제가 생긴것이었다.
| BOJ 12865번 :: 평범한 배낭 (0) | 2019.12.14 |
|---|---|
| BOJ 9370번 :: 미확인 도착지 (0) | 2019.12.13 |
| BOJ 9251번 :: LCS (0) | 2019.12.09 |
| BOJ 1504번 :: 특정한 최단 경로 (0) | 2019.12.08 |
| BOJ 2206번 :: 벽 부수고 이동하기 (0) | 2019.12.08 |
#문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
#작성 코드
|
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
|
#include <iostream>
#include <string>
using namespace std;
#define MAX 1000
string stra, strb;
int c[MAX+1][MAX+1]; // 0으로 채워진 행과 열을 앞에 추가.
void input(){
cin>>stra;
cin>>strb;
}
int findLCS(string stra, string strb){
// stra와 strb의 문자열을 하나하나 비교.
for(int i=1; i<=stra.length(); i++){
for(int j=1; j<=strb.length(); j++){
// 현재 비교하는 문자열이 같지 않으면
// 이 위치 전까지 존재하는 lCS 중 가장 긴 수를 유지한다.
if( stra[i-1]!=strb[j-1] ){
c[i][j] = max(c[i-1][j], c[i][j-1]);
}
else{
// stra[i-1]==strb[j-1]
// stra, strb 각각 한 문자열 전까지 lCS길이에 1을 추가한다.
c[i][j] = c[i-1][j-1]+1;
}
}
}
return c[stra.length()][strb.length()];
}
int main(){
input();
cout<<findLCS(stra, strb);
return 0;
}
|
cs |
##
어제 유튜브에서 봤던 minumum edit distance 문제와 비슷했다. https://youtu.be/b6AGUjqIPsA
| BOJ 9370번 :: 미확인 도착지 (0) | 2019.12.13 |
|---|---|
| BOJ 1912번 :: 연속합 (0) | 2019.12.09 |
| BOJ 1504번 :: 특정한 최단 경로 (0) | 2019.12.08 |
| BOJ 2206번 :: 벽 부수고 이동하기 (0) | 2019.12.08 |
| BOJ 1697번 :: 숨바꼭질 (0) | 2019.12.08 |
#문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호가 주어진다.
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
#작성 코드
|
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 <cstdio>
#include <queue>
#include <vector>
using namespace std;
int N, E;
int one, two;
vector< pair<int, int> > node[801];
int INF = 800001;
void input(){
// 정점의 개수, 간선의 개수 입력
scanf("%d %d", &N, &E);
// 그래프 입력
for(int i=0; i<E; i++){
int start, end, cost;
scanf("%d %d %d", &start, &end, &cost);
// 양방향 그래프!
node[start].push_back(make_pair(end, cost));
node[end].push_back(make_pair(start, cost));
}
// 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호
scanf("%d %d", &one, &two);
}
int dijkstra(int start, int end){
// start 에서 시작해서 각 정점으로 가는 최단거리 무한대로 초기화.
long long int shortest[801];
fill_n(shortest, 801, INF);
priority_queue< pair<int, int> > pq;
// 우선순위 큐에 시작 정점 push.
pq.push(make_pair(0, start));
shortest[start] = 0;
while(!pq.empty()){
// 현재 위치의 정점에 대해 탐색.
int now = pq.top().second;
int nowcost = -pq.top().first;
pq.pop();
// 알고 있는 start->now 최단거리보다 nowcost가 크면 이 정점은 패스
if( shortest[now] < nowcost ) continue;
// now를 경유해서 갈 수 있는 정점에 경유해서 가는 거리가 더 짧다면 교체.
for( int i=0; i<node[now].size(); i++){
int next = node[now][i].first;
int nextcost = node[now][i].second + nowcost;
if( shortest[next] > nextcost ){
shortest[next] = nextcost;
pq.push(make_pair(-nextcost, next));
// 우선순위 큐를 사용하므로 cost를 음수화해서 저장해야 작은것부터 꺼낼 수 있다.
}
}
}
// end까지의 최단거리 갱신이 안되었다면 -1을 리턴한다.
if( shortest[end] >= INF ) return -1;
// end까지의 최단거리가 존재한다면 그 거리를 리턴
else return shortest[end];
}
int solve(){
int startToOne = dijkstra(1, one);
int startToTwo = dijkstra(1, two);
int oneToTwo = dijkstra(one, two);
int twoToEnd = dijkstra(two, N);
int oneToEnd = dijkstra(one, N);
int result1=0, result2=0;
bool flag1 = true, flag2 = true;
// 경로 중 하나라도 최단거리를 찾지 못하는 경로가 있다면 -1을 출력한다.
// 경로 1번 : 1->one->two->N
if( startToOne==-1 || oneToTwo==-1 || twoToEnd==-1 ){
flag1 = false;
}
// 경로 2번 : 1->two->one->N
if( startToTwo==-1 || oneToTwo==-1 || oneToEnd==-1 ){
flag2 = false;
}
result1 = startToOne+oneToTwo+twoToEnd; // 경로1번 결과
result2 = startToTwo+oneToTwo+oneToEnd; // 경로2번 결과
// 경로 1번, 경로 2번 모두 불가능 할 때
if( !flag1 && !flag2 ){
return -1;
}
// 경로 1만 가능할때
else if( flag1 && !flag2 ){
return result1;
}
// 경로 2만 가능할때
else if( flag2 && !flag1){
return result2;
}
// 경로 1과 2 모두 가능할 때
else{
return min(result1, result2);
}
}
int main(){
input();
printf("%d\n", solve());
return 0;
}
|
cs |
##
정점의 개수 N이 최대 800개 가능하므로 vector< pair<int, int> > node[801];을 생성한다.
a번 정점에서 b번 정점까지 거리가 c인 양방향 길이 존재 -> node[a]에 {b, c}를 push, node[b]에 {a, c}를 push 한다.
반드시 거쳐야 하는 두 개의 서로 다른 정점을 입력받고 one, two라는 전역변수에 저장한다.
맞는 것 같은데, 계속해서 틀렸습니다 판정을 받아서 반례를 게시판에서 찾아 체크했는데 모두 알맞게 나왔다.
문제는, line 90, 94에서 flag1과 flag2에 대해서만 검사하고 !flag2, !flag1 검사를 해주지 않았기 때문에 발생했다.
조건에 대해서는 하나하나 꼭 체크 해주자!!
#191209 REVIEW
1. line 72~100에서 flag1과 flag2를 체크하는 방법 이외에,
dijkstra()함수에서 INF보다 큰 경우에 -1을 리턴하는 대신 INF 값 그대로를 리턴하게 하고,
result = min(result1, result2) 를 저장해놓고,
result>=INF 라면 -1을 출력하고, 아니라면 result를 출력하게 하는 방법으로 하면 좀 더 간단하게 처리할 수 있겠다.
2. dijkstra 함수의 리턴형을 vector<int>로 교체.
startToOne, startToTwo는 원래 코드에서, 같은 결과의 shortest[]배열을 생성하고, 배열 내에서 리턴하는 값의 위치만 달랐다.
dijkstra함수를 start에서 시작해서 다른 모든 정점으로의 최단거리를 계산한 vector를 리턴하도록 해서,
startToOne, startToTwo를 동일한 결과값에서 추출할 수 있도록 변경했다.
|
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
|
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int N, E;
int one, two;
vector< pair<int, int> > node[801];
int INF = 800001;
void input(){
// 정점의 개수, 간선의 개수 입력
scanf("%d %d", &N, &E);
// 그래프 입력
for(int i=0; i<E; i++){
int start, end, cost;
scanf("%d %d %d", &start, &end, &cost);
// 양방향 그래프!
node[start].push_back(make_pair(end, cost));
node[end].push_back(make_pair(start, cost));
}
// 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호
scanf("%d %d", &one, &two);
}
vector<int> dijkstra(int start){
// start 에서 시작해서 각 정점으로 가는 최단거리 무한대로 초기화.
// vector를 리턴하도록 수정해보았다.
vector<int> shortest(801, INF);
priority_queue< pair<int, int> > pq;
// 우선순위 큐에 시작 정점 push.
pq.push(make_pair(0, start));
shortest[start] = 0;
while(!pq.empty()){
// 현재 위치의 정점에 대해 탐색.
int now = pq.top().second;
int nowcost = -pq.top().first;
pq.pop();
// 알고 있는 start->now 최단거리보다 nowcost가 크면 이 정점은 패스
if( shortest[now] < nowcost ) continue;
// now를 경유해서 갈 수 있는 정점에 경유해서 가는 거리가 더 짧다면 교체.
for( int i=0; i<node[now].size(); i++){
int next = node[now][i].first;
int nextcost = node[now][i].second + nowcost;
if( shortest[next] > nextcost ){
shortest[next] = nextcost;
pq.push(make_pair(-nextcost, next));
// 우선순위 큐를 사용하므로 cost를 음수화해서 저장해야 작은것부터 꺼낼 수 있다.
}
}
}
// start부터 다른 모든 정점으로의 최단거리를 저장한 벡터자체를 리턴함.
return shortest;
}
int solve(){
vector<int> sStart = dijkstra(1);
int startToOne = sStart[one];
int startToTwo = sStart[two];
vector<int> sOne = dijkstra(one);
int oneToTwo = sOne[two];
// one->two와 two->one은 동일하므로 한번만 사용.
vector<int> sEnd = dijkstra(N);
int twoToEnd = sEnd[two];
int oneToEnd = sEnd[one];
// 두 가지 경로의 결과값 저장.
int result1=0, result2=0;
result1 = startToOne+oneToTwo+twoToEnd; // 경로1번 결과
result2 = startToTwo+oneToTwo+oneToEnd; // 경로2번 결과
//수정한 부분!
int result = min(result1, result2);
if( result>=INF ) return -1;
else return result;
}
int main(){
input();
printf("%d\n", solve());
return 0;
}
|
cs |
| BOJ 1912번 :: 연속합 (0) | 2019.12.09 |
|---|---|
| BOJ 9251번 :: LCS (0) | 2019.12.09 |
| BOJ 2206번 :: 벽 부수고 이동하기 (0) | 2019.12.08 |
| BOJ 1697번 :: 숨바꼭질 (0) | 2019.12.08 |
| BOJ 2565번 :: 전깃줄 (0) | 2019.12.07 |