분류 전체보기
백준 1700: 멀티탭 스케줄링 - 그리디
https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 사용할 전기용품을 플러그에 꽂기 전에 세 가지 경우를 생각해야합니다. 이미 꽂혀 있는 경우 멀티탭에 빈 공간이 있는 경우 멀티탭에 있는 것을 뽑고, 새로운 것을 꽂아야 할 경우 1번의 경우 그냥 넘어가주면되고, 2번의 경우는 꽂고 넘어가주면 됩니다. 3번의 경우는 제일 마지막에 사용되거나, 앞으로 사용하는 일이 없는 것을 찾아 바꿔줍니다. 플러그에 꽂힌 전기용품을 기준으로 for문을 돌면서 현재 ..
백준 1439: 뒤집기 - Greedy
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 처음에 stack에 1을 넣어주고, 문자열을 하나씩 보면서 값이 바뀌면 stack에 1을 추가합니다. ex) 001100111000 => [1, 1, 1, 1, 1] = [0그룹, 1그룹, 0그룹, 1그룹, 0그룹] 혹은 [1그룹, 0그룹, 1그룹, 0그룹, 1그룹] 값이 바뀌지 않았다면 모두 0이거나 1이기 때문에 뒤집어줄 필요가 없기 때문에 0을 출력합니다. 값이 바뀌었다면 stack 길이에서..
백준 - 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 카카오 인턴쉽 문제입니다. 위상 정렬을 모르고 풀었을 때는 도저히 감이 안왔었는데, 위상 정렬을 한 번 공부하고 나니 그렇게 어렵지 않..