. '프로그래밍 공부/백뚠' 카테고리의 글 목록
본문 바로가기

프로그래밍 공부/백뚠18

신입사원 장그래는 정규직이 될 수 없다 (백준 1946 : 신입사원) 몇 년전에 우리네의 회사 생활을 대변해주고 위로해주는 미생이라는 드라마가 세간의 화제가 되었던 적이 있었다. 나는 웹툰으로밖에 안봤지만, 당시 신입사원이었던 나에게 많은 공감이 되었고 신입사원으로서의 마음가짐을 심게해 준 미생이었는데. 신입사원 장그래는 결국에는 정규직이 되지 못하였지만 (스포인가?) 사실 청년실업자가 넘쳐나는 이 시대에는 비정규직 장그래조차 되기힘든게 현실아니겠는가 (백수가 되어버린 나를 포함하여 ㅠㅡㅠ) 그런데 심지어 이번 문제에서는 우리는 인사담당자가 되어서 실날같은 희망을 가지고 지원한 수 많은 청년들을 떨어뜨려야한다. 하지만 어쩌겠는가. 취직이 잘 되는 사회를 만들던가! (속이 뻥) 어쩔수 없다. 눈물을 머금고 칼춤을 춰 손에 피를 묻히자. 인사 담당자도 그저 한낱 월급쟁이에 불.. 2021. 1. 3.
누가 내 치즈를 옮겼을까? (백준 2638: 치즈) 2638번: 치즈 (acmicpc.net) 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 톰과 제리같은 만화를 보면 항상 치즈는 샛노란 색깔에 치즈케이크같은 모양에 구멍이 송송 뚫려있는 모양으로 나왔다. 그걸 보고있으면 참 맛있어 보였는데, 우리가 흔히 먹는 치즈는 네모나고 얇은 치즈였다. 한번은 위 사진같은 치즈를 먹은 적이 있었는데.... 솔직히 맛은 기억 안난다. 그냥 평범했나보다. 푸른곰팡이 치즈였나 그거는 먹은 적이 있었는데, 겉보기로 음식을 판단하는 나이기 때문에 한입먹는 것이 되게 힘들.. 2020. 12. 30.
토이스토리 (백준 2637 : 장난감 조립) 2637번: 장난감조립 (acmicpc.net) 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 이 문제를 보면서 프라모델이 생각났다. 작은 부품들로 중간 부품을 만들고, 중간 부품들로 큰 부품을 만들고, 큰 부품을 조립하여 완성시킨다. 정말 기본 부품의 경우, 중간 부품 하나를 만들기 위해 작은 부품을 모두 떼놨다가 잃어버려서 제대로 못만드는 경우도 있어서 곤혹스러웠던 기억이 있다. 그러니 프라모델만들 때에는 딱 필요한 부품만 뗀 뒤에 작업을 진행하도록 하자. 그러고보니 프라모델 안.. 2020. 12. 29.
따봉도치는 고마워! (백준 3055:탈출) 3055번: 탈출 (acmicpc.net) 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 여러분들은 인터넷하면서 많은 낚시글을 본적이 있을 것이다. (본적없다면 당신은 상당히 건실한 삶을 살았다는 것이다. 자랑스러워해도 된다.) 이런 고전짤로부터 시작해서 소중한 머리카락으로 협박하는 놈도 있었고 같은 대 인공지능 시대에 걸맞는 낚시글도 있었고, 최근에 유행했던 킹치만이나 가슴이 웅장해지는 구미호놈까지 인터넷이 존재하는 한, 낚시글은 끊이지 않을 것이다. 물론 인터넷보면서 이런 식의 낚시글을 본게 한두개가 아니지만 (자라.. 2020. 12. 29.
미노타우르스와 함께 춤을 (백준 2178:미로탐색) 2178번: 미로 탐색 (acmicpc.net) 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 시간에는 BFS 탐색을 공부해보도록 한다. 미로 탐색 문제는 BFS 탐색의 기본을 닦을 수 있는 좋은 문제이다. 즉, 어떤 맵이 있어서 1이 통로이고, 0이 벽이다. 여기서 미로를 탐색할 수 있는 최단거리를 찾는 문제이다. 이게 또 미로라고 하니 옛날에 화면보호기라는게 있던 게 기억이 난다. 요즘은 화면보호기라는 말 자체가 안들리지만, 옛날에는 모니터의 수명이 짧았는데, 한 화면만 계속 틀고 있으면 해당 색의 화소가 타버려서 모니터가 금방 .. 2020. 12. 29.
몸에도 좋고 맛도 좋은 (백준 3190 : 뱀) 3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 라떼에는 도트로 된 게임기가 있었는데, 거기에 항상 뱀 게임이 있었다. (테트리스, ㅗ 모양으로 된 자동차 게임, 핑퐁 게임도 같이 있었다... 기억나는 사람 있는가? 내 또래는 알거야...) 그 뱀 게임을 이제 만들어 볼 시간이다. 일단 입력부터 받아보자. import sys from collections import deque sys.stdin = open("input.txt", "r") # 보드의 크기 N N = int(s.. 2020. 12. 22.
땅! 땅! 땅! 빵! (백준 8983 : 사냥꾼) 8983번: 사냥꾼 (acmicpc.net) 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 많은 고민을 했던 문제이다. 처음에는 동물들의 좌표를 x축으로 정렬하고 각 x좌표마다 사거리를 계산해서 그 사거리 안에 있는 동물들을 탐색해봤는데, 아무리 시간을 좁혀봐도 시간초과가 났다. 그런데, 내 생각에 맹점이 있었다. 좌표값은 10억이기 때문에 x축을 기준으로 사거리를 계산하는 것은 엄청난 시간이 걸리는 반면, 동물의 수는 10만에 불과하다. (최댓값 기.. 2020. 12. 21.
레이저 타워 디펜스 (백준 2493 : 탑) 2493번: 탑 (acmicpc.net) 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제를 보는 순간, 완전탐색으로 풀면 되겠네! 했지만, 고르든 등급의 백준 문제는 그런 추잡한 시도는 용납하지 않는다. 그럼 어떤 식으로 풀어야 할까. - 대전략: 탑 높이 리스트는 tower로 저장하고, 우선 체크리스트( check = [] ) 를 만들자. 또한, tower에 대해 for i in range(N)으로 왼쪽부터 ptr(포인터)가 시작하도록 하자. 또한, ptr 시작은 0 으로 하자. 왜 why. 문제를 .. 2020. 12. 21.
색종이를 곱게 접어서 (백준 2630:색종이 만들기) 2630번: 색종이 만들기 (acmicpc.net) 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 딱 봐도 Z랑 비슷하지 않는가? 배열 안의 1을 카운트해서 1의 갯수가 N x N이 아닌경우, 4분할을 하여 다시 1을 카운트 해보고 아니면 다시 4분할 하는 식으로 가자. 우선 입력값을 받고, 재귀함수의 기본꼴을 만들자. 일단 해당 색종이의 현재 좌표를 알아야하기 때문에 x, y를 넣어준다. N = int(sys.stdin.readline()) paper = [list(map(int.. 2020. 12. 18.
섞고 섞고 돌리고 섞고 (백준 2470 : 두 용액) 2470번: 두 용액 (acmicpc.net) 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net - 대전략: 요소를 오른차순으로 나열하고, 제일 작은 것은 min, 큰 것을 max로 하자. (min과 max는 인덱스 값이다.) 그리고 두개를 더했을 때, 음수면은 min을 한칸 위로 옮기고 양수면 max를 한칸 밑으로 내린다. min과 max를 더한 절대값 ( abs(sol[min] + sol[max]))이 제일 낮았을 때, min과 max을 저장하고, 양 합의 절댓값이 더 낮은.. 2020. 12. 18.
아~ 와이파이 잘되는 집을 찾으시는구나? (백준 2110 : 공유기 설치) 2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net N : 집 갯수, C : 공유기 갯수 우선, 집 좌표를 받아서 sort하자 N, C = map(int,sys.stdin.readline().split()) house = [int(sys.stdin.readline()) for _ in range(N)] house.sort() 딱봐도 맨 처음과 맨 끝 좌표에는 좌표기를 설치해야될 것 같지 않는가. (반례가 있나? .. 2020. 12. 18.
나무를 자르다니 나무해 (백준 2805:나무자르기) 2805번: 나무 자르기 (acmicpc.net) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 나무의 수 : N 원하는 나무의 길이 : M 상근이가 환경에 관심이 많기 때문에 최소한의 나무만 자르고 싶다고 한다. 정말 기특하지 아니할 수 없다. 상근이를 위해서 열심히 풀어보자. - 대전략 항상 수능을 공부할 때 들었던 말이 있다. "출제자의 의도를 파악하라." 다행히도 백준의 출제자의 의도는 알고리즘 분류에 나타나있다. 이 문제의 알고리즘 분류는 이분 탐색이다. 이분.. 2020. 12. 18.
야구는 9회말 2아웃부터 (백준2053:숫자야구) 2503번: 숫자 야구 (acmicpc.net) 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 어렸을 적에 많이 했던 숫자 야구이다. 그래도 나름 잘했던 게임이라 생각하는데 이런식으로 뒤통수맞을 줄이야. - 대전략 : 생각하고 있을 답의 총 개수라면, 결국 경우의 수를 전부 뽑아내어 간추릴 수 밖에 없다. 첫번째 대답에서 1스트라이크 1볼이라고 했으니, 1개는 자릿수와 숫자가 맞고, 1개는 자릿수가 맞고, 1개는 틀렸을 경우의 수를 전부 뽑아낸 뒤, 뒤의 조건에 대입하여 소거시킬 수 밖에 없다. 일단, 입력.. 2020. 12. 17.
아래로부터의 혁명 (백준 9095 : 1, 2, 3 더하기) 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net - 대전략 : 예를 들어 입력값이 5(N)라고 하자. 일단 1부터 올라가야 할 것이다. 그러면 [1 1 1 1 1]이 될 것이고 이 조합의 수는 1개이다. 그다음은 1 2개를 합쳐서 [2 1 1 1]을 만들고 이 조합의 수는 4! (요소의 갯수) / 3! (중복된 숫자의 갯수) 가 된다. 리스트 안의 1, 2, 3의 갯수를 리스트화 하자. arr = [a b c]에서, a는 3의 갯수, b는 2의 갯수, c는 1의 갯수가 된다. 즉, [1 1 1 1 1] 은 arr=[0 0 5] 가 되고, [2 2 1.. 2020. 12. 17.

티스토리툴바