https://www.acmicpc.net/problem/17144

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

 

요즘은 시뮬레이션 문제 푸는게 재밌는 것 같다..

복잡한 알고리즘 고민없이 코딩할 수 있어서 그런가,,

 

마냥 구현만 하면 풀 수 있는 문제들이라 아무 생각없이 풀 수 있어 좋은 것 같다(생각없이 풀다보니 코드는 개판이 된다)

 

미세먼지 안녕! 문제는 1) 확산 2) 공기 순환을 구현하면 풀 수 있다.

확산에서 중요한 점은 확산 전 원본 배열을 기준으로 계산을 쭉 진행해야 하기 때문에, 새로운 배열이 필요하다.

나는 memcpy를 이용해 새로운 배열을 만들었고, O(n*2), n 이 1000 이하라 시간안에는 돌아가지만,

예전에 어떤 문제를 풀면서 memcpy가 상당히 느리다는 것을 알았다.. 직접 for문 돌린게 더 빨랐던 것 같기도

 

공기 순환은 rotate 라는 이름(함수 이름 짓기가 젤 어렵다)으로 구현했는데, 사실 실수가 많이 발생할 법한 구현이다.

left, right, up, down 으로 각각 쪼개서 구현해서, 시계방향은 down -> right -> up -> left 순서로 덮어써가고,
반시계방향은  up -> right -> down -> left 순서로 덮어써가면 실수를 줄일 수 있을 것 같다.

 

시뮬레이션 문제의 핵심은 구현 중 발생할 수 있는 실수를 최대한 줄이는게 핵심일 것 같다..

사실 좋은 코드는 실무에서 굉장히 중요하지만, 알고리즘을 풀면서 코드의 질이 크게 중요한 가 싶다 (변명 아님..)

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int arr[1111][1111], r,c,t;
  4. int dy[4] = {-1,1,0,0}, dx[4] = {0,0,-1,1};
  5.  
  6. void rotate(int y, int x, int y_dir){
  7. arr[y+y_dir][x] = 0;
  8.  
  9. for(int i=y+y_dir; i != (y_dir == -1 ? 0 : r-1); i += y_dir){
  10. arr[i][x] = arr[i+y_dir][x];
  11. }
  12.  
  13. int y_ = y_dir == -1 ? 0 : r-1;
  14. for(int i=0; i<c-1; i++){
  15. arr[y_][i] = arr[y_][i+1];
  16. }
  17.  
  18. for(int i=y_; i != y; i-= y_dir){
  19. arr[i][c-1] = arr[i-y_dir][c-1];
  20. }
  21.  
  22. for(int i=c-1; i-1>0; i--){
  23. arr[y][i] = arr[y][i-1];
  24. arr[y][i-1] = 0;
  25. }
  26. }
  27.  
  28. void spread(){
  29. int new_arr[1111][1111] = {0};
  30. memcpy(new_arr, arr, sizeof(arr));
  31. for(int i=0; i<r; i++){
  32. for(int j=0; j<c; j++){
  33. if(arr[i][j] >= 5){
  34. int cnt = 0;
  35. for(int d=0; d<4;d++){
  36. int ny = i+dy[d], nx = j+dx[d];
  37. if(ny>=0 && ny< r&& nx>=0 && nx< c && arr[ny][nx] != -1){
  38. cnt+=1;
  39. new_arr[ny][nx] += arr[i][j]/5;
  40. }
  41. }
  42. new_arr[i][j] -= arr[i][j]/5 * cnt;
  43. }
  44. }
  45. }
  46. memcpy(arr, new_arr, sizeof(arr));
  47. }
  48. int main(){
  49. int src_y = -1;
  50. scanf("%d%d%d", &r,&c,&t);
  51.  
  52. for(int i=0;i<r;i++){
  53. for(int j=0; j<c; j++){
  54. scanf("%d", &arr[i][j]);
  55. }
  56. if(arr[i][0] == -1 && src_y == -1)
  57. src_y = i;
  58. }
  59.  
  60. for(int i=0; i<t; i++){
  61. spread();
  62. rotate(src_y, 0, -1);
  63. rotate(src_y+1, 0, 1);
  64. }
  65. int ans= 0;
  66. for(int i=0;i<r;i++){
  67. for(int j=0; j<c;j++){
  68. ans += arr[i][j];
  69. }
  70. }
  71.  
  72. printf("%d\n", ans+2);
  73. return 0;
  74. }
  75.  

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

