코딩 초보 삐리리뽀옹이 나가신다

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/2042

2) 설명

전형적인 세그멘트 트리 문제다.

인풋에 숫자를 변경하는 인풋과 구간합을 구하는 인풋이 있다.

2. 풀이

1) 알고리즘

    : 세그먼트 트리

2) 풀이 설명

 세그먼트 트리를 사용해서 구간합을 구한다.

일반적인 방법은 O(N^2) (이중 반복문)인데 반해 세그먼트 트리를 사용하면 O(logN) 에 구할 수 있어서 시간복잡도를 줄일 수 있다.

풀이는 주석 정도로 설명하고 세그먼트 트리 알고리즘은 따로 포스팅해야겠다.

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

typedef long long LL;

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int segN, N, M, K;
	LL a, b, c;
	cin >> N >> M >> K;
	
	//1. N이상의 2의 제곱수 찾기 -> segN
	for(segN=1;N>segN;segN*=2);

	//2. segmentTree 공간 확보
	vector<LL> segmentTree(segN*2, 0);
	
	//3. 인풋 받기
	for(int i=segN;i<segN+N;i++)
		cin >> segmentTree[i];
	//4. segmentTree 생성
	for(int pat=segN*2-1;pat>1;pat--)
		segmentTree[pat/2] += segmentTree[pat];
	
	//5. 명령어 수행
	for(int i=0;i<M+K;i++){
		cin >> a >> b >> c;
		if(a == 1){
			//5-1. 숫자 변경
			b += segN - 1;
			LL gap = c - segmentTree[b];
			while(b>0){
				segmentTree[b] += gap;
				b /= 2;
			}
		} else if(a == 2) {
			//5-2. 구간합 출력
			b += segN - 1, c += segN - 1;
			LL answer = 0;
			while(b<=c){
				if(b%2 == 1) answer += segmentTree[b++];
				if(c%2 == 0) answer += segmentTree[c--];
				b /= 2;
				c /= 2;
			}
			cout << answer << "\n";
		}
	}

	return 0;
}

4. 느낀점

 - 기본 세그먼트도 트리 어렵습니다..  더 공부하겠습니다..

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/2841

2) 설명

손가락 많은 외계인이 악보대로 기타연주할 때 최소한의 손 움직임을 구하는 문제다.

움직임은 누를 때 1, 뗄 때 1 추가한다

만약 1번줄의 3프렛을 누른 상태에서 1번줄 5프렛을 누르고자 한다면 굳이 3프렛 누른 손을 뗄 필요 없이 5프렛을 바로 누르면 된다. 즉 손 움직임 카운트값이 1 증가한다.

이 상태에서 1번줄 2프렛을 쳐야 한다면 3프렛, 5프렛에 있는 손가락을 모두 떼야 한다. 즉 손 움직임 카운트 값이 2 증가하고 2프렛을 누르면서 총 3 증가하게 된다.

2. 풀이

1) 알고리즘

    : 스택

2) 풀이 설명

1번부터 6번 각 줄별로 스택을 만들었다. (총 6개, 스택 라이브러리 대신 벡터를 사용했다. 거의 동일하기 때문에..)

이후 줄별로 연주하는 프렛을 스택에 쌓았고 만약 스택의 마지막 값이 새로 누를 프렛보다 작다면 그냥 1번 스택에 새로 누를 프렛을 넣었다.

만약 스택 마지막 값이 새로 누를 프렛보다 크다면 작은 값이 나올 때까지 계속 스택에서 pop을 해나갔다.(pop 할 때마다 움직임 증가)

이때 스택 초기 선언할 때 원소 하나를 0값으로 넣어서 빈 스택을 참조하는 일을 방지했다. 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

#define LINE_NUM 6
#define MAX_FRET 300000

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, P;
	cin >> N >> P;
	int answer = 0;
	vector<vector<int>> stack(LINE_NUM+1, vector<int>(1, 0));

	int line, fret;
	for(int i=0;i<N;i++){
		cin >> line >> fret;
		while(stack[line].back() > fret){
			stack[line].pop_back();
			answer++;
		}
		if(stack[line].back() != fret){
			stack[line].push_back(fret);
			answer++;
		}
	}
	cout << answer << endl;

	return 0;
}

4. 느낀점

 - 다른 분들 풀이에 비해 코드 길이는 좀 짧지만 속도가 좀 느렸다.(내 풀이는 88ms, 다른 분들은 80ms)

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/14891

