CS/Algorithm
[백준(파이썬/Python)] 1644_소수의 연속합(투 포인터, 에라토스테네스의 체)
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net N이 클 때 소수 판별을 효율적으로 할 수 있는 에라토스테네스의 체와 투포인터 개념을 활용하는 문제입니다. 에라토스테네스의 체는 소수 판별할 때 대표적인 알고리즘으로 "임의의 정수 x가 소수라면, x의 배수는 소수가 아니다"라는 명제를 이용해 구현하는데요. 이를 구현하는 방법은 아래 코드에서 prime_list() 함수로 구현되어 있습니다. 한편, 문제에서 구하고자 하는 것은 어떤 수 N을 연속한 소수의 합으로 나타낼 수 있는 경우의 수입니다. 따라서, 에라토스테네스의 체로 구한 N보다 작은 소수들의 집합을 리스트로..
CS/Algorithm
[프로그래머스(파이썬/Python)] 수식 최대화(2020 카카오 블라인드 채용)
https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 2020년 카카오 블라인드 채용에 있는 문제로, 문제의 요구사항을 충실히 구현하면 되는 문제입니다. 우선 문자열로 주어진 expression을 splitExpression() 함수를 구현해서 숫자와 연산자 집합으로 분리를 했습니다. 문제 조건에서 "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다. 라는 내용이 있기 때문에, numbers..
CS/Algorithm
[백준(파이썬/Python)] 9663_N-Queen - 백트랙킹
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen 문제는 N*N 체스판에 상하좌우, 대각선에 퀸이 존재하지 않도록 적절히 퀸을 위치하는 문제입니다. 백트랙킹으로 풀 수 있는 대표적인 문제죠. 이 문제는 시간 제한이 상당히 타이트한데, 파이썬으로 제출할 경우 이차원 배열을 쓰면 당연히 시간초과가 나고 최적화를 해서 제출해야만 정답 판정을 받을 수 있습니다...ㅠㅠ 문제를 푸는 아이디어는 다음과 같습니다. 1. 각 행마다 Queen은 하나만 존재해야 ..
CS/Algorithm
[프로그래머스(파이썬/Python)] 키패드 누르기(2020 카카오 인턴십)
https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 문제의 요구사항을 그대로 구현하면 됩니다. 키패드의 숫자의 위치를 dictionary 형태로 표현했는데 key = 키패드의 숫자, value = 숫자의 위치로 지정했습니다. 그리고 주어지는 각 숫자에 대해 해당 숫자가 1, 4, 7(맨 왼쪽 열)중 하나..
CS/Algorithm
[백준(파이썬/Python)] 2225_합분해 - DP
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP를 맨 처음에 공부할 때 즈음에 배우는 피보나치 수를 DP로 구하기가 떠오르는 문제였습니다. 탑다운 방식으로 DP를 해결하는 방식인데, 이 문제 역시 문제 풀이의 로직만 생각해낸다면 구현은 탑다운으로 거의 똑같이 할 수 있는 것 같습니다. 이 문제가 DP의 정당성을 가지는 이유(부분 최적해가 전체 최적해를 보장하는 이유)는 각 자릿수가 하나라도 다르면 다른 경우의 수로 취급하기 때문이입니다. 예를 들어 어떤 수 N을 3개의 숫자로 표현한다고 해보죠. N = 0 + _ _ N = 1 + _ _ N = 2 + _ _ .....
CS/Algorithm
[백준(파이썬/Python)] 8983_사냥꾼 - 이분탐색
https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 이 문제는 모든 사대에서 사격 가능한 영역을 구하고, 그 영역 안에 동물들이 있는지를 확인하는 방식으로 풀었을 때 시간복잡도가 O(M*N*L)이 소요됩니다. 비효율적이죠. 따라서 이분탐색을 통해 각 동물의 위치에서 가장 가까운 사대의 위치를 찾고 그 거리가 사정 거리 안에 있는지를 확인해주는 방식으로 문제를 풀었습니다. 각 동물의 위치에서 가장 가까운 사대의 위치는 x좌표가 가장 가까운 사대이기 ..
CS/Algorithm
[백준(파이썬/Python)] 두 용액 - 이분탐색, 투포인터
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net '맞왜틀'을 엄청 반복했던 문제입니다... 이 문제에서 약간 트릭(?)이었다고 생각하는 부분은 산성과 알칼리 용액이 모두 존재했을 때에도 한 종류의 용액 두 개를 골라 혼합했을 때가 최적해가 될 수 있다는 것입니다. 예를 들어 -100, -50, 1, 2라고 주어졌을 때 정답은 1+2 = 3이 되어야 하는데, 잘못 생각하면 abs(-50 + 2) = 48 이라고 ..
CS/Algorithm
[백준(파이썬/Python)] 1520_내리막 길 - DFS, DP
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DFS + DP를 이용한 문제입니다. 우선 이 문제를 DFS로만 풀려면 가능한 모든 경로의 수를 다 세야하기 때문에 정말 많은 경우의 수가 나오게 됩니다. 그러면 시간초과가 뜨겠죠? 500 * 500 배열에서 계속해서 상하좌우로 이동이 가능한 상황을 떠올려 보면 직관적으로 느낄 수 있습니다. 따라서 이 문제는 DP를 이용해서 불필요한 연산을 줄여야하는데, 이를 위해서는 우선 DP의 사용 정당성에 대해 ..
CS/Algorithm
[프로그래머스(파이썬/Python)] 튜플 - 문자열 처리
https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 처음에 주어진 문자열 s를 리스트로 바꿔서 처리하기 위해 크게 1) 여는 대괄호, 2) 쉼표, 3) 닫는 대괄호, 4) 숫자일 때로 조건을 나누어 처리했습니다. 위 과정을 통해 주어진 문자열 s를 리스트 형태로 바꾸고 나면, 해당 이차원 리스트를 길이 순으로 정렬하고 길이가 짧은 리스트의 앞에서부터 결과 리스트..
CS/Algorithm
[백준(파이썬/Python)] 15683_감시 - 구현, 시뮬레이션
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 이 문제에서 핵심적인 부분은 어떻게 모든 카메라의 관찰 방향의 조합을 다 찾아서 그 때의 감시를 받지 않는 구역의 개수를 체크할 것인가입니다. 저같은 경우에는 카메라마다 감시 방향도 깔끔하게 떨어지지가 않아서 카메라 1~5번 마다 cam{n}_direction이라는 방향을 입력해주었고, 감시 방향을 순회하기 위해 [[방향1의 방향들], [방향2의 방향들]...] 식으로 3차원 리스트를 ..
