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은 하나만 존재해야 ..
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(맨 왼쪽 열)중 하나..
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 + _ _ .....
Algorithm
[백준(파이썬/Python)] 8983_사냥꾼 - 이분탐색
https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 이 문제는 모든 사대에서 사격 가능한 영역을 구하고, 그 영역 안에 동물들이 있는지를 확인하는 방식으로 풀었을 때 시간복잡도가 O(M*N*L)이 소요됩니다. 비효율적이죠. 따라서 이분탐색을 통해 각 동물의 위치에서 가장 가까운 사대의 위치를 찾고 그 거리가 사정 거리 안에 있는지를 확인해주는 방식으로 문제를 풀었습니다. 각 동물의 위치에서 가장 가까운 사대의 위치는 x좌표가 가장 가까운 사대이기 ..
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 이라고 ..
Algorithm
[백준(파이썬/Python)] 1520_내리막 길 - DFS, DP
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DFS + DP를 이용한 문제입니다. 우선 이 문제를 DFS로만 풀려면 가능한 모든 경로의 수를 다 세야하기 때문에 정말 많은 경우의 수가 나오게 됩니다. 그러면 시간초과가 뜨겠죠? 500 * 500 배열에서 계속해서 상하좌우로 이동이 가능한 상황을 떠올려 보면 직관적으로 느낄 수 있습니다. 따라서 이 문제는 DP를 이용해서 불필요한 연산을 줄여야하는데, 이를 위해서는 우선 DP의 사용 정당성에 대해 ..
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를 리스트 형태로 바꾸고 나면, 해당 이차원 리스트를 길이 순으로 정렬하고 길이가 짧은 리스트의 앞에서부터 결과 리스트..
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차원 리스트를 ..
Algorithm
[백준(파이썬/Python)] 10282_해킹 - 다익스트라
https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 문제의 조건 중에서 "d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다." 라는 표현이 있습니다. 이 부분을 주의해서 각 노드(컴퓨터)의 방향성을 정해줘야 합니다. 즉, a에서 b로 방향이 생기는 것이 아니라, b에서 a로..
Algorithm
[백준(파이썬/Python)] 11779_최단경로 구하기2 - 다익스트라
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이 문제는 다익스트라 알고리즘을 통해 최단거리를 구한 후, 최단 거리에 대한 경로를 출력을 요구하고 있습니다. 따라서, 일반적인 다익스트라 구현에 경로를 출력하기 위한 구현이 추가로 필요한데 이 부분은 아래 코드에서 parents라는 딕셔너리로 구현햇습니다. 현재 지점에서 다른 지점으로 넘어가면서 최단거리를 갱신할 때 다음 지점의 부모를 현재 지점으로 설정해주는 것..
