코딩개발로 물장구치는 개발자

안녕하세요 Dibrary입니다. 알고리즘을 풀다보면 꼭 마주하는 문제들이 몇 개 있습니다. 소수, 최소공배수, 최대공약수 등등... 중고등학교때는 그저 술술 풀었지만, 코딩으로 하자니 막상 숨이 턱. 막히는 그런 개념들이죠. 그 중에 이번에는 '소수'를 구하는 코드를 정리해보겠습니다. 대표적인 문제로는 아래 문제가 있습니다. 대놓고 소수 구하기 라고 하죠 . 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 우선, 소수란 '자기 자신과 1만을 약수로 갖는 수' 입니다. 예를 들어보죠, 2는 1과 2만을 약수로 가집니다. 소수죠. 3도 1과 3..

안녕하세요 Dibrary 입니다. 이번에는 과거에 풀지 못했던 문제를 다시 도전했는데, 생각외로? 쉽게 풀려서 당황했는데, 왜 그런 느낌을 받았는지를 정리해보고자 합니다. 문제는 '최소 직사각형'이라는 문제인데, 처음에 맞이했을 때의 그 느낌을 아직도 잊을 수 없습니다. (알고리즘을 아예 풀지 못하면서 BOJ에서 A+B 이런거만 건드릴 때 였죠...) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 지금에 와서야 이 문제가 '그리디'고, 문제에 '숨은' 조건을 찾는 것이 중요하다는 것을 알지만, 처음에는 아예 몰랐습니다. 처음에 이 문제를 맞닥뜨리고 느낀 ..

안녕하세요 Dibrary입니다. 이번엔 간단한 JOIN문제인데, 어문데서 시간을 꽤나 허비했던 문제를 정리해보겠습니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 JOIN 카테고리에 있는 문제라서 JOIN을 써야 하는 것을 알 수도 있지만, 문제의 내용을 보고도 JOIN을 써야 함을 알 수 있습니다. 이 문제를 보고 제일 먼저 든 생각은, 한쪽엔 있고, 한 쪽엔 없는 것을 '구분' 해야 하고 그 중에 없는 것을 뽑아다가 보여줘야 한다. 입니다. 저는 먼저 문제를 파악해보는데 중점을 뒀었습니다. 예를 들면, 데이터가 몇 개고, 같은 데이터는 ..

안녕하세요 Dibrary입니다. 이번에는 이진탐색을 사용해서 풀어야 하는 문제를 정리해보겠습니다. 처음에 나름 알머리 굴리다가 시간초과로 실패를 겪은 문제입니다. 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제를 처음 보자마자 떠오른 생각은 아래와 같습니다. M만큼만 자르면 된다. (이걸 반복문에서 캐치해야 할 것 같다.) M만큼 자르는 M-1 포인터를 for문으로 돌리면 어떨까. 근데 2번에서 생각해보니 거의 100000! 번에 가까운 연산이 이뤄질 수도 있다는 생각이 들어서 위 방법은 곧바로 포기 했습니다...

안녕하세요 Dibrary입니다. 이번에는 제가 BFS/DFS에 아주 약간? 자신감이 생겨서 도전했다가 몇 시간을 .. 날려버린 문제를 정리해보겠습니다. 알고보니 BFS/DFS같은 그래프 풀이방법 만 쓰는 게 아니라, 여기에 모든 경우의 수 까지 같이 확인해야 하는 문제였어서 처음 접한 저는 매우 어려웠었습니다. 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 처음에 문제를 보고 곧바로 "BFS를 쓰믄 되겠다! " 라는 생각이 제일 먼저 떠올랐습니다. 왜냐하면, 문제에서 "바이러스는 퍼져나갈 수 있다" 라고 나왔기 때문이죠...

안녕하세요 Dibrary입니다. 이번에는 굉장히 유명한 '회의실 배정'문제를 정리해보겠습니다. 사실, 이 문제는 여러 알고리즘 책에 소개가 되었으나 막상 안보고 하려니 잠시 헷갈린 문제입니다. 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 먼저 예제 입력에 대해서 확인을 해보겠습니다. 총 11개의 가능한 시간이 주어지는데, 이를 엑셀로 표현해보면, 이렇게 나옵니다. 이 중에 예제 출력의 결과인 4가 나오게 하려면, 이렇게 골라야 합니다. 근데, 이때 제가 의문이 들었던 내용은, 첫 번째로 택해진 1, 4에 해당되는 시간 구간은 맨 처음에 시작하는 것도 아니고, 그렇다고 길이가 가장 긴 것도 아니고, 아무것도 아닌데, 그럼 ..

