2020 Kakao 여름 인턴십을 돌아보며 작성한 글입니다.

Link https://www.acmicpc.net/problem/17136 Note 10 x 10 의 판에 1 이 적힌 부분을 덮기 위해 필요한 색종이의 수를 구하여라. 삽질에 삽질에 삽질을 했던 문제. 타임아웃 문제를 해결해야 했던 문제도, 그리디로 처리해 오답이 나온 경우도 있었다. 타임아웃의 경우는 한 위치에서 5x5 색종이가 놓는게 가능하다 ...

Link https://www.acmicpc.net/problem/14500 Note 1x1 정사각형 4개로 이루어진 테트로미노를 n x m 크기의 종이에 최대한 배치 할 때, 테트로미노가 놓인 칸의 수의 합을 출력해준다. 일단 이 문제를 보았을 때 떠올린 방법은 나올 수 있는 모든 경우의 수를 배열에 넣어 배치하는 방법밖에 안떠올랐다. 이 후, 다른...

Link https://www.acmicpc.net/problem/1543 Note 영어로만 이루어진 문서가 주어질 때 검색하고 싶은 단어가 중복되지 않게 몇번 등장하는지 알아보자. 문제의 난이도에 비해 정답률이 낮은게 의문이었다. 아마 원인은 String 클래스의 find 함수나 indexOf 함수를 이용하며 생기는 검색 속도 문제일꺼 같다. 이번 ...

Link https://www.acmicpc.net/problem/1946 Note 한 지원자의 서류 심사 성적과, 면접시험 성적중 적어도 다른 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙 하에 지원자를 선발할 때 선발 할 수 있는 최대 인원 수를 구하여라. 되게 간단한 듯 보이면서 많이 틀렸던 문제다. 서류 심사 성적을 기준으로 정렬을...

Link https://www.acmicpc.net/problem/2217 Note k개의 로프 정보가 주어질 때, 로프를 사용하여 들어 올릴 수 있는 최대 중량을 계산하여라. 알고리즘에 있어 크게 생각할 부분은 없었다. 각 로프 입장에서는 자기가 들 수 있는 값보다 큰 값을 들어올리지는 못하기 때문에 자기 자신을 기준으로 자기보다 많이 들어 올릴 수...

링크 https://www.acmicpc.net/problem/1931 Note 한개의 회의실과 회의 일정이 주어질 때 회의가 겹치지 않게 최대한 많이 배정 할 수 있는 수를 구하여라. 문제 자체에서 그리디 알고리즘이라는걸 알 수 있는 문제였다. 정렬을 이용하면 쉽게 해결 될 꺼 같은 문제 였는데 감이 잡히지 않아 고생좀 했었다. 종료 시간을 기준으로...

Link https://www.acmicpc.net/problem/1761 Note 가중치가 있는 트리가 주어질 때 두 정점 사이의 가중치의 합을 출력한다. 기존 LCA문제에서 가중치가 추가된 LCA문제. 단지 루트 노드가 지정이 되지 않았기에 어느 노드를 기준으로 깊이를 설정해도 상관은 없다. 가장 일반적이게 1번 노드를 기준으로 깊이를 지정했다. ...

Link https://www.acmicpc.net/problem/11437 Note 1을 루트로 하는 트리가 주어질 때 두 정점의 가장 가까운 공통 조상의 번호를 출력한다. LCA를 처음 공부할 때 개념을 잡기 좋은 문제라고 한다. 다른 블로그를 돌아다니면서 개념을 익힐 때 왜 깊이를 DFS로 설정해 주는지 의문을 가졌었다. 예제를 직접 노트로 옮겨...

Link https://www.acmicpc.net/problem/6118 Note 수혀니와 재서기가 숨바꼭질을 할 때 가장 멀리 있는 지점 중 가장 작은 번호와, 거리, 같은 지점의 개수를 출력해주자. 가중치도 없고, 단순히 거리만 있는 문제이기에 크게 생각할 점이 없다. 최대 지점의 수가 2만이기에 인접 행렬을 사용하지 않아야 한다. 최소 거리만 ...

