Ikjo's Technology blog

문제 설명 25331번: Drop 7 Drop7은 7×7 크기의 격자에서 진행하는 싱글 플레이어 게임이다. 처음에는 격자가 비어있고, 플레이어는 매 턴마다 1 이상 7 이하의 정수 하나가 적힌 공을 받아 7개의 열 중 한 곳에 떨어뜨려야 한 www.acmicpc.net 접근 방법 해당 문제는 원티드 주관 코딩테스트 대회 2022년 2회차 문제로서 당시 시간적 여유가 있었음에도 불구하고 문제 해결을 위한 아이디어가 떠오르지 않아 제대로 접근조차 하지 못했었던 문제였습니다. 그래서 아쉬운 마음에 코딩테스트 이후에 따로 시간을 내서 재도전 해보았습니다. 우선 문제를 해결하기 위해 접근했었던 방법을 단계별로 나타내면 다음과 같습니다. 1. 각 열별로 공 떨어트리기 - 떨어뜨린 공은 이미 배치되어 있는 공 바로 ..

문제 설명 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 접근 방법 해당 문제는 BFS(너비 우선 탐색)를 통해 해결할 수 있었습니다. 로봇 청소기는 현재 장소에 대한 좌표값 뿐만 아니라, 현재 방향 정보를 가지고 있습니다. 이러한 정보를 바탕으로 별도의 로봇 청소기에 대한 구조체를 선언해주었습니다. static class Robot { int x; int y; int direction; int countOfCleaning; public Robot(int x, int y, int direction, int ..

문제 설명 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 접근 방법 해당 문제는 누적합을 이용하여 해결할 수 있었습니다. 사실 처음 문제에 접근했을 때는 누적합을 생각하지 못하고 주어진 수열 상의 구간 길이 1부터 구간 길이 N까지의 부분합을 일일이 구해주면서 S 이상인 최소 구간을 구하도록 했었습니다. (결과는 당연히 시간 초과..😂) 이러한 방식은 반복문을 3개나 타기 때문에 매우 비효율적인 방법이었습니다. (반복문 하나는 구간 길이를 1부터 N까지 증가시키는 반복문, 다른 하나는 구간을 ..

문제 설명 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 해당 문제는 DFS(깊이 우선 탐색)를 통해 해결할 수 있었습니다. 이 문제를 풀기 전까지만 해도 깊이 우선 탐색하면 주로 인접 행렬 방식으로 접근했었습니다. 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식으로 연결이 되지 않은 노드 정보들까지도 배열 상에 포함되어 있다고 볼 수 있습니다. 이러한 인접 행렬 방식의 단점은 메모리가 불필요하게 낭비된다는 점입니다. 앞서 언급했듯이 연결되지 않은 노드들의 정보들도 포함되기 때문입니다. 해당 문제에서는 노드의 개수 N이 최대 10만개로, ..

문제 설명 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 접근 방법 해당 문제는 투 포인터 알고리즘을 통해 해결할 수 있었습니다. 최초 용액 정보를 받은 데이터를 오름차순으로 정렬해줍니다. (내림차순으로 정렬해도 무방합니다.) 이후 오름차순된 해당 데이터 상 시작점과 끝점을 투 포인터로 삼아 두 점의 합을 구하는데, 이 합이 최대한 0에 가까운 경우의 두 용액의 값을 결과값으로 저장하도록 합니다. 이때 시작점과 끝점을 투 포인트로 삼은 이유는 최솟값과 최댓값을 합쳤을 때 0..