https://www.acmicpc.net/problem/14891

 

14891번: 톱니바퀴

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터

www.acmicpc.net

 

위 문제는 시뮬레이션 문제로 자성을 가진 톱니바퀴의 극에 따라 k번 회전 시켰을 때,

톱니바퀴의 변화를 잘 구현해야하는 문제이다.

 

톱니바퀴는 다음과 같이 반시계방향 / 시계방향으로 회전할 수 있다.

 

톱니바퀴의 수는 다음과 같이 4개로 고정돼 있다. 그리고 맞닿아 있는 극이 다를 경우 회전이 영향받는다. 즉, 만약 1 번 톱니바퀴가 반시계방향으로 회전하는 경우 2번째 톱니바퀴의 맞닿아 있는 극이 서로 다르므로, 2번 째 톱니바퀴는 반대방향인 시계방향으로 회전한다. 그리고 2번 톱니바퀴와 3번 톱니바퀴의 맞닿아 있는 극은 같기 때문에 2번이 회전할 때 3번 톱니바퀴는 회전하지 않는다.

 

 

 

그럼 문제는 이해했고, 회전을 어떻게 구현할까.

CPP 에는 rotate 라는 함수를 지원한다. 입력에서 8개의 정수로 N,S 극을 표현하기 때문에, 회전 시 rotate함수로 배열을 적절히 회전시킬 수 있다. 만약 rotate를 사용하지 않는다면, 각 톱니바퀴의 현재 left / right 의 극 index를 저장하는 방법이 있겠다. 

 

개인적으로 시뮬레이션 문제를 풀 때는 직관적인 것이 풀기 편해 rotate를 사용했다.

 

# rotate 사용법

#include <vector>
#include <iostream>
#include <algorithm>
 
auto print = [](auto const& remark, auto const& v) {
    std::cout << remark;
    for (int n: v)
        std::cout << n << ' ';
    std::cout << '\n';
};
 
int main()
{
    std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};
 
    print("before sort:\t\t", v);
 
    // insertion sort
    for (auto i = v.begin(); i != v.end(); ++i) {
        std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);
    }
 
    print("after sort:\t\t", v);
 
    // simple rotation to the left
    std::rotate(v.begin(), v.begin() + 1, v.end());
 
    print("simple rotate left:\t", v);
 
    // simple rotation to the right
    std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());
 
    print("simple rotate right:\t", v);
}

Output :

before sort:            2 4 2 0 5 10 7 3 7 1 
after sort:             0 1 2 2 3 4 5 7 7 10 
simple rotate left:     1 2 2 3 4 5 7 7 10 0 
simple rotate right:    0 1 2 2 3 4 5 7 7 10

 

 

k 번 톱니바퀴를 회전 시키는데, 각 회전마다 왼쪽 / 오른쪽 회전이 전파돼야 한다. 

