Problem Solving
백준 - 1744: 수 묶기 - Greedy
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 세 가지 경우로 나누어 리스트에 저장을 했습니다. 1. 1을 제외한 양의 정수 2. 1 3. 0과 음의 정수 그런 후에 1번은 내림차순으로 정렬을 한 뒤 앞에서 부터 묶어주었고, 3번은 오름차순으로 정렬을 한 뒤 앞에서부터 묶어주었습니다. 2번은 1의 개수만큼 값을 더해주었습니다. 1번에서 1을 제외한 이유는 1은 곱하는 것보다 더해주는 것이 값을 더 증가시켜주기 때문입니다. 3번에서 0과 음의..
백준 - 2847: 게임을 만든 동준이 - Greedy
https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 뒤에서 부터 보면서 만약 다음 수가 현재 수보다 크다면, 현재 수보다 1 작은 값으로 만들어주면 됩니다. 1 작은 값으로 만들어야 점수를 낮추는 횟수를 최소화 할 수 있습니다. 문제 조건에서 항상 답이 존재하는 경우만 주어지기 때문에 1보다 작아지는 경우는 생각하지 않아도 됩니다. from sys import stdin input = stdin.readline n = int(input()) sc..
백준 11967: 불 켜기 - BFS
현재 방에서 스위치를 통해 불을 킨 후, 인접해 있는 방 중 불이 켜져있는 방에 들어가 스위치를 키게 끔 하였습니다. 이 것을 한 주기라고 보고, 한 주기에서 불을 킨 적이 있다면, 다시 1,1 부터 새롭게 들어갈 수 있는 방을 확인하게끔 하였습니다. 한 번 불을 켰다면 다시는 불을 키지 않아도 되게끔 'swithced_turned'라는 변수로 체크해 두었고, 이는 초기화 되지 않습니다. 새롭게 불이켜진 방이 있고, 그 방은 현재 이동 가능한 방과 인접해 있어 이동할 수 있는 경우가 될 수 있습니다. 따라서 매 주기마다 계속 이전에 와 봤던 방이라도 확인을 해주어야 하기 때문에 'visited'는 주기마다 초기화를 해주었습니다. 불을 켤 때 마다 count를 해주고, 주기가 끝날 때마다 'total_co..
백준 3197: 백조의 호수 - BFS
https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net python3로 돌릴 경우 시간초과가 나기 때문에 pypy3로 제출하였습니다. 이 문제는 아무 생각 없이 BFS를 돌리게 되면 시간 초과가 납니다. 우선 백조가 만나는 지 체크하는 것과, 물을 녹이는 것을 한 주기라고 생각합니다. queue를 몇 개 더 추가하여, 물을 녹이기 전 백조가 만나는 지 체크하고, 만나지 않는 다면 물을 녹이는 일을 하 되, 다음 주기 때의 ..
백준 2636: 치즈 - BFS
https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net (0, 0)를 시작으로 bfs를 돌리면서 0을 만나면 queue에 넣고 가장자리에 있는 치즈를 만나면 0으로 바꾼 뒤 queue에는 넣지 않으면 가장자리에 있는 치즈만 녹이는 것이 가능합니다. (visited는 모두 체크) bfs를 돌면서 가장자리의 치즈를 만나면 count를 해주고 완료 후에는 count를 return해주어 마지막에 모든 치즈가 녹기 전에 몇 개가 있었는지 알 수 있습니다. from sys impo..
백준 1062: 가르침 - 비트마스크, 조합
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 조합과 비트마스크로 풀 수 있는 문제입니다. 모든 단어들은 'anta'로 시작하고 'tica'로 끝나므로 'a c i n t' 이 5개는 꼭 배워야합니다. 만약 k가 5보다 작다면 'a c i n t'를 모두 배울 수 없으므로 답은 0이 됩니다. k가 5보다 크다면 'anta'와 'tica' 사이의 단어들을 추출한 뒤 'a c i n t'를 제거해줍니다. 그 후, 비트마스크로 풀기 위해 '..
백준 1922: 네트워크 연결 - 크루스칼, 유니온 파인드
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 간단한 크루스칼 문제입니다. 컴퓨터를 연결하는데 필요한 비용을 기준으로 정렬을 한 뒤에 유니온파인드 알고리즘을 통해 크루스칼로 풀면 됩니다. from sys import stdin, setrecursionlimit input = stdin.readline setrecursionlimit(10**6) def get_parent(parent, node): if parent[node] == node: return node parent[node] = get_parent(parent, paren..
프로그래머스 동굴 탐험 - BFS, 위상정렬
https://programmers.co.kr/learn/courses/30/lessons/67260 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr 2020 카카오 인턴쉽 문제입니다. 위상 정렬을 모르고 풀었을 때는 도저히 감이 안왔었는데, 위상 정렬을 한 번 공부하고 나니 그렇게 어렵지 않..
백준 2252번: 줄세우기 - 위상정렬
https://www.acmicpc.net/problem/2252 위상정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘입니다. 예를 들어 A의 작업보다 B의 작업이 먼저 처리 되어야하고, C의 작업이 A의 작업보다 먼저 처리 되어야 한다면 C - A - B 의 순서대로 일을 처리해야 할 것입니다. A의 작업보다 B의 작업이 먼저 처리 되어야하고, C의 작업도 B의 작업보다 먼저 처리 되어야 한다면 A - C - B 도 되고, C - A - B 도 됩니다. 그래서 위상정렬 특성상 별 다른 조건이 없을 경우 여러 답이 나올 수 있습니다. 이제 위에서 얘기한 "작업"을 학생들의 "키"로 생각해보겠습니다. 학생 A의 키가 B보다 크고, C의 키가 A보다 크다는..