[백준] 400문제 달성! (PLATINUM IV)

[BOJ / 메모이제이션 BFS] 14867 물통

https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 14867 물통 알고리즘 : 메모이제이션을 활용한 BFS 얼핏보면 간단 dp같지만, 두 물통의 총량이 100,000으로 두 값을 dp배열의 크기로 사용하면 메모리초과가 납니다. 하지만 나오는 물의 경우의 수는 한정적이므로 이를 map으로 dp를 한다면 시간이 오래 걸리지만 (visited 체크시 log N) 시간내에 결과값을 얻어낼 수 있습니다. ma..

[BOJ / 비트마스크 DP] 1102 발전소

www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 1102 발전소 알고리즘 : 비트마스크 DP / BFS 비트마스크를 DP배열의 iterator로 사용하는 문제입니다. dp를 이용해 현재 적용중인 상태에서 이미 들린 상태이거나 이미 결과값을 초과한 경우 가지치기를 하면 됩니다. 문제에서 해결이 안되는 경우에는 -1을 출력하라고 했으나, 모든 발전소는 다른 모든 발전소를 킬 수 있으므로 즉, 키는 비용에 음수값이 주어지는 경우가 없으므로 -1을 출력하는 경우는 모든 발전소가..

[BOJ / 라인스위핑] 9318 위성사진

https://www.acmicpc.net/problem/9318 9318번: 위성 사진 문제 상근이는 위성 사진 여러장을 이용해서 지도를 만들고 있다. 위성에는 카메라가 달려있고, 카메라는 한 영역을 찍는다. 이러한 위성 사진 여러 장을 합치면, 큰 사진을 만들 수 있다. 위성 � www.acmicpc.net 9318 위성사진 알고리즘 : 세그먼트/인덱스 트리 + 라인스위핑 요즘 풀이하고 있는 라인스위핑 기초 문제입니다. 인덱스 트리 짜는 법이 헷갈려서 세그먼트 트리와 섞어서 짰습니다. 라인스위핑을 이용하여 수평선을 기점으로 구간트리를 구성하고 업데이트하여 넓이를 알아내는 방식입니다. CHECK POINT 총 나올 수 있는 구간의 수는 MAX_N * 2개(모든 사각형의 변의 높이가 같지 않을 때)이므로..

[BOJ / 비트마스크 DFS] 17136 색종이 붙이기

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐 www.acmicpc.net 17136 색종이 붙이기 알고리즘 : 비트마스크 DFS 삼성 A형 기출문제입니다. 문제 풀이 방법은 1767 프로세서 연결하기와 매우 유사합니다. ht..

[BOJ / 삼성A형기출] 16234 인구 이동

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 16234 인구이동 알고리즘 : BFS, 시뮬레이션 floodfill 방식의 문제로 시뮬레이션 느낌이 나는 bfs 문제입니다. 중복 ..

#2 [2018-2020.01] 대학 회고록

1. 대학 입학 2017년에 수시지원을 하여 국민대 소프트웨어공학과, 숭실대 컴퓨터공학과, 인하대 컴퓨터공학과에 최초합하여 최종적으로 인하대에 진학하였습니다! 2. 인하대학교 컴퓨터공학과 학생회 CSESC 인하대학교 컴퓨터공학과 학생회 홍보편집부에 들어가 많은 과 행사에 대한 회의와 홍보, 일일호프와 같은 과 행사에 참여했습니다. 처음에는 학생회라고 하여 일도 많고 바쁠 줄 알았지만, 생각보다 여유롭고 재밌는 행사가 많았습니다. 3. 과 수석 운이 따랐는지 첫 학기 학점이 4.5가 아님에도 과 수석이 되어 다음 학기에 전액 장학금을 받았습니다. 처음 받아보는 장학금이라 좋았습니다. 4. Challenge The Programming CTP 2학기에는 알고리즘 소모임에 들어가 선배분들께 고급 알고리즘을 배..