안녕하세요 Dibrary입니다. 이번 문제는 '스택'을 활용한 문제입니다. 스택을 배우긴 했는데, 어떻게 써야할 지 모르는 사람이었다면 이 문제를 풀지 못했을 겁니다. (저처럼요...) 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 먼저 예시로 나온 문제를 보면 10, 3, 7, 4, 12, 2 에서, 10을 기준으로는 3개, 7은 1개, 12는 1개 총 5개를 볼 수 있죠. 그래서 전 처음에 이런 방식으로 도전했었습니다. 모든 타워 정보를 넣은 후에, for문을 2겹으로 돌면서 기준 타워보다 그 다..

안녕하세요 Dibrary입니다. 파이썬으로 설명된 자료구조 책을 보면 여느 다른 책들과 같이 '리스트, 트리, 정렬, 탐색, 그래프' 등이 나와있습니다. 근데 파이썬을 자주 써 본 사람이라면 이런 의문이 들죠. 파이썬에서는 어차피 리스트 자료형이 있는데.... 물론, 저도 그런 생각을 한 적이 있습니다. (그리고 그 리스트 자료형은 여기서 말한 연결리스트도 아니죠;;) 그런 혼란을 가지고 있지만 불편함은 없어서 그냥 유야무야 넘어가다가, 자료형 리스트가 아닌 자료구조 '단순 연결리스트, 이중 연결리스트, 원형 연결리스트' 등을 배워야 하는 이유를 최근에 알고리즘을 풀다가 깨달았습니다. 1. 불필요한 공간 낭비를 위해서 사용할 수 있다. 애초에 리스트를 배열 대신에 쓰는 이유는 공간 사용의 효율을 높이기 ..

안녕하세요 Dibrary입니다. 이번에는 그래프 탐색 + 약간의 생각을 사용해야 풀 수 있는 문제 입니다. (참고로 저는 생각을 하지 못해서 어려웠었죠;;) 이 문제를 보자마자 떠오른 생각은 아 확산이 되네? BFS또는 DFS로 퍼뜨려 나갈 수 있겠다. 근데 시작점이 한 개가 아니네....? 헐 생각 1번을 구현하기는 어렵지 않습니다. 문제는 '시작점'이 여러 개 인 것을 해 본 적이 없다는 것이었죠. 이 문제를 풀 때 생각해볼 2가지 아이디어가 있습니다. 먼저 잘 생각해 보면 시작점이 여러 개인 것은 그다지 중요하지 않습니다. BFS를 사용한다고 할 때, 우리는 해당 '위치'에 대해서 뭘 고려할까요? '방문 했느냐' / '방문 안했느냐' 입니다. 즉, 시작점이 여러 개라 한들 방문해버리면 어차피 거긴 ..

안녕하세요 Dibrary입니다. 알고리즘 문제를 풀다 풀지 못하겠다 싶은 문제를 마주한 경우가 꽤 있으실 겁니다. 예를 들면 백준에서 내 등급이 '실버'지만, 실버 문제를 풀지 못하는 경우 이런 경우 많죠. 근데, 그러면 대부분 1~2시간 가량 고민해 본 뒤에 다른 사람의 해답을 봐라. 라고 합니다. 근데, 거기서 끝내면 자기 공부가 안 됩니다. 제가 어려운 문제를 마주한 경우 어떤 방법으로 해 나가는지 정리해보겠습니다. 뭐 꼭 이렇게 해야 한다는 것은 아니지만, 확실한 것은 '저'에게 효과가 있었던 방법입니다. 1. 문제를 보고 떠오르는 생각을 정리해 둔다. 말 그대로 해당 문제는 어떤 방식으로 풀어야 할거 같다. 어떤 제약이 있는 것 같다. 그냥 단순히 접근하면 어떤 어려움에 봉착할 거 같다. 등 떠..