CS/알고리즘 문제 풀이
[백준] 1325 - 효율적인 해킹 [Python(파이썬)]
문제 https://www.acmicpc.net/problem/1325 max_cnt: max_cnt = cnt results.append([i, cnt]) for i, cnt in results: if cnt == max_cnt: print(i, end = ' ')
CS
CS/알고리즘 이론
[알고리즘] 이진 탐색(Binary Search)
순차 탐색 리스트 A에 n개의 수가 저장되어 있을 때, 어떤 수 X가 A에 저장되어 있는지 알고 싶다. X가 A에 없는 경우 A의 첫번째 원소부터 마지막 원소까지 모든 수를 살펴봐야 하므로 n번의 비교가 반드시 필요하고, 이에 따른 시간 복잡도는 O(n)이다. 이와 같이 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이 바로 순차 탐색이다. 이진 탐색 하지만, 만약 A의 수들이 오름차순으로 정렬된 상태라면 더 적은 비교를 통해 X를 찾을 수 있다. 바로 이진탐색을 이용하는 것이다. 이진 탐색이란 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 탐색 범위가 매우 큰 문제가 주어질 때, 이진 탐색을 이용하면 문제를 효율적으로 해결할 수 ..
CS/알고리즘 문제 풀이
[백준] 1759 - 암호 만들기 [Python(파이썬)]
문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 백트래킹을 이용하거나 combination 함수를 사용하는 두 가지 방법으로 풀 수 있다. 문제 자체의 난이도는 그렇게 높지 않았지만, "최소 한 개의 모음과 최소 두 개의 자음으로 구성되어있다."라는 제약 조건에 대한 처리를 해주지 않으면 테스트케이스는 통과하더라도 틀릴 수 있는 문제였다. 나는 두 가지 방법으로 다 풀어봤는데, 속도적인 측면에선 combination 함수를 사용하는 편이 ..
CS/SQL
[MySQL] 하나의 글과 연관된 여러 개의 이미지 추출하는 쿼리 작성하기 (feat. GROUP_CONCAT)
하나의 글에 연관된 여러 개의 이미지 출력하고 싶을 때가 있다. 인스타그램을 떠올려보면 쉽게 이해가 갈 것이다. 우리가 원하는 데이터의 형태는 게시물(post) 하나에 여러 개의 이미지가 묶여서 하나의 행으로 구성되는 것이다(이때, 이미지는 blob형태가 아닌 varchar로 주소의 형태로 저장된다고 가정한다). 말로 하면 살짝 이상한데, 객체 형태로 표현하자면 다음과 같다. { id: 1, content:"글1", paths: [...] } 어떻게 쿼리를 작성할 수 있을까? 다음과 같은 테이블이 있다고 가정하자. posts 테이블 ID CONTENT 1 글1 2 글2 3 글3 images 테이블 ID POST_ID(FK) PATH 1 1 /path1 2 2 /path2 3 2 /path3 4 2 /pa..
CS/알고리즘 문제 풀이
[백준] 1697 - 숨바꼭질 [Python(파이썬)]
문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 언뜻 문제만 DFS를 이용해 백트래킹을 해야 하는 문제로 보인다. 하지만 이 문제는 최단 경로를 구하는 일차원 그래프 탐색 문제였다. 오히려 다른 BFS문제들보다 더 심플하다. 방문처리만 조금 신경써준다면 수월하게 해결할 수 있다. 미리 그래프의 크기만큼의 리스트를 선언하거나 집합을 이용해서 O(1) 안에 방문처리를 해줄 수 있도록 하자. 코드
