유진's 공부로그

문제 https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 문제 요구 조건 가로 길이가 n으로 주어지고, 세로 길이는 2로 고정되어 있다. 세로를 2로 고정하기 때문에 고려할 사항은 가로 길이뿐이다. 따라서 가로 n을 어떻게 채울 것인가에 대해 생각하면 된다. 그렇게 되면 두 가지 선택지가 있다. 직사각형 모양 타일을 세로로 쌓거나 혹은 가로로 쌓거나이다. 즉, 1과 2를 사용해서 n을 잘 채우면 된다..

도커 이미지 내의 파이썬과 실제 프로젝트에 필요한 파이썬의 버전이 다를 수 있다. 이 경우에 파이썬의 버전을 업그레이드하는 방법을 정리해보고자 한다. 아래 서술할 내용은 파이썬의 버전 업그레이드보다는 여러 개의 버전을 한꺼번에 관리하는 것에 더 가깝다. 정리하자면, 파이썬 상위 버전을 설치한 후 python 커맨드를 날렸을 때 어떤 버전의 파이썬을 실행할 것인지를 상위버전으로 설정해주면 된다. 파이썬 상위버전 설치 참고로 bash 명령어는 root 사용자일 때는 sudo를 사용하지 않는다. 아래는 root 계정이 아님을 가정하고 명령어를 작성하였다. sudo apt update sudo apt install python3.7이렇게 설치를 한 후에 python --version으로 python 버전을 확인..

이야기에 앞서 VSC에서 코드를 주로 작성하는데 프로젝트마다 다른 conda 가상 환경을 사용하는 것을 선호한다. EDA를 하는 경우에는 jupyter notebook 환경에서 하는 게 편한데, VSC에서도 extension만 설치한다면 jupyter를 무리없이 사용할 수 있다. 다만 가상환경을 분리하는만큼 주피터 커널 또한 가상환경의 커널을 사용해야 하는데 이런 부분에서 종종 문제가 발생했다. (커널을 생성해줬는데 주피터에서는 인식하지 못하는 경우 등) 이 부분을 해결한 과정을 간단히 적어보고자 한다. 실행 환경 Ubuntu 20.04 (WSL) VSCode python 3.9.7 conda 4.11.0 VSCode 내 관련 extension 설치 python과 jupyter 관련 extension을 ..

문제 설명 m x n 크기인 사무실이 있습니다. 사무실에는 전염병에 걸린 직원이 있는데, 이 직원은 매일 상하좌우로 병을 퍼트려 다른 직원을 감염시킵니다. 단, 백신을 접종한 직원은 면역력이 있어 감염되지 않습니다. 예를 들어 2x4 크기 사무실에서, 병에 걸린 직원의 위치가 (1,4), (2,2)이고 백신을 맞은 직원의 위치가 (1,2)입니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기 까지는 이틀이 소요됩니다. 사무실의 크기 m, n과 병에 걸린 직원의 위치 infests, 백신을 맞은 직원의 위치 vaccinateds가 매개변수로 주어집니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기까지 며칠이 걸리는지 return 하는 solution 함수를 완성해주세요. 제한 사..

https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제 풀이 입력 문자열의 길이가 최대 1000이었으므로 완전 탐색이 가능할 것으로 생각함. 따라서 망설임 없이 loop를 두 번 타는 걸 생각했다. → O(n^2) 풀이 압축률이 가장 높은 단위에서의 압축된 문자열의 길이를 반환해야 하기 때문에, 단위를 1부터 전체 문자열 길이까지 설정하고 각 단위에서 단위 문자열의 중복 개수를 찾아야 한다. 로직은 간단..

문제 설명 각 캐릭터는 보스몹을 잡기 위해 아이템을 사용해서 공격력을 높일 수 있음. 아이템을 사용하면 공격력이 올라가는 대신 체력이 감소함. 캐릭터는 아이템을 사용해서 공격력을 증가시키되 최소 체력은 100 이상을 유지해야 함. 이 상황에서 팀 내 공격력을 최대화하기 위해 사용 가능한 아이템 수를 구하여라. 입력 입력으로는 1) 각 캐릭터의 잔여 체력, 2) 아이템을 사용하며 증가하는 공격력 & 소모되는 체력 이 주어짐. e.g.) healths = [100,200,300] // items = [[30, 20], [100, 50]] 제한 사항 healths의 길이는 1 이상 10,000 이하 healths의 원소는 1이상 1,000,000 이하인 자연수 items의 길이는 1 이상 5,000 이하 아이..

DFS(Depth-First Search; 깊이우선탐색)와 BFS(Breadth-First Search; 너비우선탐색)는 그래프의 정점을 방문하는 그래프 탐색(Graph Search or Graph traversal; 그래프 운행) 방법의 큰 갈래이다. 코딩 테스트 시에는 DFS를 좀 더 많이 활용하는 듯하다. DFS는 스택이나 재귀로, BFS는 큐로 구현한다. python에서 그래프는 아래와 같이 보통 딕셔너리를 활용해서 인접 리스트로 구현하는 경우가 많다. graph = { 1: [2,3,4], 2: [5], 3: [5], 4: [], ... } DFS (깊이 우선 탐색) 일단 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 ..

https://school.programmers.co.kr/tryouts/32181/challenges 문제의 핵심은 주어진 skill이 skill_trees 내 skill_tree에 올바른 순서로 들어가있는가이다. skill의 subsequence만 들어가도 무방하다. 문제에서 주어진 배열의 길이를 보았을 때 시간 복잡도를 고려할 만한 문제는 아님을 판단할 수 있어야 한다. 그리고 문제 요구 사항을 보고 어떤 자료구조를 사용할 것인지에 대한 감이 빨리 와야 할 것 같다. 나의 첫 풀이 def solution(skill, skill_trees): """ skill_trees 탐색하되...skill의 순서가 어떻게 되는지 체크 """ answer = 0 for sk in skill_trees: sk = "..

https://programmers.co.kr/learn/courses/30/lessons/12909 스택을 이용해서 풀이 가능한 전형적인 문제이다. 나는 직접 스택을 구현해서 풀이했지만, 프로그래머스 스터디 리더님께서는 스택을 직접 구현하지 않고 변수를 활용해서 풀이하셨다. 어쨌든 스택의 원리를 이용한다는 점에선 풀이 접근에 변함이 없다. 직접 구현하면서도 이렇게 푸는 것보다 더 나은 방법이 있겠다 싶었지만...나는 직접 구현하는 게 좀 더 직관적이라 매번 그렇게 푸는 것 같다. pop, push 연산을 수행하는 것보단 변수만으로 구현하는 게 효율성 면에서 낫다. 특히, 공간 복잡도 면에서 더욱 그럴 것이다. def solution(s): answer = True c = 0 for char in s: ..

프로그래머스에서 알고리즘 스터디를 진행 중인데 오늘 처음으로!!! for ~ else 문을 알게 되었다. 간단하게 말하자면, for loop이 break 없이 끝날 경우에 else문을 실행하는 것. break든 아니면 break 없이 모든 loop을 다 돌았든 for loop을 탈출했을 때 무조건 그 아래에 statement가 있으면 수행을 해야 한다. 하지만, 어떤 경우에는 loop을 정상적으로 탈출한 경우에만 statement를 수행하고 싶을 경우가 있을 것이다. 이럴 경우 flag를 달아주든지 해야하는데 for ~ else문을 사용하게 되면 이런 flag의 사용을 막을 수 있다. 프로그래머스 스킬 트리 문제(https://programmers.co.kr/learn/courses/30/lessons/..