2) 설명

삼성 기출인 것 같다. 시뮬레이션 문제..

톱니바퀴 4개를 두고 i번째 톱니를 시계방향 혹은 반시계방향으로 돌리는 문제다.

이때 1, 2, 3, 4 톱니들이 서로 맞물려 있는 바퀴의 값이 다를 때만 옆의 톱니바퀴를 반대방향으로 돌린다.

예를 들어 2번 톱니를 돌리는데 돌리기 전 1번, 2번 톱니가 맞물린 쪽이 S, N으로 다르다면 1번도 돌리고 S, S로 같다면 돌리지 않는다.

다 돌리고 나서 각 톱니의 12시 방향에 있는 값을 구하면 된다.

2. 풀이

1) 알고리즘

    : 시뮬레이션

2) 풀이 설명

톱니를 돌리는 걸 처음에 직접 구현하려다가 그냥 rotate 함수를 썼다.

사실 시뮬레이션 문제를 잘 안 풀어봐서 처음 써보다보니 음의 방향으로 돌리는 걸 v.begin()기준으로 해서 헷갈렸다.(v.end() 기준으로 해서 조금 더 간단하게 할 수 있었다)

어떤 톱니까지 돌릴지는 rotate 전에 diff라는 vector를 사용해서 미리 구했다.

그리고 diff에 체크된 배열들을 gear_idx 톱니(입력으로 돌리는 톱니)를 기준으로 왼쪽, 오른쪽으로 돌려나갔다.

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

#define N_GEAR 4
#define N_WHEEL 8

using namespace std;


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int K, gear_idx, direction, answer = 0;
	vector<vector<bool>> gear(N_GEAR+1, vector<bool>(N_WHEEL, false));
	string input;
	for(int i=1;i<=N_GEAR;i++){
		cin >> input;
		for(int j=0;j<N_WHEEL;j++){
			gear[i][j] = input[j]=='0'? 0 : 1;
		}
	}

	cin >> K;
	vector<bool> diff(5, false);

	while(K--){
		cin >> gear_idx >> direction;
		
		fill(diff.begin(), diff.end(), false);
	
		int left_direction = -direction;
		int right_direction = -direction;

		for(int i=gear_idx+1;i<=N_GEAR;i++)
			diff[i] = gear[i][6] != gear[i-1][2];

		for(int i=gear_idx-1;i>0;i--)
			diff[i] = gear[i][2] != gear[i+1][6];
	
		rotate(gear[gear_idx].begin(), (direction==1? gear[gear_idx].end() - 1 : gear[gear_idx].begin() + 1), gear[gear_idx].end());

		for(int i=gear_idx+1;i<=N_GEAR && diff[i];i++, left_direction *= -1)
			rotate(gear[i].begin(), (left_direction==1? gear[i].end() - 1 : gear[i].begin() + 1), gear[i].end());

		for(int i=gear_idx-1;i>0 && diff[i];i--, right_direction *= -1)
			rotate(gear[i].begin(), (right_direction==1? gear[i].end() - 1 : gear[i].begin() + 1), gear[i].end());
	}
	vector<int> squared = {0, 1, 2, 4, 8};
	for(int i=1;i<=N_GEAR;i++){
		if(gear[i][0])
			answer += squared[i];
	}
	cout << answer << "\n";


	return 0;
}

4. 느낀점

 - 시뮬레이션은 단순한 개념을 깔끔하고 효율적으로 구현해내야 하는 게 중요한 것 같다

 - 단순해보인다고 냅다 구현하려다 보면 코드 더러워지면서 혼난다.. 내 코드다 많이 더러워서 나중에 다시 손봐야 할 것 같다..

1. GIT CLI 사용 시 로그인 계정 저장하기

 1) git config credential.helper store

      -> 입력 후 push하여 로그인 인증하면 다음부터 반영구적으로 로그인 유지

 2) git config credential.helper store --global

      -> 입력 후 push하여 로그인 인증하면 다음부터 모든 프로젝트에서 반영구적으로 로그인 유지

 3) git config credential.helper cache

      -> 입력 후 push하여 로그인 인증하면 다음부터 일정 시간 동안 로그인 유지(기본 15분)

 4) git config credential.helper 'cache --timeout=3600'

      -> 입력 후 push하여 로그인 인증하면 다음부터 직접 지정한 일정시간(초 단위) 동안 로그인 유지

