기로에 서다

문제 www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 풀이 1. 조는 친구들을 우선 체크한 후, 출석 번호를 받은 친구들의 배수마다 출석했다고 체크를 하는데 조는 친구들은 무시하고 넘어가면 됩니다. 2. 이 때 구간질의마다 학생 수를 세면 시간초과가 나기 때문에 미리 누적합 배열을 저장해놓고, [s, e] 구간의 합에 대해psum[e] - psum[s - 1]을 출력하면 해결할 수 있습니다. 코드 #include ..

문제 www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 풀이 1. W가 소문자 알파벳으로만 이루어졌으므로 문자열 내에서 알파벳들의 위치를 담는 알파벳 벡터를 만들어 각각의 위치들을 담아줍니다. 2. 알파벳 벡터를 순회하며 크기가 K이상인 것들에 대해서 시작 인덱스를 st라 하면 끝은 st + k - 1까지 원소들을 K개씩 검사합니다. 3. 이 때 문제에서 요구하는 정확히 K개 문자를 포함하는 연속 문자열은 결국 w를 구성하는 연속 문자열[st, st + k..

문제 www.acmicpc.net/problem/20436 20436번: ZOAC 3 첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다. 그 다음 줄에는 알파벳 소문자로 구성된 문자열이 주어진다. 문자열의 www.acmicpc.net 풀이 1. 각기 다른 자판의 위치를 좌표로 저장하고 왼쪽 손이 닿을 수 있는 위치, 오른쪽 손이 닿을 수 있는 위치를 구분하여 손의 위치와 자판의 거리만큼 더해가면서 해결할 수 있습니다. 2. 거리와 상관없이 문자를 누르는 횟수는 문자열의 길이와 같습니다. 따라서 답은 거리의 합에 문자열의 길이를 더해준 것입니다. 코드 #include using namespace std; typedef pair..

문제 www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 1. 파이프의 가능한 경로를 찾기위해서 위부터 아래로 진행방향을 고정하고 끝점까지 도착 할 수 있는지의 여부를 체크하는 dfs를 진행합니다. 2. 위의 그림에서 파이프의 경로가 되는 빨간점에서 파란점들로 가는 상황에 대해서 생각해보면 아래와 같은 결론을 낼 수 있습니다. 1번 빨간점이 다음 열로 이동할 때 1번 파란점이아닌 2번 파란점으로 이동한다면 2번 빨간점이 이동할 수 없습니다. 따라서 윗점에서 파이프의 경로가..

1.객체 지향 특징 기본적이지만 추상화, 캡슐화, 상속, 다형성을 가지고 있음.컴포넌트를 쉽고 유연하게 변경하면서 개발할 수 있는 방법2.역할과 구현을 분리그 장점은 ?클라이언트는 대상의 역할(인터페이스)만 알면 된다. 클라이언트는 구현 대상에 대해서 크게 신경쓰지 않아도 된다.따라서 인터페이스를 안정적으로 잘 설계하는 것이 중요하다 객체 설계시 ?객체 설계시 역할(인터페이스)를 먼저 부여하고, 그 역할을 수행하는 구현 객체 만들기 3. 자바 언어의 다형성오버라이딩을 생각~헷갈리는 오버로딩과 오버라이딩은 전혀 다른개념이다.오버로딩은 같은 이름의 메소드를 매개변수의 타입, 개수에 따라 재정의하는 것오버라이딩은 상위 클래스의 메소드를 하위 클래스의 메소드에서 재정의하는 것

Inflearn lecture 를 공부하며 기록

문제 www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 풀이 1. 간단하게 생각해본다면 시작 점에서부터 BFS를 돌려 "왼쪽 위 점에서부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 확인하며 진행하면 될 것 같지만 $O(n*m*h*w)$로 시간 초과가 납니다. 2. "해당 점에서 부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 연산하며 중복된 칸을 계속 탐색하므로 이를 막기 위해 dp를 사용합니다. 이때 상태 정의는 "dp[i]..

문제 www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 1. 구해야 하는 것은 벌레가 [1, h] 높이를 지나갈 때, ① 부서지는 석순의 개수의 최소 값과 ② 그러한 개수를 만족하는 높이의 개수를 구해야 합니다. 2. ②번부터 생각해본다면, 높이를 지날 때마다 부서지는 석순의 개수를 인덱스로 갖고 그러한 높이들의 개수를 값으로 갖는 맵(stl)을 사용하면 첫 번째 원소 값 기준으로 오름차순 정렬된 채로 유지되기에 결과적으로 답은 맵의 첫 번째 원소의 인덱스(..

문제 www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 풀이 i번째 비행기가 들어왔을 때 [1, g_i]게이트 중 어디에 도킹시킬지를 정해줘야 하는데 이는 아래와 같은 예를 떠올려보면 어렵지않게 큰 번호의 게이트부터 채워나가야함을 알 수 있습니다. ※ [1, 2, 3]의 게이트가 꽉 찼을 때, g = [5, 4]라면 1번째 비행기를 4번게이트에 두면 2번째 비행기가 도킹x, 반대로 5번게이트에 도킹하면 2번째 비행기가 도킹가능..

문제 www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 풀이 모든 전구의 상태를 완전탐색한다면 $O(2^n)$으로 시간초과가 나기 때문에 다른 방법을 생각해봐야 합니다. 문제에서 구하는건 최소한으로 누르는 스위치의 개수이기에 스위치를 누르는 횟수를 줄이기 위해서 같은 스위치를 2번이상 누르지 않도록 해야합니다. 1. 스위치를 누르는 방향을 정해놓고 전구를 순회하면 한 번 누른 스위치는 다시 누르는 경우가 생기지 않으므로 방향을 정해놓고 진행합니다. ..