관찰과 질문, 그리고 데이터

200101 책 제목은 ‘자료구조와 알고리즘’이지만, 다루는 내용은 ‘파이썬으로 배우는 컴퓨터공학 기초’에 가깝다. 책 제목은 ‘자료구조와 알고리즘’이지만, 다루는 내용은 ‘파이썬으로 배우는 컴퓨터공학 기초’에 가깝다. Python의 기본 자료구조, collection 자료구조뿐만 아니라 모듈, 데코레이터, 멀티프로세싱에 유닛 테스트까지 다양한 범위를 커버한다. Python 자체에는 익숙하지만 프로그래밍 언어로써는 아직 생소한 사람들에게 적합한 책. 다만 설명은 상세하지 못하다. 개인적으로, 파이썬이 개발자나 컴퓨터공학 전공자 수준을 넘어 대중화된 계기는 프로그래밍 언어로써의 효용성과 가치가 재발견되었기 때문이 아니라, 빅데이터 유행에 R과 함께 데이터분석 도구로 각광받다가 파이썬의 딥러닝 프레임워크가 ..

https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 | 프로그래머스 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준 programmers.co.kr 풀이를 찾아보면 다들 전형적인 DP문제라고 하는데, 나한테는 왜 이렇게 어..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 삼성SW역량테스트 기출문제로, DP를 사용해 풀 수 있는 문제. table[i] = i번째 날에 얻을 수 있는 최대 보수라고 정의하면 table[i]의 초기값은 '해당 날짜에 일할 수 있을 때 기본값' 이 된다. 해당 날짜에 일할 수 없으면 0으로 정의한다. 점화식은 table[i] = max(table[i-1] + i번째 날에 일했을 때 얻는 보수, table[i]) 형태가 된다.

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 www.acmicpc.net 이분탐색 + BFS 활용문제. start지점과 end지점이 이미 정해져 있으므로, BFS에서는 'start -> end'로 이동하는 모든 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net DP 점화식을 세워서 해결할 수 있는 문제. 각 집마다 R, G, B 색깔로 칠할 때의 비용이 주어지므로, idx 0 = R, 1 = G, 2 = B로 정의하면 0

19.12.06 면접본 뒤 19.12.11일에 복기하며 쓰는 글. 4학년 1학기 마치고 휴학계 낸 다음, 부족한 컴퓨터공학 지식도 익힐 겸 입사지원서 낼 수 있는 회사들 체험해볼 겸... 9월부터 11월까지 몇몇 회사에는 공채를, 몇몇 회사에는 인턴지원서를 넣었다. 물론 모조리 서류탈당했다. 그러다 롯데e커머스 Programming 분야에서 서류통과를 했으니 면접 보라고 연락이 왔다. 그마저도 구글 지메일이 lotte.com 메일을 스팸함에 분류해놓는 바람에 면접날짜를 면접 전날에야 알게 되었다. 19년 하반기 동계인턴에는 L-tab 전형이 온라인으로 대체되어 있었다. 일반적으로 신입공채에서 보는 인적성검사 시험 대신, 온라인으로 보는 인성검사만 정해진 기간 안에 실시하면 된다. 어렵다 쉽다 할 거 없이..

https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr DP를 사용해 풀 수 있는 문제. board의 y좌표, x좌표를 기준으로 볼 때 board[y-1][x-1], board[y][x-1], board[y-1][x] 세 개의 좌표값이 전부 1이라면 board[y][x]는 세 개의 정사각형이 왼쪽, 위쪽, 왼쪽 대각선에 포진해 있게 된다. 따라서 이 경우 결과적으로 정사각형 4개가 붙어 있는 모양이 되므로 변의 길이가 2인 정사각형이 된다. 따라서 DP 점화식을 board[y][x] = ma..

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 | 프로그래머스 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모 programmers.co.kr 사람 한 명당 보트를 한 번 사용하는 경우가 보트를 최대한으로 사용한 경우..

https://www.acmicpc.net/problem/2655 2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 문제는 문제에 맞는 점화식 설계를 못하면 정말 풀기 힘들다... 처음엔 문제 조건에 맞게 백트래킹 형태로 풀어봤지만 시간 초과가 나왔다. DP로 문제를 풀어내려면 1. 무게 또는 면접 중심으로 벽돌을 정렬한다. 2. table[i] ..

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 내가 Python을 써서 그런 건지, 애초에 메모리 제한이 128로 작아서 그런 건지는 모르겠지만 DP가 아니면 문제 자체를 풀 수가 없었다. 문제의 논리 그대로 bfs를 적용하면 메모리 초과가 발생하고, 그나마 DP를 쓸 때조차도 반복문 잘못 세워서 메모리 초과를 숱하게 띄웠던 문제. 고수분들의 고견을 구하고 싶습니다. Python의 작업이 어떻기에 위의 두..