문제 바로가기 (백준) 완전탐색 문제였고 아직 시간복잡도에 대한 개념이 덜 잡혀있음을 깨달았다. 13Cm의 조합은 100,000을 넘지 않으므로 시간 초과 없이 문제를 해결할 수 있다. (문제에서 치킨집 개수의 범위를 정해준 것은 분명 이러한 이유가 있었기 때문인 점 기억하기!) 13Cm을 파이썬 조합 라이브러리를 이용해 코드를 간결하게 만들 수 있다. 치킨집 중 M개를 고르는 모든 경우에 대해 치킨 거리의 합을 계산하여(완전 탐색) 치킨 거리의 최솟값을 구한다. 1️⃣ 무한대 표현(INF) : 최단 경로 알고리즘에서 도달할 수 없는 노드에 대한 최단 거리 = 1e9 ex. temp = 1e9 2️⃣ 조합(Combination) from itertools import combinations # combi..
문제 바로가기(프로그래머스) 아이디어 : 구현(시뮬레이션), 전체탐색 전형적인 시뮬레이션 문제로, 문제에서 제시한 구체적인 처리과정을 차례대로 코드화하면 된다. 문제를 제대로 이해하는 데 꽤 오랜 시간이 걸렸다. (카카오 코테의 대표적인 특징이랄까) 문제에서 제시해준대로 기둥과 보의 존재 요건을 그대로 적용한다. 설치할 때의 조건 만족 여부는 명확한 확인이 가능하지만, 삭제할 때의 조건 만족 여부는 주변의 여러 기둥, 보를 모두 확인해봐야 하므로 굉장히 까다롭다. 따라서 삭제를 요구할 때마다 일일이 전체 구조물을 확인하는 전체탐색 방법을 사용할 수 있다. 시간복잡도가 문제일 수 있지만, 문제에서 제한한 전체 명령의 개수는 최대 1,000개 이다. O(M^2)으로 하는 것이 가장 이상적일텐데, 이 문제의 ..
문제 바로가기(프로그래머스) 아이디어 : 구현(완전탐색), 2차원 리스트 회전 배열을 회전, 이동시켜야 한다는 부분에서 턱 막힌 문제였다. 회전 관련 부분은 따로 다뤘었고, 이동 문제는 배열을 직접 이동시킬 게 아니라, 기본 Lock 배열판을 크게 만들면 되는 거였다. 문제에서 제시한 자물쇠와 열쇠의 크기는 최대 20 x 20 이므로 완전 탐색을 이용해서 열쇠를 이동이나 회전시켜서 자물쇠에 끼워보는 작업을 전부 시도해봐도 무리가 없다. (400 * 400 = 16만, 일반적인 채점 환경에서는 1초에 2000만 ~ 1억 정도의 연산 처리 가능) 즉, 완전 탐색 아이디어를 사용하면 된다. 그리고 완전탐색을 수월하게 하고자 자물쇠 리스트의 크기를 3배 이상으로 변경하면 계산이 수월해진다. 그리고 그 중앙에 실..
코딩테스트 2020 KAKAO 신입 공채 를 풀다보니 2차원 배열의 90도 회전을 요구하는 문제가 있었다. 파이썬에서 2차원 리스트를 다룰 때 종종 사용되는 개념이므로 코드공식에 적어두고 필요할 때마다 꺼내봐야겠다. 그 전에 회전 알고리즘 원리를 먼저 파악해보자. 해당 2020 카카오 문제를 풀면서 2차원 배열 회전을 처음 맞닥뜨렸다면 절대 제시간 내에 풀지 못했을 것이다.. 보다 이해하기 쉽게 정리해봤다. 시계방향으로 90도 회전할 때, 회전 후의 행과 열 값을 알아야 한다. 2차원 배열이 회전할 때는 일정한 규칙이 있다. 90도 회전할 때의 위치를 모두 연결해보면 일정한 사이클이 있다. 사이클이 생긴다는 것은 요소의 합이 N일 가능성이 있다. (이때 N은 사각형의 크기) 그래서 나온 공식이 사진의 1..
이코테 책에서 풀다가 복습할 내용들만 정리해본다. 자세한 문제는 '이것이 코딩테스트다 with 파이썬 (나동빈)' 책에서 확인하기 구현 문제란 특별한 알고리즘 기법은 필요 없는 정확한 풀이가 핵심이 되는 문제를 말한다. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미하며 나는 이런 부분에 많이 취약한 것 같다. - 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제 - 특정 소수점 자리까지 출력해야 하는 문제 - 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 - 2차원 배열에서의 이동, 회전 등 까다로운 문제 특히 완전탐색과 시뮬레이션 유형은 모두 구현 유형으로 볼 수 있다. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시..
이코테 책에서 풀다가 복습할 문제들만 정리해본다. 자세한 문제는 '이것이 코딩테스트다 with 파이썬 (나동빈)' 책에서 확인하기 1️⃣ 만들 수 없는 금액 (K 대회 기출) N개의 동전으로 양의 정수 금액 중 만들 수 없는 최솟값을 구하는 프로그램을 작성하라. 첫번째 풀이) 1원부터 만들 수 있는 최대값까지 주어진 N개의 동전으로 만들 수 있는지 확인해야 하므로 먼저 화폐 단위를 내림차순으로 정렬한다. 예를 들어 3, 2, 1, 1, 9 가 주어졌다면 9, 3, 2, 1, 1 로 정렬한다. 그리고 1원부터 주어진 동전 조합으로 만들 수 있는지 coin[0]부터 체크한다. 즉, 9부터 3, 2, 1, 1 순으로 1원을 만들 수 있는지 확인하고 coin[3] = 1로 만들 수 있음을 확인하면 다음 숫자인 ..
기초 100제는 알고리즘 문풀에서 많이 사용되는 기본 코드 유형과 관련된 문제(특히 구현 implementation 관련)들로 이루어져 있다. 자신감을 기르기에 딱 좋은 사이트이다. 🌳 기억하면 좋을 구현 팁들 input().split(':')를 사용하면 입력받은 값을 콜론 ':' 기호를 기준으로 자른다. input().split()는 공백을 기준으로 입력값을 자른다. print(a, b, sep=':')를 사용하면 콜론 ':' 기호를 사이에 두고 a:b 형식으로 값을 출력한다. (sep은 seperator를 의미함) 키보드로 입력되는 것들은 기본적으로 문자열로 인식되고, 문자열끼리 더하기(+)하면 두 문자열이 합쳐 연결된(concatenate) 결과를 만들어 낸다. 10진수 int 형의 숫자를 %x, ..
SELECT DISTINCT CART_ID FROM CART_PRODUCTS WHERE NAME = 'Milk' and CART_ID IN (Select C.CART_ID FROM CART_PRODUCTS as C WHERE NAME = 'Yogurt') ORDER BY CART_ID; A와 B를 동시에 구입한 장바구니가 있는지 알아보는, 대표적인 연관분석 문제였다. SQL에서 연관분석을 해보리란 생각은 안 해봤는데 (맨날 R에서만 해봤음) 생각보다 간단하게 중첩쿼리문으로 해결했다. SELECT P.CART_ID FROM CART_PRODUCTS as P, CART_PRODUCTS as C WHERE P.CART_ID = C.CART_ID and P.name = 'Milk' and C.name = 'Yo..