전파를 위해 propagate 함수를 정의 했다. propagate의 역할은 현재 회전한 톱니바퀴의 다음(왼쪽 / 오른쪽) 톱니바퀴의 회전여부를 검사하고, 만약 회전할 경우 그 다음 톱니바퀴로 전파한다.

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<vector>
  4. #include<algorithm>
  5. #define LEFT_T 6 // 왼쪽 톱니바퀴 index
  6. #define RIGHT_T 2 // 오른쪽 톱니바퀴 index
  7. using namespace std;
  8. int k;
  9. vector< vector<int> >t(4);
  10.  
  11. void left(vector<int>& v){
  12. rotate(v.begin(), v.begin()+1, v.end());
  13. }
  14.  
  15. void right(vector<int>& v){
  16. rotate(v.rbegin(), v.rbegin()+1, v.rend());
  17. }
  18.  
  19. void rotate(vector<int>& v, int t_dir){
  20. if(t_dir == 1) right(v);
  21. else left(v);
  22. }
  23.  
  24. void propagate(int prev_idx, int t_dir, int prop_dir){
  25. // prev_idx : 회전을 전파한 톱니바퀴
  26. // t_dir : 이전 톱니바퀴가 회전한 방향
  27. // prop_dir : propagation의 방향
  28.  
  29. int cur_t = prev_idx + prop_dir;
  30. if(cur_t < 0 || cur_t > 3) return;
  31.  
  32. int prev_tl = t[prev_idx][LEFT_T], prev_tr = t[prev_idx][RIGHT_T];
  33. int cur_tl = t[cur_t][LEFT_T], cur_tr = t[cur_t][RIGHT_T];
  34.  
  35. if(prop_dir == -1){ //left propagation
  36. if(cur_tr != prev_tl){
  37. propagate(cur_t, -t_dir, prop_dir);
  38. } else return;
  39. } else {
  40. if(prev_tr != cur_tl){ // right propagation
  41. propagate(cur_t, -t_dir, prop_dir);
  42. } else return;
  43. }
  44. rotate(t[cur_t], -t_dir);
  45. }
  46.  
  47. int main(){
  48. for(int i=0;i<4;i++){
  49. for(int j=0; j<8; j++){
  50. int m;
  51. scanf("%1d", &m);
  52. t[i].push_back(m);
  53. }
  54. }
  55. scanf("%d", &k);
  56. for(int i=0; i<k; i++){
  57. int cur_t, rot;
  58. scanf("%d%d", &cur_t, &rot);
  59. cur_t -= 1;
  60.  
  61. // 왼쪽 전파
  62. propagate(cur_t, rot, -1);
  63. // 오픈쪽 전파
  64. propagate(cur_t, rot, 1);
  65.  
  66. // 현재 톱니바퀴 회전
  67. rotate(t[cur_t], rot);
  68. }
  69.  
  70. int ans = 0;
  71. for(int i=0;i<4;i++){
  72. ans += t[i][0] << i;
  73. }
  74. printf("%d\n",ans);
  75. return 0;
  76. }
  77.  

 

 

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

https://www.acmicpc.net/problem/14503

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

www.acmicpc.net

 

위 문제는 시뮬레이션 문제이며, 구현만 잘 하면 쉽게 풀 수 있다.

시뮬레이션 문제를 푸는 것에 있어 가장 중요한 점은 동작과정을 정확히 이해하고, 그대로 구현해야 한다는 점인 것 같다.

 

위 로봇 청소기 문제는 동작은 간단하지만 현재 바라보고 있는 방향이 가장 중요하다.

 

2번 째 행동이 a, b, c, d 4가지 경우가 있는데, 크게 a,b 와 c,d 로 묶을 수 있을 것 같다.

a,b 는 왼쪽 방향으로 돌아가며 순차적으로 탐색해나가는 과정의 조건이고, c,d는 4방향을 모두 탐색한 후의 행동이다.



시뮬레이션 문제에서 동작은 하나씩 모두 잘게 쪼개는 것이 중요하다. 이 문제에서는 현재 바라보는 방향이 가장 중요하므로, 

신경쓰도록 하자.

 

직접 동작을 쪼개보면 알겠지만, 로봇이 c 조건에 부합돼 후진해야 할 때 현재 바라보는 방향처음 진입한 방향의 오른쪽 방향이다. 로봇은 현재 바라보는 방향에서 왼쪽 방향을 탐색하기 때문에 4방향 모두 탐색하는 시점은 3번 회전한 뒤이다.

(처음 북쪽을 봤다면 : 서쪽탐색 후 왼쪽 회전 ->  남쪽 탐색 후 왼쪽 회전 -> 동쪽 탐색 후 왼쪽 회전 -> 북쪽 탐색하면 4방향 모두 탐색조건 부합하므로 현재 방향은 동쪽)

 

d 조건에 부합되는 순간 모든 탐색과정이 종료해야 한다.

 

