'분류 전체보기' 카테고리의 글 목록 (2 Page)

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

[백준] 2481 해밍 경로

2022. 2. 17. 15:50 Algorithm/BOJ

문제 링크 http://icpc.me/2481 2481번: 해밍 경로 길이가 같은 두 개의 이진수 코드 w1과 w2가 있다고 하자. 이 두 코드 사이의 해밍 거리(Hamming distance)는 w1과 w2의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 www.acmicpc.net 풀이 해밍 거리가 1인 경우는 비트 하나만 다른 것을 의미하기 때문에 비트가 하나만 다른 것들을 모두 그래프로 만든 후에 bfs를 돌리면 된다. 비트 하나만 바꿀 때는 XOR연산을 하면 된다. 그래프를 만들 때는 N개의 수에 k번 비트 연산을 하고 그 수가 존재하는지 map으로 확인하면 O(NKlogN)에 만들 수 있다. cf) 입력을 int형으로 받아서 2시간 가까이 뇌절을 했다. 30자리..

[백준] 1533 길의 개수

2022. 2. 3. 15:26 Algorithm/BOJ

문제 링크 http://icpc.me/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 풀이 본대 산책 2과 비슷한데 가중치가 있는 문제다. 가중치가 5 이하이기 때문에 정점을 늘려서 풀 수 있다. 정정 하나를 v0 v1 v2 v3 v4로 나누고 각 정점별 가중치를 1로 둔다. 이때 만약 u -> v의 가중치가 3이라면 u0 -> v2 -> v1 -> v0과 같은 방식으로 u -> v의 간선을 연결할 수 있다. 이렇게 그래프를 약간 변경하여 행렬제곱을 T제곱을 하면 O((5..

[백준] 12850 본대 산책 2

2022. 1. 27. 20:28 Algorithm/BOJ

문제 링크 http://icpc.me/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 유배당한 불쌍한 정보대생을 위한 문제다.. 분할 정복을 이용한 O(logN) 행렬 제곱을 이용하여 풀었다. 이 글을 참고하여 풀었다. 행렬 곱셈식을 곱씹어본다면 왜 이렇게 풀이할 수 있는지 알 수 있다. Counting source to destination path of k length HERE author discusses three methods to count source to destination path of k length. I am not able to get the last method which is base..

[백준] 13977 이항 계수와 쿼리

2022. 1. 25. 22:00 Algorithm/BOJ

문제 링크 http://icpc.me/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 모듈러 역원에 대해 알아야 하는 문제다. 모듈러 역원에 대한 내용은 여기를 참고하자. n!을 전처리하여 미리 구해두고, 각 쿼리마다 n! * ((n-r)! * r!)^(mod-2)을 구하면 된다. 이때 제곱은 분할정복을 이용하여 계산한다. 코드 #include using namespace std; using ll = long long; const ll mod = 1e9 + 7; const int N = 4e6 + 6..

티스토리툴바