백준[16401] 과자 나눠주기
2021. 10. 14. 12:38
Algorithm/BOJ
문제 링크 http://icpc.me/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN www.acmicpc.net 풀이 결정문제로 바꿔 이분 탐색을 하여 풀 수 있다. m명에게 길이가 n인 과자를 줄 수 있는지 없는지 판단하는 문제로 바꿔, 길이 n을 이분탐색을 돌리면 된다. 이렇게 풀면 O(NlogN)에 풀 수 있다. 코드 #include int arr[1000006]; int main() { int m, n; scanf("%d %d", &m, &n)..
백준[2239, 2580] 스도쿠
2021. 10. 14. 01:20
Algorithm/BOJ
문제 링크 http://icpc.me/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 2239번과 2580번이 아예 똑같은 문제인데 왜 두 문제가 있는지는 잘 모르겠다. 한번 풀고 복습까지 하라는 백준님의 말씀이실지도... 이 문제는 백트레킹을 사용하여 풀 수 있다. 모든 행, 열, 박스들에 무슨 수가 들어있는지 미리 저장해 두고 빈칸에 백트레킹을 하며 1~9까지 넣어보면 된다. row [n][k] : n열에 숫자 k가 있다는 의미이다. 그리고 끝까지 도달하면 출력을 하고 더 이상 백트레..
[git] git이란?
2021. 10. 13. 22:43
git
Git git은 분산 버전 관리 시스템이다. 이 말만 들으면 무엇을 할 수 있는 시스템인지 이해가 되지 않을 것이다. 쉽게 말하자면 깃은 여러 버전을 백업해두고, 그 백업 기록을 남겨놔 언제든지 참조하고, 되돌아갈 수 있으며 여러 명의 개발자가 동시에 작업을 해줄 수 있도록 도와주는 시스템이다. 로컬에 저장되는 git 데이터를 로컬 저장소인 github와 같은 사이트에 업로드한다면, 그 깃 데이터를 가지고 여러 개발자가 다른 장소에서 작업을 할 수 있으며, 코드뿐만 아니고 작업했던 백업 기록까지 공유할 수 있다. 또한 백업을 하는 것을 커밋이라고 하는데 각 커밋들마다 메시지를 남겨, 이 커밋은 어떤 내용이 수정되었는지 메모를 하여 다른 개발자들이 쉽게 확인할 수 있게 해 준다.
[git] pull vs fetch
2021. 10. 13. 22:13
git
pull vs fetch pull은 원격 저장소에 있는 데이터를 가져오는 동시에 로컬에 있는 기존의 로컬 브랜치와 merge까지 자동으로 해준다. git pull [원격 저장소 이름] [브랜치 이름] fetch는 원격 저장소에 있는 데이터를 가져오기만 하여 merge를 따로 해줘야 한다. fetch를 사용하는 이유는 로컬에 있는 데이터를 그대로 보존하면서 원격 브랜치 데이터의 수정사항을 확인할 수 있다. git fetch [원격 저장소 이름] [브랜치 이름]
[git] merge, rebase 브랜치를 합치는 방법
2021. 10. 13. 22:05
git
merge vs rebase merge와 rebase 모두 브랜치를 합치는 명령어지만 약간의 차이가 있다. merge는 아래 사진과 같이 깃의 커밋들의 로그가 두 브랜치가 합쳐지는 형태로 남는다 rebase는 merge처럼 합쳐지는 형태로 기록이 남지 않고 합쳐질 브랜치가 앞에 붙는 형식으로 선형적으로 남는다. rebase는 로그가 선형적으로 남아 기록이 더 깔끔하게 남을 수 있지만, 없어지는 커밋이 생길 수도 있다. 반면에 merge는 로그가 합쳐지는 두 가지 갈래 형태로 남아 깔끔하진 않을 수 있지만 모든 커밋이 보존된다. merge merge를 할 때 우선 남아야 하는 브랜치로 이동한 후에 merge를 해야 한다. git checkout [남아야할 브랜치 이름] git merge [합칠 브랜치 이름..
[git] branch
2021. 10. 13. 21:45
git
branch 브랜치란? git에서 새로운 커밋이 이어지는 가지를 만드는 기능이다. 브랜치를 새로운 기능을 추가하거나, 버그를 수정하는 등 다양한 상황에 원본 파일을 남겨놓고 새로운 무언가를 할 때 많이 사용한다. 또는 여러 개발자가 동시에 작업할 때도 사용한다. 위의 이미지는 브랜치를 이용하는 예시이다. 마스터 브랜치는 보통 배포를 하는 브랜치이고, 그 외 여러 각 역할을 하는 브랜치를 만들어 각 브랜치에서 작업하여 마스터로 합친다. branch 생성 아래 명령어로 브랜치를 생성할 수 있다. 그러나 생성된 브랜치로 이동은 되지 않고 생성만 된다. git branch [브랜치 명] 특정 branch 이동 위의 명령어로 브랜치를 생성했다면 이제 아래 명령어로 브랜치로 이동을 할 수 있다. git checko..
[git] add, commit
2021. 10. 13. 21:30
git
add git add는 파일을 stage에 올리는 것이다. add는 다양한 명령어로 할 수 있다. 파일 하나만 add하기 git add [파일 이름] 변경사항 있는 파일 모두 add하기 git add . stage한 파일 unstage하기 git reset HEAD [파일명] Commit commit은 stage된 파일들을 저장소에 올리는 것이다. 이 저장소에 저장된 커밋들의 체크섬을 가지고 커밋한 시점으로 코드를 되돌릴 수 있다. 커밋메세지를 지정한 에디터에서 작성 하기 git commit cf) 에디터 지정하기 아래 명령어를 터미널에 입력하면 기본 에디터가 vim으로 변경된다. git config --global core.editor vim 커밋 메세지에 git diff 메세지도 포함하여 에디터에서 ..
백준[14500] 테트로미노
2021. 10. 13. 21:07
Algorithm/BOJ
문제 링크 http://icpc.me/14500 풀이 ㅜ모양을 제외한 나머지 모양은 잘 관찰해보면, 어떤 점 하나를 시작으로 어떻게 가든 한번 갔던 칸으로 돌아가지 않으면서 상하좌우로 4칸을 가는 모든 경우를 나타낸다. 그렇기 때문에 백트래킹을 하며 4칸을 고르면 된다. ㅜ는 예외처리를 하여, 90도씩 돌리는 경우를 4개 고려해주면 된다. 코드 #include #include using namespace std; const int NN = 502; int arr[NN][NN], ans, n, m; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool visited[NN][NN]; void solve(int y, int x, int sum, int sz) {..
백준[20551] Sort 마스터 배지훈의 후계자
2021. 10. 11. 14:35
Algorithm/BOJ
문제 링크 http://icpc.me/2051 풀이 map을 사용해서 풀었다. 그냥 모든 쿼리에 대해 탐색을 하면 O(NM)이기 때문에 시간 초과가 발생한다. 그렇기 때문에 탐색하는 시간을 줄여야 한다. 이때 idx[쿼리] = 쿼리의 인덱스로 미리 다 저장해놓으면 탐색을 하지 않고 빠르게 인덱스를 구할 수 있다. 그러나 쿼리의 범위가 -10^9 ~ 10^9으로 매우 크기 때문에 배열을 선언할 수 없다. 그래서 map을 이용하여 값들을 모두 저장해놓으면 쿼리당 O(logN)에 처리할 수 있다. 다른 풀이로는 탐색을 할 때 이분 탐색을 이용하여 인덱스를 빠르게 구할 수도 있다. lower_bound를 이용하여 idx를 구하고 그 인덱스에 있는 값이 주어진 쿼리와 같은 수인지 체크하면 된다. 코드 #inclu..
백준[2457] 공주님의 정원
2021. 10. 8. 22:35
Algorithm/BOJ
문제 링크 http://icpc.me/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 풀이 그리디로 풀 수 있다. 현재 가지고 있는 꽃이 죽기 전에 피고, 가장 오랫동안 살아있는 꽃을 고르면 된다. 날짜는 구현의 편의를 위해 달에 100을 곱하고 일을 더했다. ex) 2월 28일 = 228 문제를 읽자마자 그리디일거같았지만 구현하는데 시간이 꽤 걸렸다. 코드 #include #include using namespace std; pair arr[100005]; int main() {..
백준[2800] 괄호 제거
2021. 10. 7. 15:52
Algorithm/BOJ
문제 링크 http://icpc.me/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 풀이 백트래킹과 스택을 이용하여 풀 수 있다. 우선 여는 괄호와 닫는 괄호의 짝을 찾아 이것을 인덱스로 가지고 있어야 한다. 이 짝을 찾기 위해서 스택을 이용한다. )를 만날 때 까지 스택에 모두 push하다가 ) 를 만날때 ( 를 만날 때까지 pop을 하고 처음 만난 (가 )의 짝이다. 위에 구해둔 괄호 쌍을 이용하여 백트래킹을 한다. 백트래킹을 해도 괄호가 최대 10개이기 때문에 ..
백준[2015] 수들의 합 4
2021. 10. 5. 16:12
Algorithm/BOJ
문제 링크 http://icpc.me/2015 풀이 누적합을 이용하여 풀 수 있다. 0~i번째까지의 합을 미리 구해놓고, 구해놓은 누적합을 잘 관찰하여 풀 수 있다. psum[i] : 0 ~ i까지의 합이라고 할 때, i ~ j까지의 합은 psum[i] - psum[j-1]이다. 이때 구간 합이 k가 되는지 확인할 수 있는 여부는, psum[i] - psum[j-1] (j < i) == k가 되는 j 값이 몇개 존재하는지 확인하면 된다. 그리고 psum[i] 자체가 k인지도 체크하면 된다. 그렇기 때문에 psum[1] ~ psum[n]까지 값을 기록해야 하는데 값의 범위가 20억으로 매우 크므로 그냥 배열을 만들 수 없어, map을 이용하여 저장한다. 코드 #include #include #include..
백준[13976] 타일 채우기 2
2021. 10. 5. 12:37
Algorithm/BOJ
문제 링크 http://icpc.me/13976 13976번: 타일 채우기 2 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 풀이 dp와 분할 정복을 이용하여 풀이할 수 있다. 분할 정복을 이용한 행렬의 빠른 거듭제곱은 곱셈을 풀면서 공부하자. dp점화식은 dp[n] = 3*dp[n-2] + sum(dp[k]) (k는 n-4부터 0까지 k-=2) 위의 식에 n-2를 대입한식과 위의 식을 빼면 dp[n] = 4 * dp[n-2] - dp[n-4]가 나온다. 행렬식으로 표현하면 위와 같이 표현할 수 있다. 이제 위의 행렬식을 분할정복을 이용하여 빠르게 계산하면 된다. 코드 #include #include using namespace st..
백준[15961] 회전초밥
2021. 10. 2. 18:36
Algorithm/BOJ
문제 링크 http://icpc.me/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 풀이 슬라이딩 윈도우로 풀 수 있다. k개의 연속된 초밥 그룹에 어떤 종류의 초밥이 몇 개 있는지 그룹을 오른쪽으로 밀면서 그룹에 수들의 종류가 몇 개 있는지 확인하면 된다. 그룹을 밀 때, 기존의 왼쪽 끝의 수가 하나 빠지고, 오른쪽에 수가 하나 들어온다. 이때, 왼쪽 수가 기존의 그룹에 유일하면 cnt--해주고, 새로운 수가 기존에 없으면 cnt++을 하면 된다. 회전..
백준[22352] 항체 인식
2021. 10. 2. 00:18
Algorithm/BOJ
문제 링크 http://icpc.me/22352 풀이 간단한 bfs/dfs문제이다. 붙어있는 같은 데이터들을 모두 탐색하면서, before와 after가 다른 세트가 2세트 이상 있다면 No를 출력하면 되는 문제다. 필자는 bfs로 구현했다. 코드 #include #include using namespace std; int before[32][32], after[32][32]; bool visited[32][32]; queue q; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i