티스토리

컴공의 노예생활

검색하기

블로그 홈

컴공의 노예생활

hddcp.tistory.com/m

창업 당해버린 대학생의 공부일기

구독자: 0

방명록 방문하기

주요 글 목록

[백준] 14287 - 내리 갈굼 3 https://www.acmicpc.net/problem/14287 14287번: 내리 갈굼 3 영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다. 이러한 내리 갈굼은 회사에 가장 큰 불만 사항이 되었고, 사장 영선이는 이 불만을 해소해주기 위하여, 단 하루만 야자타임식으로 하여, 반대로 부하가 상사를 갈구면, 그 위로 쭉 사장까지 모두 갈굼을 당한다. 갈굼의 대한 정보는 실시간으로 주어진 www.acmicpc.net 내리 갈굼 2 문제에서 거꾸로 부하가 상사를 갈구는 문제. 상사가 받은 갈굼 정도는 부하들이 받은 내리갈굼의 합과 같다. 전위순.. 공감수 0 댓글수 0 2019. 12. 19.
[백준] 2820 - 자동차 공장 https://www.acmicpc.net/problem/2820 2820번: 자동차 공장 문제 상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. (상근이는 모든 사람의 상사이다) 상근이의 번호는 1번이고, 나머지 직원의 번호는 2부터 N이다. 모든 직원은 자신의 모든 부하 직원(직속 부하와 부하의 부하등등을 모두 포함)의 월급을 인상하거나 삭감할 수 있다. 상근이는 권력 남용을 막기 위해 직원의 월급을 www.acmicpc.net 구간합을 구하는 문제는 아니지만 트리에서 자식들의 갱신이 이루어지는 문제이므로 segment tree와 lazy propagation을.. 공감수 0 댓글수 0 2019. 12. 18.
[백준] 14268 - 내리 갈굼 2 https://www.acmicpc.net/problem/14268 14268번: 내리 갈굼 2 영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다. 갈굼에 대해 정도에 대한 수치가 주어지는데, 이 수치 또한 부하들에게 똑같이 갈궈진다. 이번에는 내리 갈굼이 실시간으로 일어날 것이다. 입력으로 아래와 같은 쿼리가 주어질 것이다. 1 i w : i번째 직원이 직속 상사로부터 w만큼 갈굼을 당한 www.acmicpc.net 앞선 내리 갈굼 문제에서 갱신 중간에 쿼리가 주어지는 문제이다. 내리 갈굼 문제의 알고리즘에서 dfs를 이용하여 해당 사원의 상.. 공감수 0 댓글수 0 2019. 12. 9.
[백준] 14267 - 내리갈굼 https://www.acmicpc.net/problem/14267 14267번: 내리 갈굼 영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다. 갈굼에 대해 정도에 대한 수치가 주어지는데, 이 수치 또한 부하들에게 똑같이 갈궈진다. 직속 상사와 직속 부하관계에 대해 주어지고, 갈굼에 대한 정보가 주어질 때, 각자 얼마의 갈굼을 당했는지 출력하시오, www.acmicpc.net 갈굼 수치를 입력받을 때, 바로 모든 수치를 전파하는 것은 비효율적이다. 모든 수치를 입력받은 후에, 해당 부모의 수치를 갱신하고 자식에게 전파하는 경우 불필요한 탐색과 .. 공감수 0 댓글수 0 2019. 12. 9.
[백준] 17822 - 원판 돌리기 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1) (1, j)는 ( www.acmicpc.net 회전 시의 인덱스 변화를 잘 신경쓴다면 어렵지 않은 구현 문제.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.. 공감수 0 댓글수 0 2019. 12. 2.
[백준] 2357 - 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 www.acmicpc.net Segment Tree를 이용하여 시간을 단축할 수 있는 문제 아래의 페이지에 설명이 잘 정리되어 있다. https://www.ac.. 공감수 0 댓글수 0 2019. 11. 30.
[백준] 12766 - 지사 배정 https://www.acmicpc.net/problem/12766 12766번: 지사 배정 문제 Innovative Consumer Products Company (ICPC)는 비밀 프로젝트를 시작하려하고 있다. 이 프로젝트는 s개의 하위 프로젝트로 구성된다. 이 프로젝트에 관련된 b(≥s)개의 ICPC의 지사들이 있고, ICPC는 각 지사에 하위 프로젝트들 중 하나를 맡기고자 한다. 다시 말하자면, 지사들은 s개의 분리된 그룹으로 나누어지고, 각 그룹이 한 하위 프로젝트를 맡게 된다. 각 달의 마지막에, 각 지사는 그 그룹에 있는 다른 모든 www.acmicpc.net b개의 지사를 s개의 프로젝트로 나누었을 때, 메시지 전달 비용의 최솟값을 구하는 문제이다. 교차로 i에서 j까지의 최단거리를 v[i.. 공감수 0 댓글수 0 2019. 11. 26.
[백준] 17142 - 연구소 3 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 시간 제한이 짧은 문제인만큼 시간 단축을 위한 아이디어를 떠올리는 것이 중요하다. 핵심 아이디어는 각각의 바이러스가 서로의 전파를 .. 공감수 0 댓글수 0 2019. 7. 28.
[백준] 17143 - 낚시왕 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 시뮬레이션 유형의 문제. python dict를 사용해서 상어의 삭제를 구현했다. 상어가 다른 상어를 잡아먹기 때문에, 동일한 칸에 위.. 공감수 0 댓글수 0 2019. 7. 25.
[백준] 16234 - 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 간단한 탐색 문제이고 queue를 이용한 dfs로 풀었다. 12345678910111213141516171819202122232425.. 공감수 0 댓글수 0 2019. 7. 23.
[백준] 15683 - 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 백준 문제집 중 '삼성 sw 역량 테스트 기출문제'에 포함된 문제 해당 문제집은 거의 대부분 Brute-Force 문제인 듯. 재귀를 이용.. 공감수 0 댓글수 0 2019. 7. 22.
[백준] 14889 - 스타트와 링크 https://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 brute-force 문제 재귀 함수를 이용하여 풀었다. pypy2를 이용하여 컴파일. python3 등을 사용하였으면 시간초과가 발생했을 것 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243import sys diff_min = float("INF")def make_team(n, stat, depth, team1_arr).. 공감수 0 댓글수 0 2019. 7. 17.
[백준] 14500 - 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net Brute Force 문제 다른 분들 풀이를 보면 본래 의도는 블록을 하나씩 붙여가며 dfs 하는 문제로 보입니다. (ㅜ 형태의 블.. 공감수 0 댓글수 0 2019. 7. 15.
[백준] 13460 - 구슬 탈출 2 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 브루트포스로 해결할 수 있는 문제 문제 자체는 간단하나 조건이 많아 구현 과정에서 실수가 발생할 확률이 높은 문제. 틀렸을 경우.. 공감수 0 댓글수 0 2019. 7. 13.
[백준] 14888 - 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 간단한 브루트 포스. 재귀 함수로 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include #.. 공감수 0 댓글수 0 2019. 7. 12.
[백준] 17144 - 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 알고리즘적으로는 간단한 구현 문제. 주의할 점이 있다면, 먼지 확산이 동시에 일어나기 때문에, 각 칸에 확산되는 먼지는 모든 .. 공감수 0 댓글수 0 2019. 7. 8.
[백준] 1064 - 평행사변형 https://www.acmicpc.net/problem/1064 1064번: 평행사변형 평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC) 이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나올 수도 있다. 만들어진 모든 사각형 중 가장 큰 둘레 길이와 가장 작은 둘레 길이의 차이를 출력하는 프로그램을 작성하시오. 만약 만들 수 있는 평행사변형이 없다면 -1을 출력한다. www.acmicpc.net 평행사변형이 존재하지 않는 경우를 먼저 계산해야 한다. 세 점이 동일한 직선 상에 있는 경우 평행사변형을 그릴 수 없으므로 a와 b, a와 c 사이의 기울기를 비교하면 된다. 이때, 나눗.. 공감수 1 댓글수 0 2019. 7. 3.
[백준] 15954 - 인형들 https://www.acmicpc.net/problem/15954 15954번: 인형들 첫 번째부터 세 번째까지의 인형을 선택하면 표준편차는 2/3의 양의 제곱근이 되고, 이 때 표준편차가 최소가 된다. 두 번째부터 네 번째까지의 인형을 선택하는 경우와, 세 번째부터 다섯 번째까지의 인형을 선택하는 경우에도 값은 같다. www.acmicpc.net 작년도 카카오 코드 페스티벌에 출제되었던 문제. 당시에 참가했을 때는 못풀었었다... 주어진 조건에서 편차의 최솟값을 구하는 문제이나 두 가지 유의할 점이 있다. 1. 소수의 정밀도 일반적인 c++ float, double, python의 float type을 사용하는 경우 부동 소수점 형의 오차로 인해 정답을 구하기 어렵다고 한다. 따라서 c++의 경우 l.. 공감수 0 댓글수 1 2019. 7. 2.
[백준] 1562 - 계단 수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 간단한 dynamic programming 문제이다. dp에 이용되는 숫자의 특징은 2가지다. 수의 마지막에 위치하는 숫자 현재까지 사용된 숫자 현재까지 사용된 숫자의 경우, bitmask를 사용하여 10진수로 변환한다. ex) 2, 4, 5 를 가짐 -> 0000110100(2) -> 52 위 두가지 특징을 가진 계단 수의 개수를 2차원 배열에 저장한다. n-1 길이의 계단 수들로부터 n 길이의 계단 수의 계단 수의 개수를 구한다. 배열을 전부 순회하며 해당 수의 가장 뒷자리에 올 수 있는 수를 추가한 뒤, 이를 n .. 공감수 0 댓글수 0 2019. 6. 30.
[백준] 3190 - 뱀 https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 간단한 구현 문제. 문제 내에 뱀의 이동, 길이 증가에 대한 알고리즘이 잘 설명되어 있어 그대로 구현하면 된다. n x n 배열에 사과를 1, .. 공감수 0 댓글수 0 2019. 6. 30.
[백준] 17140 - 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 단순한 연산 구현 문제. 상대적으로 속도가 느린 Python을 사용하였다. 시간제한을 맞추기 위해 몇가지 방법을 사용하였다. PyPy3로 제출 heapq, sys 모듈 사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43.. 공감수 0 댓글수 0 2019. 6. 29.
[백준] 1238 - 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때 www.acmicpc.net 간단한 플로이드-워셜 알고리즘 문제 https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%.. 공감수 0 댓글수 0 2019. 6. 28.
[백준] 13306 - 트리 https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 a가 주어진다 (1 ≤ a ≤ N). 다음 (N-1)+Q개의 줄 중에서 N-1개는 (1)의 형태로, Q개는 (2)의 형태로 주어진다. (1) 두 정수 x와 b가 주어진다(x = 0, 2 ≤ b ≤ N). 이것은 b의 www.acmicpc.net 일반적인 방법으로 UNION-FIND TREE 를 사용할 경우 edge 삭제 후 부모 갱신 과정에서 시간초과가 발생한다. 삭제된 edge.. 공감수 0 댓글수 0 2019. 6. 27.
[백준] 2805 - 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net INPUT의 개수가 1,000,000 개로 모든 높이에서 잘라 볼 경우 O(NM) 의 시간 복잡도가 소요되어 시간초과가 발생할 것이다.. 공감수 0 댓글수 0 2019. 6. 26.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.