소스코드

 

  1. #include<stdio.h>
  2. int n,m,src_y, src_x, src_d, arr[55][55];
  3. int dy[4] = {-1,0,1,0}, dx[4] = {0, 1, 0, -1};
  4. int visited[55][55], ans;
  5.  
  6. int turn_left(int d){
  7. return d-1 >= 0 ? d-1 : 3;
  8. }
  9. int solve(int y,int x, int d){
  10. visited[y][x] = 1; // num 1
  11.  
  12. int clean = 0;
  13. for(int i = 0; i < 4; i++){ // num 2
  14. int left = turn_left(d);
  15. int ny = y + dy[left], nx = x + dx[left];
  16. if(!arr[ny][nx] && !visited[ny][nx] && ny >=0 && nx >=0 && nx < m && ny < n){
  17. d = left;
  18. if(solve(ny, nx, d) == -1) return -1;
  19. clean = 1;
  20. } else
  21. d = left;
  22. }
  23. if(!clean){
  24. int ny = y-dy[d], nx= x-dx[d];
  25. if(!arr[ny][nx] && ny >= 0 && nx >= 0 && nx < m && ny < n){
  26. if(solve(ny, nx, d) == -1) return -1;
  27. } else {
  28. return -1;
  29. }
  30. }
  31. return 0;
  32. }
  33. int main(){
  34. scanf("%d%d %d %d %d",&n,&m,&src_y, &src_x, &src_d);
  35. for(int i=0;i<n;i++){
  36. for(int j=0;j<m;j++){
  37. scanf("%d", &arr[i][j]);
  38. }
  39. }
  40.  
  41. solve(src_y, src_x, src_d);
  42.  
  43. for(int i=0; i < n; i++){
  44. for(int j=0; j < m; j++){
  45. ans += visited[i][j];
  46. }
  47. }
  48. printf("%d\n", ans);
  49. return 0;
  50. }

 

 

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

https://www.acmicpc.net/problem/1969

 

1969번: DNA

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오

www.acmicpc.net

 

이 문제는 brute force 문제이다

 

DNA 염기 { A, C, G, T } 로 구성된 문자열이 N개 주어졌을 때, 각 자리수의 가장 빈도수가 많은 문자만 뽑으면 된다

 

문제에서는 Hamming distance 등 생소한 용어로 혼란을 주지만 문제 자체만 보면 각 자리수의 빈도수가 가장 높은 문자만

 

뽑으면 그것이 전체 DNA sequence 중 가장 차이가 적은 문자열이 된다

 

counting을 위해서 map 자료구조를 이용했고, 사전 순을 맞추기 위해 max 를 검사할 때 사전 순으로 검사하도록 한다

 

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<vector>
  3. #include<string>
  4. #include<map>
  5. using namespace std;
  6. int n,m;
  7. char buf[55];
  8. char order[4] = { 'A', 'C', 'G', 'T'};
  9.  
  10. int main(){
  11. scanf("%d %d",&n,&m);
  12. vector<string> v;
  13. for(int i=0;i<n;i++){
  14. scanf(" %s", buf);
  15. v.push_back(string(buf));
  16. }
  17. vector< pair<char, int> > ans;
  18. for(int i=0; i<m; i++){
  19. map<char, int> c;
  20. for(int o=0; o<4; o++)
  21. c[order[o]] = 0;
  22. for(int j=0; j<n; j++){
  23. c[v[j][i]] += 1;
  24. }
  25. int max_ = 0, diff = 0;
  26. char d;
  27. for(int o=0; o<4; o++){
  28. diff += c[order[o]];
  29. if(max_ < c[order[o]]){
  30. max_ = c[order[o]];
  31. d = order[o];
  32. }
  33. }
  34. ans.push_back(make_pair(d, diff-max_));
  35. }
  36. int cnt = 0;
  37. for(int i=0;i<ans.size();i++){
  38. printf("%c", ans[i].first);
  39. cnt += ans[i].second;
  40. }
  41. printf("\n%d\n", cnt);
  42. return 0;
  43. }

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24

API Key를 발급받았으면, 어떤 템플릿으로 메일을 보낼지 미리 만들어 둘 수 있다

 

SendGrid 에서는 `Dynamic Templates` 를 제공한다 

 

 

Email API > Dynamic Templates

 

`Create a Dynamic Template` 를 클릭해 하나 만들어보자

 

필자는 회원가입에서 많이 사용하는 `email confirmation` 을 위한 템플릿을 만들었다

 

 

 

생성한 'email_confirmation' 템플릿

 

Template 은 drag & Drop 으로 image, text, button 등 쉽게 layout 을 구성할 수 있다.

 

가장 중요한 점은 mail 을 보낼 때, 받는 사람에 따라 정보를 다르게 보여줘야 한다 (이름, 메일 등)

 

템플릿에서 {{ 변수명 }} 으로 설정해놓고 나중에 request_body 에 맞게 데이터를 보내면 된다