1. 깃허브(Github) 가입하기

 - https://GitHub.com 가입하기

2. 깃(Git) 설치

 - https://git-scm.com/downloads OS에 맞게 다운 받기

 - 윈도우 아이콘 옆 돋보기에서 Git Bash 입력 후 찾아서 실행할 수 있으면 성공

3. 로컬저장소 만들기

 1) 폴더 내에서 우클릭 후 Git Bash Here 클릭

 2) bash 창에 git init 입력

      -> 폴더 안에 .git 이라는 폴더가 생성되면 성공(안 보이면 보기 - 숨긴 항목 체크)

 3) git config 설정

      git bash 창 진입(깃헙에 가입했던 이메일 주소, 이름으로 설정)

      - git config --global user.email "이메일 주소"

      - git config --global user.name "이름"

 4) README.md 파일 생성

      - README.md : 프로젝트 대략적인 설명 파일

      - 일반 텍스트 파일 생성하듯이 생성하고 확장자만 md로 바꾸기(굳이 안 바꾸고 README.txt 로 남겨둬도 됨)

 5) commit할 파일 or 폴더 추가

      - git add README.md

 6) commit 하기

      - git commit -m "Add README.md"

      - 5번에서 추가했던 파일들에 대해 "Add README.md" 커밋메시지(-m "Commit msg" : 커밋 메시지 = "Commit msg"라는 의미)와 함께 커밋

4. 이전 커밋으로 돌아가기

 1) git log

      - commit log들을 보여준다

      - commit [COMMIT ID] 의 [COMMIT ID] 부분 복사(앞 7자리만 복사해도 된다)

 2) git checkout [COMMIT ID]

      - 복사했던 [COMMIT ID]로 git checkout 하면 그 커밋으로 돌아간다

 3) git checkout -

      - 최신 커밋 상태로 돌아오기

5. GitHub 원격 저장소 사용하기

 1) GitHub 홈페이지 접속해서 우상단에 + 클릭 -> New repository 클릭 후 저장소 생성

 2) 로컬 저장소 - 원격 저장소 연동하기

      - 해당 repository 들어가서 go to file, add file, code 중 code 클릭 후 HTTPS SSH [git 주소] 옆에 아이콘 클릭(git 주소 복사)

      - git remote add origin [git 주소]

      - git 주소 칸에 우클릭 하면 붙여넣어짐

 3) commit한 상태 원격 저장소에 push 하기

      - git push origin master (master branch에 여태까지 commit한 것들을 올리겠다는 의미)

 4) Github repository에 README.md 파일이 추가되어 있으면 성공

6. 원격 저장소에서 내려받기

 - 다른 폴더에서 프로젝트를 내려받는 방법

 1) 다른 폴더로 이동

 2) git clone [git 주소] .

      - 마침표 안 찍으면 폴더 하나 더 깊숙이 들어감

      - ex) temp 폴더에서 exercise 프로젝트 내려받기

            - 마침표 찍었을 때 : temp - exercise - 프로젝트 소스

            - 마침표 안 찍을 때 : temp - 프로젝트 소스

 3) 원격 저장소에 push 하기

      - 5의 3) 과정과 똑같이 하면 된다

 4) 원격 저장소 최신 상태 받아오기

      - 다른 사람이 push 해놓은 상태를 받아오기

      - git pull origin master

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/9656

2) 설명

돌 게임(9655)이랑 다른 게 없는 문제같다.. 마지막 돌을 가져간 사람이 이기네 지네 차이일 뿐...

2. 풀이

1) 알고리즘

    : DP, 수학

2) 풀이 설명

돌 게임 때는 알고리즘이 DP로 분류돼 있어서 DP로 풀었는데 생각해보니까 DP를 쓸 필요가 없는 것 같다..

문제에서 분류해준 알고리즘에 갇혀서 효율적인 풀이를 생각하지 못 했다..

그냥 N이 홀수인지 짝수인지만 판별하면 됐다.. 왜냐하면 N-2번째 돌을 가져가는 사람이 N번째 돌을 가져갈 수밖에 없기 때문이다.(상대방이 N-1번째 돌을 하나 가져가면 N번째 돌을 가져가야 하기 때문) 그럼 결국 N이 홀수일 때는 무조건 상근이가, 짝수일 때는 창영이가 마지막 돌을 가져갈 수밖에 없어진다.

