전체 글
-
[백준 2922] 즐거운 단어 (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2020. 12. 15. 13:53
www.acmicpc.net/problem/2922 2922번: 즐거운 단어 상근이는 자신이 다니는 학교에서 영어단어를 가장 많이 외우고 있다. 그 비법은 바로 조기교육이었다. 상근이는 젖병을 물기도 전에 영어 단어를 외웠다. 따라서, 지금은 자리에 앉으면 사전을 www.acmicpc.net 문제풀이 mo : 모음 ja : 자음 S : 입력값 go(s, idx, ch) : 재귀적으로 _에 문자를 놓는 함수, s : 문자열, idx : 인덱스, ch : _에 지금까지 사용한 단어 verify(s) : s가 문제의 조건(자음, 모음 연속 3개인지 아닌지, s에 L이 포함되어 있는지)에 위배하지 않는지 확인 _ 에 들어올 수 있는 글자는 모음, L이 아닌 자음, L 총 3가지 가능 => 3^10 이므로 브루트..
-
[백준 14226] 이모티콘 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2020. 12. 15. 12:15
www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제풀이 S : 입력값 dp : 화면과 클립보드를 표현할 2차원 리스트, dp[i][j] = x : 화면에 있는 이모티콘의 갯수 i개, 클립보드에 있는 이모티콘의 갯수j개 일때 걸린 시간 x초 q : i, j 를 BFS로 탐색하는 deque ans : 결과값 1. BFS를 이용해 세 가지 경우를 탐색하여 deque에 넣어준다. (이때 각 연산은 1초가 소요) - 화면에 있는 i개의 이모티콘을 클립보드에 붙이는 경..
-
[백준 2091] 동전 (Python)Algorithm & Problem Solving/다이나믹 프로그래밍(Dynamic Programming) 2020. 11. 29. 22:17
www.acmicpc.net/problem/2091 2091번: 동전 첫째 줄에 다섯 정수 X(1 ≤ X ≤ 10,000), A, B, C, D(0 ≤ A, B, C, D ≤ 10,000)가 주어진다. www.acmicpc.net 문제풀이 X : 입력값(목표 금액) coin : 1, 5, 10, 25 센트 동전 갯수 (입력값) ans : X원 일때 최대 사용한 1, 5, 10, 25 센트 동전 갯수 check : check[i] = x i원을 만들기 위해 최대로 사용한 동전의 갯수 x개 used : 특정 money원을 만들기 위해 사용한 1, 5, 10, 25 센트 동전의 갯수 x : X원을 만들기 위해 필요한 최소 1센트 갯수 dfs(money, cnt) : 가능한 모든 경우를 확인해보기 위한 재귀 함..
-
[백준 14889] 스타트와 링크 (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2020. 11. 29. 16:43
www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제풀이 N, board : 입력값 check : 두 개의 팀을 나누기 위한 bool 순열 tmp : 순열의 마지막까지 도달했는지 확인하기 위한 check의 마지막 순열 ans : 결과값(두 팀의 능력치 차이의 최솟값) next_permutation(a) : 특정 순열의 다음 순열을 구하는 함수 단순히 bool 순열을 구하기만 하면 풀 수 있는 문제이다. python itertools의 permutation을 쓰면 시간이 좀 더 빠..
-
[백준 14502] 연구소 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2020. 11. 28. 19:58
www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 N, M, board : 입력값 virus : 바이러스 좌표 (x, y) ans : 결과값(최대 빈 공간) tmp_board : 원본 board를 훼손하지 않기 위해 복사 q : 바이러스 bfs를 위한 deque bfs(board, virus) : 바이러스를 퍼트리기 위해 bfs로 탐색 다소 비효율적이긴 하지만 6중 for문을 통해 3개의 벽을 세우는 것을 구현하였다. 1. 3개의 서로 다른 벽 세우기 구현 6중..
-
[백준 12100] 2048 (Easy) (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2020. 11. 24. 12:00
www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 풀이 N, board : 입력값 p: 행이나 열에서 블록이 이동하게 될 가장 끝의 위치 x: 이전 블록이 새로운 블록과 합쳐지는것을 표현 => 이전 블록을 저장하고 있는 변수 move_up(board) : 블록을 상단으로 이동 move_down(board) : 블록을 하단으로 이동 move_right(board) : 블록을 우측으로 이동 move_left(board) : 블록을..
-
[백준 15684] 사다리 조작 (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2020. 11. 24. 00:45
www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제풀이 N, M, H : 입력값(세로선의 개수, 가로선의 개수, 가로선을 놓을 수 있는 위치) board : 특정 지점 방문 여부 체크 ans : 가로선을 놓은 최소 개수(결과값) check() : i번 세로선이 i번으로 잘 도착하였는지 확인하는 함수 dfs(cnt, x, y) : 재귀적으로 가로선을 놓을 수 있는 곳에 다 놓는 함수, cnt - 현재까지 가로선을 놓은 개수, x - 행, y - 열 골드 5..
-
[백준 2886] 자리 전쟁 (Python)Algorithm & Problem Solving/구현(Implementation) 2020. 11. 23. 21:31
www.acmicpc.net/problem/2886 2886번: 자리 전쟁 R x C의 형태를 지닌 전차 안에는 의자와 사람들의 정보들이 주어진다. 사람들은 다리가 아픈 것을 매우 싫어하기 때문에 빈 의자가 보이면 무조건 앉으려고 한다. 하지만 나보다 의자에 가까이 www.acmicpc.net 문제풀이 R, C : 초기 입력 행, 열 board : 입력 값 chair : 의자 좌표(x, y)를 가지고 있는 리스트 people : 사람 좌표(x, y)를 가지고 있는 리스트 seated : 의자 인덱스 번호에 따른 의자 방문 횟수를 저장하는 리스트 finished : 사람 인덱스 번호에 따라 의자를 방문했는지 안했는지 판단하는 bool 리스트 # seated와 finished 는 문제조건 (1