파이썬
-
백준. 11047 동전0 | 파이썬, 그리디 알고리즘IT/알고리즘 해설 2021. 10. 28. 00:31
문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 해설 이 문제는 그리디 알고리즘을 사용한다. 그리디 알고리즘이란, 말그대로 "탐욕적"으로 문제를 해결하는 방식인데, 해결해나가는 과정에서 가장 최선의 선택을 해서 풀어나가는 알고리즘이다. 그렇기 때문에 항상 가장 올바른 답을 도출하지는 않는다. 그러나 속도 면에서 다른 그래프 탐색 알고리즘보다 빠르다는 장점이 있다. 준규는 동전을 총 N종류를 가지고 있고, 이 동전들을 사용해서 K원만큼 만들려고 한다. K원을 만들기 위해서 가장 큰 동전부터 선택해나가면서, K원이 될 때까지 동전을 찾으면 된다...
-
백준 1707. 이분 그래프 (파이썬)IT/알고리즘 해설 2021. 10. 8. 22:05
문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 해설 진짜 역대급으로 삽질했던 문제인 것 같다. 결론부터 말하면 이분 그래프는 dfs나 bfs로 풀 수 있다. 여기서는 dfs로 풀어보기로 한다. 먼저, 이분 그래프가 무엇인지와 dfs가 무엇인지부터 짚고 넘어가보자. 1) 이분 그래프란? - 문제만 보고서는 솔직히 무슨 소리인지 이해가 되질 않았다. 그래서 한참을 문제를 보고 이해하려고 하다가, 결국은 검색으로 해결하였다. (앞으로 문제가 조금 더 친절해졌으면 좋..
-
파이썬 기초 정복하기 -3) 자료형(타입) : 데이터의 다양한 형태IT/파이썬 기초 2021. 10. 5. 12:03
앞 장에서 변수를 선언하는 방법과 의미를 알아보았다. (https://2island.tistory.com/24) 이번에는, 변수 선언 시, 변수에 대입해주는 "값"의 종류에 대해서 이야기해보려고 한다. a = 1 위 코드에서는 a라는 변수에 1이라는 값을 넣어줬다. 1이라는 값은 우리가 아는 "숫자"의 형태이다. 즉 이 데이터의 종류는 숫자가 된다. 우리는 이런 종류를 앞으로 type 또는 자료형이라고 부를 것이다. 1) 타입 이 데이터의 타입에는 어떤 것들이 있을까? - 정수 : int 정수는 우리가 수학시간에 배웠던 대로, 0을 포함한 모든 양수와 음수를 정수라고 한다. -1, -100, 1, 434 등등 소수점이 없는 우리가 아는 일반적인 숫자들을 정수라고 부른다. 그리고 우리는 이 정수형 타입을 ..
-
파이썬 기초 정복하기 -2) 변수란? 파이썬에서 변수의 의미IT/파이썬 기초 2021. 10. 1. 17:16
앞 장에서, 프로그램이라는 것이 어떻게 동작하고, 파이썬은 어떤 흐름으로 실행되는지에 대해서 알아보았다. (참조 : https://2island.tistory.com/21) 이제는 본격적으로 파이썬 문법에 대해서 배워볼 것이다. 우선 프로그래밍을 처음 배우는 사람이라면 "변수"라는 것이 무엇인지 정확히 인지하여야 한다. 우리가 여지껏 배웠던 변수는 수학에서 배웠던 "어떤 값이 들어올지 모르는, 변할수 있는 수"였다. 즉, 방정식에서 x,y값이 변수였다. 그런데 프로그래밍에서 변수는 조금 의미가 다르다. 바로 "값을 담아두는 공간"으로 해석할 수 있다. 앞 장에서 우리는 휘발성 데이터가 RAM에 저장된다고 했었다. 프로그래밍에서 말하는 변수는 휘발성 데이터이다. 왜냐하면, 프로그램이 끝나면 모두 사용되지 ..
-
프로그래머스. 2021 KAKAO BLIND RECRUITMENT. 신규 아이디 추천(파이썬)IT/알고리즘 해설 2021. 9. 29. 23:27
문제 설명 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다. 다음은 카카오 아이디의 규칙입니다. 아이디의 길이는 3자 이상 15자 이하여야 합니다. 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다. 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다. "네오"는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이..
-
파이썬 기초 정복하기 - 1) 프로그램 동작 순서 & 인터프리터IT/파이썬 기초 2021. 9. 28. 12:11
요즘 여러 사이트들을 들어가보면, 짧은 기간안에 프로그래밍을 가르쳐주겠다고 나온 강의들이 많다. 그런데 프로그래밍을 하면 할수록 프로그램이 컴퓨터 내부에서 어떻게 돌아가는지를 정확히 알아야(기초를 어느정도는 알아야) 디버깅, 응용프로그래밍 등을 할 때 더 높은 이해도를 가지고 더 좋은 코드를 짤 수 있다는 생각이 들었다. 그래서 최대한 자세하고 디테일하게 공부할 수 있도록 포스팅을 해보려고한다. 1. CPU & RAM & Hard Disk의 역할 "프로그램"이라고 하면, 일반적으로 소스코드 작성을 통해서 만들어진 소프트웨어를 의미한다. 웹상에 존재하는 각종 포털사이트, 모바일에서 사용할 수 있는 어플리케이션 등등 굉장히 많은 프로그램들이 존재한다. 이 프로그램들은 기본적으로 어떻게 돌아가고 있을까? 시대..
-
백준 1038. 감소하는 수 (파이썬)IT/알고리즘 해설 2021. 9. 23. 22:06
문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 해설 이 문제는 제대로 안 읽으면 헷갈릴 수 있다. 난이도가 solved.ac 기준 골드 5인데, 문제 자체가 어렵게 쓰여서 골드 5인듯하다. 알고리즘 자체는 어렵지 않다. N번째 감소하는 수란, 0부터 시작해서 감소하는 수 집합에서 N번째 수는 무엇인지 묻는 문제이다. 여기서 감소하는 수란, 주어진 숫자의 맨 첫자리부터 끝자리까지 계속해서 감소하는 수..
-
프로그래머스 2020 카카오 인턴 - 키패드 누르기 해설 (파이썬)IT/알고리즘 해설 2021. 9. 14. 14:14
문제 설명 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 4..