Link https://www.acmicpc.net/problem/1967 Note 트리의 최대 지름을 출력해주자. 어떤 경우가 트리의 지름이 최대가 되는지를 생각하는 것이 가장 어려운문제. 질문 게시판에서 해답을 얻었던 문제. 루트노드에서 갈 수 있는 최장 거리 노드는 무조건 리프노드가 된다. 그렇다면 최장 거리에 있는 리프노드를 기준으로 가장 멀리...

Link https://www.acmicpc.net/problem/2206 Note 벽을 한번 부술 수 있는 상태에서 0,0 에서 n,m 으로 갈 수 있는 최단 거리를 출력해주자. 과거에 비슷한 유형의 문제를 푼 적이 있다. 방문 체크를 할 때 벽을 부순 상태에 따라서 사용해야 하는 방문체크 변수가 다르다. 같은 위치에서 벽을 부수고 왔거나 부수지 않고...

Link https://www.acmicpc.net/problem/17144 Note 미세먼지와 공치청정기가 있는 환경에서 미세먼지가 확산과 이동이 t번 반복 후 남아있는 미세먼지를 출력하자. 미세먼지가 퍼지는 방법, 공기청정기를 기준으로 공기의 이동까지 크게 예외를 생각할 부분이 없다. 미세먼지 확산 시 상하좌우를 확인 후, 미세먼지의 감소 양이 정...

Link https://www.acmicpc.net/problem/17143 Note 낚시왕이 낚시를 하며 잡은 상어 크기의 총합을 출력해주자. 시뮬레이션의 정석이라는 생각이 든 문제. 낚시왕은 1부터 가로의 끝까지 천천히 한칸씩 움직인다. 상어는 바라보고 있는 방향으로 자신의 속도만큼 움직인다. 벽에 부딪히는 상황이 오면 상어는 방향을 바꿔 남은 거...

Link https://www.acmicpc.net/problem/5670 Note 핸드폰의 자동 완성 기능과 비슷한 프로그램을 만들었을 때 평균 몇 회의 시도를 해야하는지 출력하자. 여러 문자열을 처리 해야하는 문제다. 앞서 풀었던 문제는 정적으로 처리 했던 것과는 다르게 동적 메모리가 필요하다. 트라이를 정적 메모리로 잡고 있기에는 메모리 낭비가 ...

Link https://www.acmicpc.net/problem/16236 Note 작고 귀여운 아기상어가 혼자 힘으로 물고기를 먹으며 얼마나 있는지 출력해주자. 삼성 A형 출제 문제 답게 문제를 열심히 읽어야한다. 다시 한번 더 느꼈다. 먼저 주어진 조건을 생각해보면 아기 상어는 자신의 몸집보다 작은 물고기만 먹을 수 있다. 아기 상어는 자신의 몸집...

Link https://www.acmicpc.net/problem/1080 Note 0과 1로 이루어진 행렬 A B에 대해서 특정 연산을 통해 A를 B로 바꾸는 연산의 최솟값을 구하는 프로그램을 만들자. 처음에는 이 문제가 왜 그리디 알고리즘인지 궁금했다. 질문 게시판에는 이미 같은 생각을 가진 다른사람이 있었다. 0,0을 뒤집을 수 있는 경우는 0,...

Link https://www.acmicpc.net/problem/17103 Note 골드바흐의 추측 : 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 를 만족하는 경우의 수를 출력해주자. 소수를 구하기 위한 에라토스테네스의 체를 이용하면 된다. 두 소수가 같아도 된다. 알고리즘 에라토스테네스의 체를 이용하여 소수를 구한 후 저장한다. TC...

Link https://www.acmicpc.net/problem/6588 Note 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있는지를 검증하는 프로그램을 작성한다. 두 홀수 소수의 합을 구하기 위해서는 일단 소수를 구해야 한다. 에라토스테네스의 체를 이용하여 소수를 구한다. 짝수인 소수는 2 단 한개밖에 없다. 출력에 있어 b - a가...

Link https://www.acmicpc.net/problem/14890 Note N x N 지도가 주어졌을 때 l길이의 경사로를 놓아 지나갈 수 있는 경로의 갯수를 출력해준다. 경사로를 놓기 위해서는 높이의 차이가 1이어야한다. 또한 경사로는 겹쳐서 놓을 수가 없다. 범위를 벗어나서는 안된다. 경사로의 개수는 무제한이다. 위 조건을 만족 하기 위...