![]()
문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... ...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... ..XXXXX..XXXXXX....
![]()
문제 크기가 1 ×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 아래 그림은 H = 8, W = 7인 경우이고, 빈칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다. 7 . . . . . . . 7 . . . . . . . 6 . . . . . ..
![]()
문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 🔎문제 해석 원숭이의 동작수의 최소값을 구해야 하므로, BFS 알고리즘을 이용해서 출발지부터 도착지점까지 갈 수 있는지를 판단해야 합니다. 문제는 간단합니다. queue를 이용해서 좌표와 말처럼 이동한 횟수를 계속해서 기록해 둡니다. 만약 말처럼 이동한 횟수가 k-1 이하라면 말처럼 이동할 수 있습니다. 하지만 k이상이라면 말처럼 이동할 수 없습니다. 즉 queue에서 기록한..
![]()
1장에서는 주로 아래의 내용을 다룹니다. What is the Internet? What is a protocol? Network edge : hosts, access network, physical media Network core : packet/circuit swithcing, internet structure Performance : loss, delay, throughput Sequrity Protocal layers, service models History 이번 글에서는 인터넷과 프로토콜에 대해서 다룰 예정입니다. 우선 인터넷의 사전적 정의는 아래와 같습니다. 인터넷은 컴퓨터와 컴퓨터 네트워크를 이용하여 전 세계적으로 정보를 교환할 수 있는 컴퓨터 네트워크입니다. 인터넷은 웹, 이메일, 파일..
![]()
문제 N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다. 모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다. 놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M..
![]()
🔎문제 해석 N의 크기가 최대 200,000이므로, O(N^2)인 알고리즘은 사용하면 안 된다. 따라서 모든 수열의 경우의 수를 탐색해야 하는 이 문제는 투 포인터 알고리즘을 사용해서 O(N) 알고리즘으로 풀어야 합니다. 우선 다른 투 포인터 알고리즘 문제와 동일하게 start, end를 사용합니다. 우선 start와 end를 0으로 초기화해줍니다. 그다음 숫자가 해당 부분수열에서 몇 번 포함되었는지를 기록하는 배열도 필요합니다. N의 최대크기는 200,000이고, N의 최댓값은 100,000이므로 배열의 최대 크기는 100,001이 될 것입니다. V [100001]; end가 n이 되기 전까지 해당 과정을 반복합니다. end가 가리키는 원소가 등장하는 횟수를 비교해 줍니다. k개 이하라면, 등장하는 횟..
![]()
문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/172927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 설명 곡괭이의 종류는 3개이고, 광물의 종류는 3개입니다. 곡괭이 하나로 광물을 5개 캘 수 있고, 5개를 연속으로 캐며, 5개를 캐면 다시는 사용하지 못합니다. 곡괭이로 광물을 캘 때, 광물에 따라 피로도가 다릅니다. 다이아 곡괭이 -> 모두 피로도가 1 철 곡괭이 -> 다이아 = 5, 나머지 =1 돌 곡괭이 -> 다이아 = 25, 철 = 5, 돌 = 1 종료조건은 모든 곡괭이를 ..
![]()
알고리즘 스터디를 하다가 새로운 알고리즘을 발견해서 호다닥 공부해서 정리하는 "아주 주관적인" 글입니다. 🔎투 포인터 알고리즘을 쓰는 이유 완전 탐색을 할 경우 시간초과를 피하기 위해서 쓰는 방법이다. 예를 들어서 N칸의 1차원 배열이 있을 때, 모든 경우의 수를 다 테스트 하면 O(N^2)이 된다. 입력인 N의 최대 범위가 너무 크다면 시간초과를 피 할수 없을 것이다. 이럴 때 사용하는 알고리즘이 투 포인터 알고리즘이다. 우선 해당 알고리즘은 포인터 포인터 2개를 사용한다. 2개의 포인터는 start, end, left, right 와 같은 배열의 시작과 끝을 의미하는 두개의 포인터를 사용한다는 뜻이다. 저는 포인터 2개를 start와 end로 사용하겠습니다. start와 end의 초기값은 모두 0이며..
