유진's 공부로그

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 이하 아이..

FloodFill과 그래프 탐색 floodfill 같은 경우엔 주어진 시작점으로부터 연결된 영역의 크기를 구하는 문제이다. (하나의 알고리즘으로 분류되는 듯하다) 프로그래머스 스터디에 참가하면서 floodfill 이라는 문제를 오래 붙잡고 있었는데, 이런 문제는 쉽게 접근하자면 모든 점마다 bfs, dfs를 수행하면서 영역 별로 "조져주는" 것이 해결책임을 알아냈다! 한 번의 탐색만으로는 수행이 불가능하다. (모든 정점을 한 번씩만 방문하는 걸로는 해결이 안된다는 의미) 처음에는 dfs 풀이만을 생각해냈는데, 한 번의 dfs만으로 풀이하려 했기에 해당 풀이도 오류가 떴다 (당시엔 몰랐음 ㅎㅎ... 컴퓨터는 죄가 없다. 코드를 짜는 나에게 있다 죄는 ^^). bfs로는 도저히 어떻게 푸는 건지 감이 안와서..

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 (깊이 우선 탐색) 일단 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 ..

인코딩 문제로 인해서 윈도우에서 압축한 zip파일을 리눅스에서 압축 해제를 하고자 할 때 #Uac ~~ 등으로 폴더명이나 파일명이 깨질 경우가 있다. 폴더명과 파일명이 한글로 되어 있을 경우인데, 이러한 경우에는 unzip 옵션을 조정함으로써 쉽게 해결할 수 있다. unzip -O cp949 [압축파일 이름] -d [압축 해제하고자 하는 디렉토리명] -d 뒤부터는 압축 해제를 원하는 디렉토리에 대한 옵션이므로 따로 지정하지 않으면 현재 디렉토리에 압축 해제가 된다. 하지만 위의 명령어만으로는 해결이 되지 않는 경우가 있다. 이때는 locale을 조정해줘야 한다. locale을 터미널에 입력하고 현재 locale이 어떻게 되어있는지 확인한다. 아마도 en_US.UTF-8로 되어 있을텐데 이 경우에는 명령창..

머신러닝 혹은 딥러닝(Computer Vision) 분야 관련 논문을 읽다보면 Cascade라는 말이 종종 나오는데, 정확히 짚고 넘어갈 필요가 있어 보여 정리한다. Definition of Cascade a process whereby something, typically information or knowledge, is suceessively passed on. 여기서 주목할 점은 successive하다는 점이다. 이걸 ML 관점에서 본다면 정보가 successive하게 전달이 된다는 것이므로, layer 간의 위계적인 정보 전달 혹은 boosting machine에서의 additional learning 등을 생각해볼 수 있을 것이다. (병렬적이 아니라 직렬적인 것에 가깝다고 생각해보자. 여러 개..

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 = "..

카운터에 대한 새로운 지식을 알게 되어 글을 적는다. 파이썬 Counter는 collections 라이브러리에 정의되어 있으며, iterator에서 각 요소 별로 몇 번 등장하는지 count해주는 딕셔너리의 서브클래스이다. (엄밀한 표현은, A Counter is a dict subclass for counting hashable objects ) cf.) Counter는 딕셔너리이다. Counter도 딕셔너리이기 때문에 Counter에서 바로 iteration을 수행하면 key값만을 반환한다. 따라서 key, value 쌍이 필요하다면 Counter객체.items() 의 메소드를 활용해서 key, value 쌍을 얻어내야 한다. 실제로 많이 사용해보지는 않았는데, Counter 간의 연산이 된다는 사실..

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/..