(자세한 내용은 Handle bar 문서 참조 https://sendgrid.com/docs/for-developers/sending-email/using-handlebars/)

 

subject 는 메일의 제목, preheader 는 미리보기 내용이다

 

필자가 만든 템플릿. (디자인을 못하는게 증명)

 

 

유용한 팁 중 하나는 버튼 URL도 request_body를 통해 동적으로 설정해줄 수 있다

 

장점은 당연한 얘기겠지만, 나중에 end-point url이 변경되거나 할 때, Sendgrid 템플릿 변경하지 않고 코드만 변경하면 되기 때문에 편하다

 

button URL > dynamic 설정 가능

 

 

저장하고 나오면,. 각 템플릿에 version 도 명시할 수 있다

 

request_body에서 버전정보를 넣어주면 해당 템플릿을 사용할 수 있다

 

여기까지 했으면 준비는 다 끝났다

'개발 > Utils' 카테고리의 다른 글

[SendGrid 로 메일 보내기] 1. API Key 발급  (0) 2021.05.23

 

SendGrid 는 하루에 약 2000 개의 메일을 무료로 보낼 수 있다

API key를 발급받아 사용하면 각자 사용하는 프로그래밍 언어로 메일을 쉽게 보낼 수 있다

 

가입한 후 Setting > API key 에서 API 키를 발급받아야 한다. `Create API Key` 버튼을 클릭.

 

Settings > API Keys

 

 

적당히 이름을 정하고 해당 API key에 부여할 권한을 선택.

 

Create API Key

 

`Create & View` 버튼을 누르면, 발급된 API Key를 보여주는데, 다시 보여주지 않으니 복사해두자 !

복사해두지 않으면 잃어버림

 

 

 

'개발 > Utils' 카테고리의 다른 글

[SendGrid 로 메일 보내기] 2. 메일 Template 만들기  (1) 2021.05.23

https://www.acmicpc.net/problem/2529

 

2529번: 부등호

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제

www.acmicpc.net

 

문제의 조건 

1. k 는 2보다 크거나 같고, 9보다 작거나 같다

2. k+1개의 숫자는 서로 다른 숫자이다

3. k개의 부등호에 맞는 값 중 최대값, 최소값을 구해야 한다

 

 

부등호에 '<=', '>=' 이 존재하고 서로 다른 숫자라는 조건이 없었다면, 경우의 수가 1e10 이 돼 TLE이 나겠지만, 

서로 다른 k+1 개의 수를 찾기 때문에 (k+1)! 의 경우의 수만 찾으면 된다.

 

처음에는 재귀함수를 통해 백트랙킹으로 풀었다.

 

소스코드 (백트랙킹)

숫자가 최대 10개이므로 비트마스크로 사용한 숫자를 체크하며, 조건이 맞지 않으면 재귀를 탈출하고, 

k+1 개의 숫자를 다 채우면 1을 리턴하면서 종료된다.

 

최솟값은 0부터 시작해서 찾아야하고, 최댓값은 9부터 시작해서 내려가며 찾아야하기 때문에

같은 재귀라도 반복문을 달리 사용해야하는 번거로움이 있었다.

 

  1. #include<stdio.h>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<string>
  5. using namespace std;
  6. typedef long long ll;
  7. int k;
  8. char karr[11];
  9. string min_="", max_="";
  10. bool inline chk(int a, char c, int b){
  11. return c == '>' ? a>b : a<b;
  12. }
  13. string num(vector<int>& ans){
  14. string s = "";
  15. for(int i=0; i < ans.size(); i++){
  16. s += ans[i] + '0';
  17. }
  18. return s;
  19. }
  20. int solve(vector<int>& ans, int visited, int p, int ismax){
  21. if(p == k) {
  22. return 1;
  23. }
  24. int cur = ans[p];
  25. int init = ismax ? 9 : 0;
  26. int iter = ismax ? -1 : 1;
  27. int end = ismax ? -1 : 10;
  28. for(int pp1=init; pp1 != end; pp1+=iter){
  29. if(visited & (1<<pp1))
  30. continue;
  31.  
  32. if(chk(cur, karr[p], pp1)){
  33. ans.push_back(pp1);
  34. if(solve(ans, visited | (1<<pp1), p+1, ismax))
  35. return 1;
  36. ans.pop_back();
  37. }
  38. }
  39. return 0;
  40. }
  41. string solve_(int i, int ismax){
  42. int visited = 0;
  43. vector<int>ans;
  44.  
  45. ans.push_back(i);
  46. visited |= (1<<i);
  47. if(solve(ans, visited, 0, ismax)){
  48. return num(ans);
  49. }
  50. return "";
  51. }
  52. int main(){
  53. scanf("%d", &k);
  54. for(int i=0;i<k;i++){
  55. scanf(" %c", &karr[i]);
  56. }
  57.  
  58. for(int i=0; i<10; i++){
  59. min_ = solve_(i, 0);
  60. if(min_ != "") break;
  61. }
  62.  
  63. for(int i=9; i>=0; i--){
  64. max_ = solve_(i, 1);
  65. if(max_ != "") break;
  66. }
  67. printf("%s\n%s\n", max_.c_str(), min_.c_str());
  68. return 0;
  69. }

 

 

풀다보니 최소값은 0~k 의 숫자, 최대값은 9~9-k 까지의 숫자만 사용하면 부등호를 만족하는 순서를 찾을 수 있기 때문에,

k 가 9인 경우 최대 10! 까지만 돌기 때문에 조합으로 풀 수 있겠다 생각됐다.

 

 

소스코드 (조합)

조합으로 푸니 코드가 깔끔해졌다.. 진작 이렇게 풀걸

처음부터 조합으로 풀 생각을 할 수 있도록 문제 해결 전략을 잘 세워야겠다..

 

  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<vector>
  4. using namespace std;
  5. int k;
  6. char karr[10];
  7. bool inline chk_(int a, char c, int b){
  8. return c == '>' ? a>b : a<b;
  9. }
  10. int chk(vector<int>& cand){
  11. for(int i=0; i<k; i++){
  12. if(!chk_(cand[i], karr[i], cand[i+1]))
  13. return 0;
  14. }
  15. return 1;
  16. }
  17. int main(){
  18. scanf("%d", &k);
  19. for(int i=0; i<k;i++)
  20. scanf(" %c", &karr[i]);
  21.  
  22. vector<int> min_ = vector<int>(k+1), max_ = vector<int>(k+1);
  23. for(int i=0; i<=k; i++){
  24. min_[i] = i;
  25. max_[i] = 9-i;
  26. }
  27.  
  28. do{
  29. if(chk(min_)) break;
  30. }while(next_permutation(min_.begin(), min_.end()));
  31.  
  32. do{
  33. if(chk(max_)) break;
  34. }while(prev_permutation(max_.begin(), max_.end()));
  35.  
  36. for(int i=0; i<=k; i++)
  37. printf("%d",max_[i]);
  38. printf("\n");
  39. for(int i=0; i<=k; i++)
  40. printf("%d",min_[i]);
  41. printf("\n");
  42. return 0;
  43. }

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04

원래 맥북에 관심이 크게 없었는데...

회사 개발환경이 Windows 호환이 잘 안되는 것들이 몇 개 있어서 맥북을 하나 사야하나 고민하게 됐다..

지금 맥북 프로가 있지만, 이전에 다니던 대학원 연구실꺼라 학교자산으로 잡혀서 반납해야한다.. ㅜ (지금은 내 맘대로 대여 중...ㅎㅎ)

 

맥북에 관심 없던 이유 중 하나는 일단 가격이 비싼게 컸고, 연구실 맥북(새 제품) 을 받아서 1년 조금 넘게 사용했을 때 부터 노트북 하판?이 수평이 안맞게 됐다. 아마 노트북연결해서 쓰고 했는데, 발열 때문에 하판이 늘어난 듯.. 

 

1년 남짓 썼는데 발열 때문에 하판이 늘어나서 달가닥 달가닥 거리니, 비싼 값을 못한다고 생각해서..

내 돈 주고 안사서 다행이다..? 라고 생각했었다 ㅋㅋㅋ

 

취업하면 데스크탑 하나 맞춰야지(게임해야되니까) 하고 있었는데,,  맥북부터 사야될 듯하다..

언제까지 졸업한 연구실 노트북 빌려쓰고 있을 순 없으니.....

 

ItSub 잇섭님 영상보니 이번 M1칩 탑재된 MacBook이 꽤 잘나온 것 같다. 반응속도도 빠르고. 발열도 적고.

내가 개발하는 것들이 인공지능쪽도 아니고, Restful API 만들고하는 정도다보니 MacBook Pro까지는 필요없을 것 같고, 

메모리 넉넉하게 Air 사면 딱 맞을 것 같다.

 

 

메모리 16GB로 변경하니 190만원.. 음

 

 

 

데스크탑은 언제 사지.. (그래픽카드 가격 좀 내려갔으면)

 

취업하고 돈을 벌어서 다행이긴한데,, 돈 쓸일이 많아서 앞으로 월급이 계좌를 스쳐 지나갈 것 같다...

 

소프트웨어 개발자로서 도태되지 않고 성장할 수 있는 몇 가지 원칙을 정리한 글이 있어 퍼옵니다.

(원문: http://www.allofsoftware.net/2012/08/blog-post_6.html )

 

1. 관리와 개발 일을 분리하라.

 관리자가 될 것이 아니라면 관리 일은 아무리 열심히 해도 개발자 경력에 별 도움이 안된다. 하지만 회사의 사정상 싫어도 관리 일을 떠맡을 수 밖에 없는 경우가 있다. 그런 경우에도 본인의 정체성을 명확히 해야 한다. 개발과 관리 일을 섞어서 하지 말고 구분해야 한다. 즉, 자신이 하고 있는 일 중에서 어떤 일이 관리고 어떤 일이 개발인지를 구분해야 한다.

 개발이 주업이고 관리는 부업임을 명확히 해야 하고, 언제든지 관리 일은 버릴 수 있도록 준비를 해야 한다.

 

2. 경력과 수준에 맞는 일을 해라. 

 경력이 많아지면 그게 걸맞는 수준의 일들을 해야 한다. 경력이 늘어가도 똑같은 일을 그저 더 빠르고 능숙하게 하고 있다면 밥값을 못하고 있을 가능성이 높다. 그런 상태라면 개발자 경력을 오래 보장 받기는 어렵다. 결국 도태될 것이다.

경력이 늘어갈수록 누구나 할 수 있는 일들은 후배에게 물려 주어야 한다. 그리고는 설계, 분석 업무의 비중을 높이고 회사의 기술 전략에 신경을 써야 한다. 경력이 더욱 늘어갈수록 자신의 팀 뿐만 아니라 타팀, 더 나아가서 회사 전체의 프로젝트에 기여를 해야 한다.

 

 이를 위해 문서화는 필수다. 개발 내용이 문서로 적혀 있어야 서로 리뷰가 가능하고 타팀의 프로젝트도 검토를 해서 나의 전문지식을 불어 넣을 수가 있다.

 

3. 권력욕을 버려라.

 개발자로서 계속 나아가겠다고 결심을 했다면 어쨌든 권력욕은 버려야 한다. 권력을 얻기 위한 거의 모든 행동은 개발 일과는 거의 관계가 없다. 방해만 될 뿐이다. 개발자는 권력보다는 뛰어난 기술력에서 자연스럽게 나오는 파워를 가져야 한다. 

 

4. 끊임 없이 코딩하라.

 개발자는 30년을 일해도 감독, 코치가 아니라 선수다. 코딩에서 손을 놓으면 급속도로 개발자의 길과 멀어진다. 주변을 보면 관리나 좀 하고 코딩은 전혀 안하면서 여기저기 감 놔라 대추 놔라 훈수를 두는 무늬만 개발자가 매우 많다. 이들은 개발자가 아니고 개발자였을 때 쌓아 놓은 지식의 약발도 별로 오래 가지 않는다.

 

5. 새로운 기술을 익혀라.

 꾸준히 새로운 기술을 익혀야 한다. 시간이 흐를수록 점점 더 많은 새로운 기술들이 나오고 있다. 이를 따라잡기는 보통 어려운 일이 아니다. 적절하게 시간 투자를 해야 한다. 모든 기술을 다 마스터 할 필요는 없다. 나중에 필요할 때 언제든지 생각이 나게 하면 된다. 필요할 때 필요한 만큼 더 익히면 된다.

 

6. 소프트웨어 개발 전문가로 포지셔닝을 하라.

 경영자가 본인을 소프트웨어 전문가로 믿도록 하라. 경영자가 기술 전략을 같이 의논하게 하고 기술 관련된 정책을 제대로 수립할 수 있도록 보좌하라. 

 

7. 후배들의 롤모델이 되어라.

 선임 개발자가 어떤 식으로 일하는지 보여주고 기술력에서 오는 파워를 보여줘라. 이는 본인을 위해서도 더 일하기 좋은 개발환경을 만드는데 도움이 되는 일이다.

 

 

 

공통 정보 정의하고 재사용하는 방법

+ Recent posts