말랑말랑

[2021-07-05] 전직장 동기와 오붓하게 알고리즘 스터디를 하며 매주 문제를 풀고 있지만 점점 공부하는게 많아지니(ㅋㅋㅋㅋ) 블로그를 소홀히 하게 됐다,,, 열심히 올려야 하는데..!! 올리고 싶은게 넘 많은데 의지에 비해 몸이 안따라준다 희희 오늘 푼건 알고리즘 문제 중에서도 가장 Hate하는 동적 계획법^^이라 어렵기도 하고 까먹기 전에 포스팅을 해야 해서 올린다 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다..

[21-05-29] 비교적 익숙한 해시..!! 한번에 퍼펙트하게 풀진 못했지만 그래도 다른 알고리즘 문제보단 비교적 빠르게 풀었다 문제 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한사항 phone_book의 길이는 1 이상 1,000,000..

[21-05-22] 친구와 소소하게 알고리즘 스터디를 시작하며 프로그래머스 DFS/BFS 문제부터 풀어보았당 문제 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모..

[21-04-20] 분명 배웠던 하노이탑이 새삼 새롭게 느껴졌다... 옛날 옛적 알고리즘 수업 시간에도 하노이탑의 풀이과정은 뭔가 이해가 잘 되지 않았었는데 아마 나는 재귀 자체에 약한가보다...^^^,,, 이번에도 역시,..,,ㅎㅎ 익숙하게 다룰 수 있도록 열공하자,,,^^,,, 문제 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 분석 문제 자체가 이동 횟수도 출력해야 하고 이동 과정도 출력해야 한다. 그럼 함수 어딘가에 출발지..

[21-04-20] 문제 www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 분석 이 문제 또한 피보나치 자체의 개념을 알면 금방 풀 수 있는 문제다. (문제에도 나와있음) N번째 숫자는 N-1번의 숫자와 N-2번의 숫자를 더한 값이다. ex) 7번째 수 : 13 = 5(5번째 수) + 8(6번째 수) 피보나치 수열 > 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 61..

[21-04-20] 재귀쪽 공부하기!!!!!! 문제 www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 분석 팩토리얼이라는 개념 자체를 알고 있으면 매우매우 쉬운 문제. ko.dict.naver.com/#/entry/koko/0c3899cc8d8c413187e8e29a6b078f34 네이버 국어사전 3개의 한국어 대사전 (표준국어대사전, 고려대한국어대사전, 우리말샘), 상세검색, 맞춤법, 보조사전 ko.dict.naver.com 쉽게 말해 N!은 정수 N에서 부터 1까지의 모든 값을 곱한 것을 말한다. ex) 5! = 5 * 4 * 3 * 2 * 1 1. 재귀 규칙..

BFS에 이어 DFS도 같이 공부했다. 재귀 쪽은 실무에서 많이 사용하진 않아서 엄~청 익숙한 방법은 아니지만? 구현하는게 어렵진 않았다. 애초에 BFS보다는 DFS가 개념이 쉽다. DFS를 먼저하고 BFS 보니 잠깐 띠용 했었음. + DFS는 재귀로 구현하는게 쉬운듯하다. 혹시 모르니 Stack을 사용해서도 구현해봐야겠다. DFS(깊이 우선 탐색) BFS와 같이 그래프 이론이자 완전탐색 방법 중 하나이다. 깊이 우선 탐색으로 노드 하나를 정하고 연결되어 있는 노드가 없을 때까지 깊이 탐색한 후 다음 노드로 넘어간다. 시작 노드와 연결 된 노드들을 찾은 후, 그중 하나를 골라 연결된 노드가 없을때까지 그 줄기를 탐색한다. BFS가 가로로 쭉 쭉 탐색하는 느낌이였다면, DFS는 세로로 쭉 쭉 탐색한다. S..

알고리즘 이론을 정말 정말 오랜만에 다시 공부해보면서 첫번째로 그동안 부족하다고 느꼈던 탐색쪽을 공부했다. BFS(너비 우선 탐색) 그래프 이론이자 완전탐색 방법 중 하나이다. BFS은 너비 우선 탐색으로 가까운 노드를 우선적으로 방문하고 탐색한다. 그래프에서 인접하게 연결된 노드부터 쭉 방문한 후 그 다음으로 인접된 노드들을 순차적으로 방문하는 방식이다. 뎁스가 낮은(가까운) 노드부터 쭉 방문한 후 뎁스를 높여가는게 특징. Queue의 구조를 사용하는 방식 최단 거리 찾기와 같은 문제에서 자주 나온다고 한다. * 이론 공부는 youtu.be/CJiF-muKz30 을 참고했다. 설명을 쉽게 잘 해주신다. Queue를 사용한 BFS int[][] graph = { {}, {2, 3, 8}, {1, 7}, ..