이름 못 정한 블로그

월요일, 화요일 이틀 동안은 DFS와 BFS에 대해서 공부하게 된다. 내가 다른 문제 풀이 방법들에 비해 자신 있는 파트라서 보통 처음 문제를 보면 DFS를 사용할 수 있는지 확인하곤 했다. 그래서 이번엔 올라온 문제가 많긴 하지만 금방 풀 줄 알았다. 그런데 기초 DFS 문제를 푸는데 전혀 쉽게 풀리지 않았다. 문제가 직관적이지 못해서 이해하는데도 시간이 많이 들기는 했지만 이해한 이후에도 뭔가 잘 안 풀렸다. 결국 재귀 함수를 호출하기 전에 함수를 하나 더 호출하는 것으로 문제를 해결했다. 거의 두 시간 정도 걸린 것 같다. 마지막으로 푼 문제도 잘 안 풀렸다. 얘는 BFS 문제였는데 큐에 집어넣는 조건을 잘못 설정해서 계속 오류가 나는거였다. 결국 다 해결하기는 했지만 꽤나 애먹었다. 7일차도 그래..

2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한..

연구실 인턴을 하면서 터미널 만질 일이 되게 많다. SmartSSD가 금방 뜨거워지기 때문에 터미널로 온도 체크를 하고 있어야 하고 Vitis platform을 실행하려면 또 터미널을 켜서 몇가지 명령어를 넣어줘야 한다. 쉘 스크립트에 대해서 전혀 모르고 있어서 매번 이렇게 직접 쳐야하나 싶었는데 사수분이 사용하시는걸 보고 나도 필요한만큼만 공부해서 사용 중이다. 1. test.sh 파일을 생성한다. 2. 생성한 파일의 내용을 다음과 같이 작성한다. #!/bin/sh 3. 원하는 내용을 추가로 더 작성한다. 4. 파일의 권한을 부여해준다. $ chmod 755 test.sh 5. 실행은 다음 3개 중에 하나를 입력하면 된다. $ ./test.sh $ bash test.sh $ sh test.sh 더 잘 ..

1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘..

1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 문제 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...) 세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 세..

5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRB..

오늘 내용은 분할 정복에 관한 내용이었다. 강의는 분할 정복을 배우게 되면 거의 무조건 배우는 merge sort, quick sort, binary search에 관해 진행했다. 셋 다 처음 듣는 내용은 아니라 강의는 무난하게 들을 수 있었다. 근데 오늘 올려준 문제들은 쉽지 않았다. 이게 왜 분할 정복 인지도 모르겠다. 내가 다른 방법으로 풀려고 하려고 해서 그런가 도저히 어떻게 쪼개서 풀어야 하는지 감도 안 잡혔다. 총 5개의 문제가 올라왔는데, 일단 3개의 문제만 풀었다. 나머지 두 개는 더 어려운 문제 같다. 내일은 주말이니 내일 풀어봐야지. 근데 3문제 다 순탄치 못하게 풀었다. 알고리즘 문제 유형 중에서 DP를 제일 못하는 줄 알았는데 분할 정복이 복병인가...? 문제를 좀 더 많이 풀어봐야..

13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net 문제 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 2^25 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 이상 500만 이하이다. 입력 첫째 줄에 A1, A2, ..., AN이 주어진다. 12 1 449 12 555 12..

오늘은 내가 제일 싫어하는 유형인 DP에 대한 내용이었다. 나는 다른 유형에 비해서 유독 DP가 어려워한다. 구현 문제 같은 건 자질구레한 예외를 하나씩 처리해가는 게 짜증은 나도 맛은 있는데 반해서 DP는 아이디어를 떠올리지 못하면 손도 못 대겠다. 이름도 억지로 Dynamic Programming이라고 지은 것 너무 싫다. 처음에 들었을 때 도대체 이게 뭐지 싶은 이름이었다. 그래도 편식할 수는 없으니 공부는 해야지... 오늘 내용은 이미 학기 중에 들은 내용과 거의 비슷했지만 DP를 조금 스마트하게 처리하는 Brute-Force 방법으로도 생각할 수도 있다는 것을 듣고 신기했다. 사실 지금까지 DP를 BF랑 엮어서 생각해본 적이 없었다. 그런데 조금 생각해보니 맞는 말 같았다. 여러 알고리즘 기법이..

얼마 전부터 삼성 대학생 S/W 알고리즘 특강을 듣게 됐다. 저번에 사전 문제를 풀었을 때는 당연히 떨어졌을 줄 알았는데 의외로 선발 메일이 왔다. 첫날 포스팅하는 것을 놓쳐서 3일째에 이제야 올린다...ㅋㅋ [BOJ] 1062 가르침 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단 uyt8989.tistory.com 첫날 느낀 점을 여기에다가 썼었는데 따로 포스팅하는게 좋지 않을까 해서 카테고리를 새로 팠다. 이번 주부터 연구실도 매일 출근하고 이것도 매일 들어야 한다. 저번 주까지만 해도 별로 안 바빴는데 급발진을 해버렸다. 동기 애들이랑 ..