[C/C++] Sequencing (Sequence Point)
2022. 5. 1. 19:16
C++
Sequencing / Sequence Point란? c++11부터 Sequence Point가 Sequencing으로 말이 바뀌었다고 한다. 이 글에선 sequence point란 말을 쓰겠다. 모든 연산의 결과가 완료되는 시점 쉽게 말하면, 한 시퀀스 포인트에서 다음 시퀀스 포인트로 가기 전에 이전의 모든 연산이 완료된다는 의미다. Sequence Point 1. ; (세미콜론) 2. ||, &&, ? : 와 같은 논리 연산 예를 들어, a || b에서 b가 되기 전에 a의 연산이 모두 완료된다. (a) ? (b) : 는 ?가 sequence point로 무조건 a가 먼저 완료된다. 3. , (쉼표) a = f1(), b = f2()와 같이 , 로 연결된 표현 4. 함수의 리턴 함수가 return..
[Python3] local, global 변수 규칙
2022. 5. 1. 14:25
Python3
아래 두 코드 중 하나는 에러가 발생한다. 정답을 보지 말고 생각을 해보자! 1번 코드 x = 1 def f(): y = x return y print(f()) 2번 코드 x = 1 def f(): y = x x = 2 return y print(f()) 정답은 2번 코드가 에러가 발생한다. 거의 동일한 코든데 왜 하나는 에러가 발생하고 하나는 정상 동작할까? 그 이유는 파이썬의 local, global 변수 규칙에서 찾을 수 있다. 파이썬에서는 함수 전체를 보고 global 변수인지 local 변수인지 결정을 한다. 함수 전체에서 reference만 일어난다면 이는 암묵적으로 global이라 판단한다. 그러나 assign이 한 번이라도 일어난다면 이는 local 변수로 판단을 한다. 위의 1번 코드에선..
못생긴 vscode 터미널 색을 바꿔보자
2022. 5. 1. 00:56
환경 세팅
테마가 다 마음에 드는데 터미널 색만 맘에 안들 때 이 방법을 써보자. 1. vscode setting창 연다 2. 중간쯤에 보이는 Color Customizations 누른다 3. 여기서 맘에 드는 폰트 컬러 복사 4. 복붙 에디터 부분 색이랑 맞추고 싶으면 background 부분만 지우면 폰트 색깔만 바뀐다.
[C/C++] printf에 float만을 위한 변환 명세가 없는 이유
2022. 4. 28. 01:41
C++
printf("%f", 1.0f)와 같이 printf에 float형을 넘겨줘도 절대 printf 함수에 float형을 넘겨줄 수 없다는 재밌는 사실을 알게 됐다. double lf = 1.0; printf("%lf\n", lf); // double lf 사용 printf("%f\n", lf); // double에 f도 가능 위와 같이 double을 출력할 땐 %lf와 %f 둘 다 사용할 수 있는데 이건 C99에 생긴 기능으로 scanf에서 double형을 %lf로 받기 때문에 편의성?을 위해 생긴 기능이라고 한다. 종종 float은 %f, double은 %lf로 출력해야 한다는 사람들이 있는데 이건 완전한 오개념이다. 아래 사진을 봐도 f는 명확히 double을 위한 변환 명세다. 그런데 float형을 ..
[백준] 3878 점 분리
2022. 4. 27. 22:29
Algorithm/BOJ
문제 링크 http://icpc.me/3878 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 풀이 두 컨벡스 헐이 서로 만나지 않게 하면 된다. 검정 컨벡스헐을 구성하는 점을 A, 흰색 컨벡스 헐을 B라 하자. 두 컨벡스 헐이 만나지 않기 위해선 A의 점들 중 어떤 점도 B 내부에 있으면 안 된다. 또한 B의 점들도 A에 있으면 안 된다. 또한 두 컨벡스 헐을 이루는 모든 직선들끼리 서로 만나면 안 된다. 코드 #include using namespace std; using ll = long long; #de..
원티드 쇼미더코드 후기
2022. 4. 15. 22:06
후기
대회라고 했지만 코테 느낌이었고, 가볍게 풀었는데 금뱃지 받았다. 문제 설명은 저작권이 어떻게 걸린지 몰라서 하지 않겠다.
Docker로 M1맥에서 Ubuntu 돌리기
2022. 4. 15. 21:23
환경 세팅
M1에서 Ubuntu 돌리려면 무조건 서버 or 패럴럴즈만 알고 있었는데 최근에 Ubuntu를 사용해야 해서 알아보던 중 도커라는 걸 알게 됐다. 도커 컨테이너는 격리된 공간에서 프로세스가 동작하는 기술이다. 도커에는 우분투뿐만 아니라 다양한 종류의 컨테이너를 올릴 수 있다. 또한 M1 맥이 아니라 다른 운영체제에서도 아래와 같은 방법으로 사용할 수 있는 것으로 알고 있다. 자세한 도커에 대한 지식은 여기를 참고하자. 우선 아래 링크에서 Docker desktop을 설치한다. https://www.docker.com/products/docker-desktop/ Docker Desktop - Docker DockerCon 2022 Don’t miss it – register now for May 10th..
[백준] 1377 버블 소트
2022. 4. 12. 21:11
Algorithm/BOJ
문제 링크 http://icpc.me/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 개인적으로 알고 나면 쉽지만 아이디어가 많이 어려운 문제인 것 같다. 문제를 잘 관찰을 해본다면 출력을 하는 수는 정렬이 끝난 다음 시점의 i값이다. 편의상 인덱스가 작은 방향을 왼쪽, 큰 방향을 오른쪽이라 하겠다. 정렬이 모두 끝난 시점을 알기 위해서는 왼쪽으로 밀려난 수 중 가장 많이 밀려난 수가 몇 번 왼쪽으로 밀려났는지를 알면 된다. 그 이유는 왼쪽으로 가야 하는 어떤 수는 한번 ..
2022 구글 코드잼 Qualification Round 후기
2022. 4. 3. 23:42
후기
4솔을 하고 71점을 먹었다. A번만 풀고 과제하다가 자고 일어나면 시간이 끝날 거 같아서 3시까지 풀다 잤다.. 피곤해 죽을 뻔.. 30점만 먹고 자려했는데 4번 풀이가 보여서 이것만 풀고 자야지하다가 맞왜틀 박으면서 늦게까지 풀었다. 마지막 문제는 쓰윽 보고 문제가 이상하길래 그냥 안 풀고 맘 편히 잤다. A. Punched Cards 이쁘게 출력만 하면 되는 간단한 구현문제다. #include using namespace std; char arr[100][100]; void f1(int r, int c) { char cc[2] = {'+', '-'}; for (int i = 0; i < 2 * c + 1; i++) arr[r][i] = cc[i % 2]; } void f2(int r, int c) ..
[백준] 2449 전구
2022. 4. 1. 02:21
Algorithm/BOJ
문제 링크 http://icpc.me/2449 2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 풀이 오랜만에 되게 재밌게 푼 dp문제다. 3차원 dp로 풀었는데 다른 사람 코드 구경하면서 2차원 dp로 내 풀이보다 훨씬 쉽게 풀 수 있는 걸 발견했다. 이 글에선 3차원 풀이를 작성하겠다. 시간 복잡도는 O(N^3 * K)에 해결할 수 있다. dp[l][r][i] : 구간 [l, r]을 i로 만들었을 때 최소 경우의 수 a[i] : a번째 전구의 색 위와 같이 정의를 하면 세 가지 케이스로 점화식을 세..
[백준] 7620 편집 거리
2022. 3. 24. 18:11
Algorithm/BOJ
문제 링크 http://icpc.me/7620 7620번: 편집 거리 가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는데 사용한 글자를 출력한다. (출력할 글자 www.acmicpc.net 풀이 dp 역추적을 하는 문제다. 하지만 메모리를 특이하게 관리해야 하는 처음 보는 문제다. 역추적을 하기 위해서 dp테이블을 모두 가지고 있기엔 테이블의 크기가 17000 * 17000 * 4byte로 너무 크다. 그렇기 때문에 역추적을 위한 테이블을 17000 * 17000 * 2bit로 만들어 메모리를 최적화시켜야 한다. 역추적 테이블은 unsigned char 한 칸에 비트 연산을 이용하여 정보를 4개..
구글 푸바 챌린지 후기
2022. 3. 16. 21:00
후기
구글엔 되게 재밌는 이스터 에그인 푸바 챌린지라는 게 있다. 구글에서 다양한 개발자를 채용하기 위해 만들어놨다고 한다. 개발자스러운 검색을 하다 보면 뜬다고 하는데 이런 게 나한테 떠버렸다. 어쩌다 알고리즘에 걸려버렸나 보다. 마지막으로 검색한 게 "python list comprehension"이었던 걸로 기억한다. 이게 뭔지 몰라서 뜨는 창은 캡처를 못했지만 개발자라면 흥미롭게 생각할만한 문구로 확인 버튼을 누르라고 꼬신다ㅋㅎ 버튼을 누르면 아래 같은 창이 뜬다. 여기서 이것저것 누르다 보면 help를 쳐보라는 말이 나오고 문제를 풀 수 있게 해 준다. 문제는 파이썬과 자바로만 풀 수 있다. 레벨별로 문제가 있는데 점점 레벨별로 난이도 차가 꽤 크다. 문제당 시간을 부족하지 않게 줘서 시간제한 상관..
[백준] 1368 물대기
2022. 3. 16. 14:23
Algorithm/BOJ
문제 링크 http://icpc.me/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 MST를 이용하여 풀 수 있다. 가상의 루트 노드를 하나 만들고, 어떤 물을 킬 때, 루트 노드에서 물을 끌어온다고 생각하면 쉽게 풀 수 있다. 물은 키는 행위는 루트 노드와 킬 노드를 연결시키는 것으로 매핑시키면 된다. 코드 #include using namespace std; struct T { int x, y, z; }; vector arr; int mat[302][302];..
[백준] 1126 같은 탑
2022. 2. 26. 16:39
Algorithm/BOJ
문제 링크 http://icpc.me/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 풀이 dp문제다. dp인 것을 못 알아차리고 고민하다가 알고리즘 분류를 봤다. 처음 생각했던 점화식은 dp[i][a_size][b_size] : i번째 까지 봤을 때 a기둥의 사이즈와 b기둥의 사이즈로 dp를 정의하는 것이었다. 그러나 이 풀이는 52 * 5e5 * 5e5로 시간초과가 발생할 것이다. 그래서 a기둥과 b기둥의 높이를 더 컴팩트하게 정의할 수 있는 방법을 생각했다. 결론은 더 큰 기둥의..
[백준] 2662 기업투자
2022. 2. 23. 16:20
Algorithm/BOJ
문제 링크 http://icpc.me/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 풀이 배낭 문제라고도 불리는 웰노운인 knapsack문제다. dp를 이용하여 풀 수 있다. dp[i][j] = max(dp[i - 1][j - k] + arr[k][i]) (0