코딩테스트/Python 문제풀이
[백준] 연산자 끼워넣기
https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N개의 수와, N-1개의 연산자가 주어지면, 연산자를 적절하게 배열하여, 앞에서 부터 계산하였을 때, 최댓값과 최솟값을 return해야 하는 문제입니다. (이 때, 연산자는 +,-,*,/ 가 있습니다. 또 N개의 수의 위치는 고정되어 있다고 가정하고, 연산자의 위치만 바꾸어야 합..
[백준] 상어 초등학교
https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 학생들을 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. 다..
[백준] 불 끄기
https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 일종의 brute forcing하는 문제인데 규칙성을 찾아 횟수를 줄여야 하는 문제입니다. 우선 문제부터 간단하게 요약하면, #O######## OOO####### #O######## ####OO#### ###O##O### ####OO#### ########## ########O# #######OOO ########O# 다음과 같이 10 x 10의 array에서 O는 불이 켜져있음을 의..
[백준] 스도쿠
https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 하다 만 스도쿠가 input으로 들어오면, 마저 끝내서 return을 해야 하는 문제입니다. 처음에는 시간초과가 나왔습니다. 처음 풀이 아이디어와, 나중에 어떻게 고치는지 순서로 설명을 해보겠습니다. 우선 이 문제를 보면, dfs를 사용해야 하는 것을 알 수 있습니다. 간단한 예시를 통해 아이디어를 살펴봅시다. 다음 그림과 같이..
[백준] 팰린드롬 분할
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 다이나믹 프로그래밍을 두번 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 주어진 문자열에 팰린드롬 분할을 한 갯수의 최솟값을 출력해야 합니다. 처음에 두개의 다이나믹 프로그래밍중 하나만 이용하여 시간초과가 났었고 이후에 해결을 하였는데 각각 과정들을 한번 설명해 보겠습니다. (큰 아이디어에서 출발해서 수정을 한 부분의 아..
[백준] ACM Craft
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상정렬과 DP를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 다음과 같이 건물들을 건설하는 게임을 하는데, 특정 건물을 건설하면 반드시 승리하게 됩니다. 이 때, 건물들 간에는 우선순위(규칙)이 정해져 있습니다. 특정 건물을 짓는데 걸리는 최소 시간을 return 해야 합니다. 위 그림을 통해 간단하게 설명하면, 만약 4번건물을 짓는 최소시간을 구해야 한다면, 1->3&2->4 ..
[백준] N과 M (8)
https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net python의 itertools 라이브러리를 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N개의 자연수중 중복을 허용해서 M개를 뽑을 때, 이 뽑는 경우들을 사전의 순서에 맞게 출력하면 되는 문제입니다. 단순하게 그냥 sequence를 미리 sorting 해주고, python itertools의 combinations_with_replacement를 사용하여 갯수만큼 뽑아내면,..
[백준] 공항
https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 그리디 알고리즘과 분리집합을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 1~G번 게이트가 있는 공항에 비행기 P대가 옵니다. 이 때, 각 비행기는 숫자 gi를 가지는데 이 1