본문 바로가기
반응형

블로그 글161

[ 백준 ] 10451 번 순열 사이클 파이썬python 풀이 // 문제 요약 1부터 N 까지 정수로 만들 수 있는 순열의 한 가지 경우가 주어질 경우 1부터 N 까지 오름차순으로 정렬한 순열과 1대 1 대응 하여 만들 수 있는 그래프에서 순환 구조는 몇개가 생기는지 리턴하는 함수를 만들어라. //사고 문제를 이해하는게 어려운 문제다. 문제의 참고자료를 보면 그림이 아주 잘 나와있는데 이런 행렬이 주어지면 첫번째 행이 from 두번째 행이 to 가 되는 그래프를 그릴 수 있다. 그려본다면 이런식이다. 모두 같은 숫자로 이루어진 순열이므로 뻗어나가고 끝나는 가지는 존재하지 않게 되고 순환구조가 발생하게 된다. 파이썬에서는 dfs를 이용하면 순환구조를 간단하게 찾을 수 있는 테크닉이 존재하는데 바로 파이썬의 set() 를 이용한 진행경로 추적이다. dfs의 경우 깊이를.. 2021. 7. 29.
[ 프로그래머스 ] LV.2 짝지어 제거하기 // 문제요약 문자열 s 가 주어지면 짝이 맞는 문자 한 쌍을 제거하고 앞뒤로 남은 문자들을 다시 붙이는 작업을 반복할때 모든 문자를 없앨 수 있다면 1 그렇지 않다면 0을 반환하는 함수를 완성해라. // 사고 특정한 페턴을 추출/제거하는 방식중에서 stack의 선입후출 LIFO의 특성을 이용하는 전형적인 문제다. 보여지는 대로... 선입선출은 먼저 들어간 것이 먼저 나오는 것이고 선입후출은 먼저 들어간 것이 나중에 나오는 것이다. 편의점 알바를 해보면 저 둘의 차이를 확실히 알것이다. 사장님은 선입선출로 정리하라고 하고 손님들은 선입후출로 사가려고 한다... 아무튼 문제를 많이 풀어보면 어느 순간 자동으로 스택이라는 것을 직감하게 되는 전형적인 문제다. 페턴을 외워두는 것도 나쁘지 않다. // 풀이 원.. 2021. 7. 22.
[ Pandas ] 데이터 분석을 통한 Titanic 생존자 예측 - 2 // 각 열에 따른 생존 확률 Survived는 살았을 경우 1, 죽었을 경우 0으로 표시된다. 이 점을 잘 생각하면 어떤 조건 하에서 전체 데이터의 mean 값을 구하면 전체 데이터의 수로 생존자의 수를 나눈 값이 된다. 이 값은 단순히 mean 값이 아니고 생존율이 된다. 이 과정에서 원문 작성자가 중요하게 보는 부분은 바로 "확률이 서로 유의미하게 다른 분류"를 찾아내는 작업이었다. 그러니까 정말 이 카테고리의 값이 더 높거나 더 낮으면 생존확률이 더 높아지던지 낮아지던지 하는가 하는 것이다. 유의미한 correlation을 본 것이라고 생각할 수도 있는데 사실 나도 여기서는 좀 의아했던 것이 단순히 correlation을 본 것이 아니라 구분 가능한 기준으로 확률이 분배되는지를 확인하는 작업이라고.. 2021. 7. 19.
[ Pandas ] 데이터 분석을 통한 Titanic 생존자 예측 - 1 // 타이타닉? 타이타닉은 이제 잘 모르는 세대가 생겼을 것같은데 일단은 엄청 큰 여객선의 이름이다. 이 배는 당시의 하이테크놀러지를 모두 적용하여 '절대 침몰하지 않는 배'라는 믿음이 있었다. 물론 당연히 침몰했다. 그러니까 생존자 데이터를 분석하는 거고... 아무튼 영화로도 나올 만큼 엄청난 규모의 세계적인 이슈였고 무엇보다 큰 인명피해를 동반한 끔찍한 사고였다. 이 배가 출항할때 탑승자들의 이름과 신상등을 적어둔 기록이 있는데 배가 큰 만큼 이 기록이 분석 가능할 정도의 규모가 되고 사회의 각 계층이 탑승하면서 다양한 데이터가 만들어졌다. 그래서 우리는 이 배에 탑승한 사람들의 데이터들이 가지는 연관성으로부터 이 사람이 살았는 지 죽었는지 분석할 수 있어 데이터 분석의 입문으로 굉장히 많이 사용되고.. 2021. 7. 14.
[ 프로그래머스 ] LV.2 가장 큰 정사각형 찾기 // 문제 요약 0과 1이 채워진 2차원의 행렬이 주어지면 1로 만들 수 있는 정사각형중에 가장 큰 정사각형의 넓이를 구하여라 // 사고 기본적으로 생각할 수 있는 풀이는 DFS나 BFS다 그러나 효율성 문제를 보는 점이나 LV.2 인 것을 감안하면 DFS / BFS 가 아닐 가능성을 생각해야한다. 이 문제의 풀이는 greedy로 푸는 것이다. 정사각형을 구성하는 가장 작은 단위는 2x2 정사각형이다. 이 단위정사각형을 필터로 하여 훑으면서 지나가는데 모든 값은 0과 1로 주어지므로 단위 정사각형이 구성될 경우 정사각형 내의 값을 아무리 크게 업데이트 해줘도 움직인 필터에서 구성되지 않을 경우의 minimum값은 여전히 0이다. 이 성질을 이용해서 누적해가면서 정사각형이 구성되는 경우를 구하면 된다. 코.. 2021. 6. 23.
[ 백준 ] 2630 색종이 만들기 파이썬python 풀이 // 문제 요약 위와 같이 절반씩 나누어서 만들 수 있는 가장 큰 정사각형 종이를 원할때 얻을 수 있는 종이 중에서 파란색과 흰색의 수는 각각 몇장씩인지 출력하여라 // 사고 분할 정복을 사실상 한번도 구현해보지 않은 상태에서 만난 문제 처음에는 종이를 나눈 횟수에 따라 정사각형의 시작점과 끝점을 구하고 그 안에서 탐색을 다시 하는 함수를 탑다운으로 짜고 있었는데 짜면서 바로 아 이방법으로는 안되겠다 하는 부분이 너무 많아서 그냥 풀이를 바로 찾아봤다. 이 풀이는 분할정복 중에서도 4개로 나뉘는 방식이라 하여 쿼드트리 방식이라고 한다. 코드를 보자. // 풀이 https://url.kr/1zmqlt hyun06000/coding_test_study_with_python It is a coding test.. 2021. 6. 23.
반응형

티스토리툴바