Algorithm & Problem Solving
-
[백준 13460] 구슬 탈출 2 (Python)Algorithm & Problem Solving/삼성 기출 2022. 5. 3. 22:26
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제풀이 BFS로 해결할 수 있는데, 이때 전형적으로 2차원 배열로 탐색하는 것이 아니라 4차원 배열로 탐색해야 한다. (빨강구슬 x, y 파란구슬 x, y) 1. 큐에 (빨강구슬 x, 빨강구슬 y, 파랑구슬 x, 파랑구슬 y) 추가 2. BFS 를 통해 아직 탐색하지 않은 영역 탐색 - 벽이나 구멍을 만날 때 까지 특정 방향으로 계속 이동 (mo..
-
[백준 1918] 후위 표기식 (Python) (중위 표기식 -> 후위 표기식 변환 문제)Algorithm & Problem Solving/자료구조(Data Structure) 2021. 10. 3. 15:57
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 문제풀이 cmd : 입력값 stack : 괄호와 연산자를 저장할 stack list ans : 결과 list 스택을 이용해서 연산자의 우선순위를 결정해 결과 list에 넣는 방식으로 해결하였다. 1. A~Z 알파벳일 경우 ans에 바로 추가한다. 2. '(', '+', '-'. '*', '/' 연산자일 경우 stack에 추가한다. - '*' 나 '/' 일 경우, 연산자 우선순위에 의해서 ..
-
[백준 15683] 감시 (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2021. 2. 14. 19:37
www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제풀이 N, M, board : 입력값 cctv, cctv_n : CCTV 좌표 리스트, CCTV 개수 ans : 최소 사각지대 개수 check : 방문 여부 확인 재귀를 이용해 모든 CCTV를 4방향 돌리면서 감시 가능 영역을 만들어보는 브루트포스 방식으로 해결할 수 있다. 1. CCTV 좌표 및 개수 세주기 2. 재귀를 이용해 모든 CCTV의 감시 영역 탐색하기 - CCTV 종류에 따라서 방향 ..
-
[백준 1461] 도서관 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 2. 10. 16:18
www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net 문제풀이 N, M, arr : 입력값 negative, positive : 음수, 양수 리스트 distance : 책의 원래 위치까지 가야하는 최소 걸음 수 리스트 음수와 양수를 나누고, 절대값이 큰 것부터 M개씩 나눈 후, 그 중 절대값이 가장 큰 수 만큼 움직이면 된다. 가장 절대값이 큰 거리의 경우는 돌아오지 않아야 하는 예외를 처리해주어야 한다. 1. 음수, 양수로 나누기 - 절대값이 큰..
-
[백준 1194] 달이 차오른다, 가자. (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 2. 10. 13:53
www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제풀이 N, M, board : 입력값 check : 특정 key를 가지고 방문 여부 체크 비트마스크를 이용한 BFS 문제였다. 평상시 비트마스크를 싫어하였는데 이 문제를 통해 조금은 친해(?)진 것 같다... 비트마스크를 활용한 풀이에 대한 설명은 아래 참고한 코드 URL 에 자세히 설명되어 있다. 1. '0' 부터 BFS 탐색 - 새롭게 이동할 곳이 '1' 이거나 '.' 이면..
-
[백준 19639] 배틀로얄 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 2. 5. 20:59
www.acmicpc.net/problem/19639 19639번: 배틀로얄 첫 번째 줄에 X, Y, M (0 ≤ X, Y ≤ 100,000, 2 ≤ M ≤ 100,000)이 주어진다. M은 짝수다. 다음 X개의 줄에는 i번째 사람과 싸웠을 때 잃게 되는 체력이 주어진다. 이 수는 0 이상 M / 2 이하의 정수이다. www.acmicpc.net 문제풀이 X, Y, M : 입력값 damage : 싸웠을 때 잃게 되는 체력 heal : 아이템을 먹었을 때 얻게 되는 체력 max_M : 초기 M 현재 체력(M) 이 초기 M (max_M) // 2 이하일 경우 포션을 먹고, max_M // 2 초과일 경우 적들과 싸우는 방식의 그리디 알고리즘으로 해결할 수 있다. 1. 현재 M 값 확인하기 - M max_M ..
-
[백준 4889] 안정적인 문자열 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 2. 5. 02:11
www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 문제풀이 stack을 이용해 안정적이지 않은 경우 ans를 증가하는 방식으로 해결할 수 있다. 1. 현재 문자가 '{' 이면 stack에 append하기 2. 현재 문자가 '}' 이면 stack 에서 pop하기 - stack 이 비어있을 경우 안정적이지 않은 경우이므로 ans 증가 - 이 경우 안정적이지 않은 '}' 를 바꿔줘야 하므로 '{'를 stack에 append 3. stack 이 남아있을 경우, s..
-
[백준 2258] 정육점 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 2. 4. 16:54
www.acmicpc.net/problem/2258 2258번: 정육점 첫째 줄에 두 정수 N(1≤N≤100,000), M(1≤M≤2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 www.acmicpc.net 문제풀이 N, M : 입력값 arr : (가격, 무게) 리스트 weight : 현재까지의 무게 same : 가격이 동일한 고기일 경우, 해당 가격만큼 결과에 더해주기 위한 변수 실버1 문제인데, 생각보다 많이 까다로운 그리디 알고리즘 문제였다. 처음에 우선순위 큐를 이용해 해결하려 하였는데, 계속 틀렸습니다를 받아서 결국 정답코드를 참고하였다. 생각보다 단순하게 생각하면 쉽게 해결할..