3. 코드

/*
	돌게임2
	DP
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	cout << (N%2? "CY\n" : "SK\n");
	
	return 0;
}

4. 느낀점

1. 고정관념에 갇히지 말자!

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/2631

2) 설명

문제 자체는 이해하기 쉽다. 간단하게 말하면 N명의 아이들이 무작위로 서있는데 얘네를 순서에 맞게 줄세우게 만드는 최소 이동 횟수를 구하면 된다. 예를 들어 1 4 2 3 6 7 5 이렇게 서있으면 1 2 3 4 5 6 7로 세우면 된다. 하지만 나는 푸는 데 오래 걸렸다..

2. 풀이

1) 알고리즘

    : DP

2) 풀이 설명

LCS를 사용하면 풀이는 간단하다. 왜냐하면 가장 많이 정렬되어 있는 집단을 고르고 나머지만 옮기는 게 가장 적게 아이들을 이동시키며 줄세울 수 있는 방법이기 때문이다.

위에 예에서 1 2 3 6 7 이 LCS가 된다. 그러면 4, 5만 제자리 찾아서 옮겨주면 되니까 최소 이동 횟수는 2가 된다.

사실 LCS는 얼마 전에도 풀고 여러번 했었는데, 머리가 나빠선지 응용 문제가 나오니까 LCS가 생각도 안 났다.

한 이틀 정도 헛다리만 집었지만 다행이도 스스로 LCS를 생각해서 풀 수 있었다.

솔직히 LCS를 풀어본 경험이 있다면 굉장히 쉬운 문제라고 생각하지만 나는 이틀을 고민해서 찾아낸 만큼 기분이 아주 좋았다.

3. 코드

/*
	줄 세우기
	DP
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	vector<int> children(N, 0), dp(N, 1);
	
	for(int i=0;i<N;i++)
		cin >> children[i];
	
	for(int i=0;i<N;i++)
		for(int j=i-1;j>=0;j--)
			if(children[i] > children[j])
				dp[i] = max(dp[i], dp[j] + 1);

	cout << N - *max_element(dp.begin(), dp.end()) << "\n";

	return 0;
}

4. 느낀점

1. 응용 문제를 자주 풀어보자!

10월 25일에 2020년도 하반기 SK C&C 코딩테스트를 치뤘다.

총 4문제(알고리즘 3문제, SQL 1문제)가 나왔다.

난이도는 상당히 쉬웠다고들 한다. (내 체감 난이도 : 2단계)

하지만 나는 SQL을 정말 오랜만에 접해서 빨리 풀어야 할 SQL 문제에 시간을 오래 들이고 심지어 맞게 풀었는지도 잘 모르겠다.

내 풀이 기준 1번은 우선순위 큐, 2번은 단순 구현, 3번은 BFS+완전탐색으로 풀 수 있었다.

1, 2번은 잘 푼 것 같은데 3번을 풀기 직전에 배탈이 나서 주어진 테케는 통과시켰지만 제대로된 검토와 최적화는 못 하고 제출해버렸다.

조지아 커피를 한번에 많이 마시면 안 된다는 좋은 교훈을 얻었다.

집에서 문제 복기하면서 보니 1, 2번은 괜찮았지만 3번은  메모리 사용을 정말 비효율적으로 했다는 것을 깨달았다... 또 코드 가독성도 엉망이었다..

일단 내 생각으로는 BFS와 완전탐색으로 풀었지만 완전탐색이 맞는지는 잘 모르겠다. N개의 라이더와 N개의 상품을 매치시키며 최소 비용을 찾아야하는데 N명의 라이더에서 상품으로의 거리가 각각 다르길래 배탈나서 정신도 없고 그냥 완탐으로 풀었다. (N이 10 이하이기도 해서 급한 마음에 될 거라고 생각했다...) 근데 복기하면서 생각해보니 최악의 경우에 10!이니까 연산이 엄청 크긴 할 것 같다... 거기다 BFS 8x8 보드에 20번 돌리는 것까지 하면(이건 상대적으로 얼마 안되지만) 아마 모든 테케를 통과하기는 힘들 것 같다.. 그렇다고 다른 방법도 당장 생각나지 않는다..ㅎㅎ

이번 코테를 계기로 느낀 점은 두 가지다.

1. 커피 천천히 조금씩 마시기.

2. SQL 공부하기.