개발저장소

문제https://www.acmicpc.net/problem/1018  풀이체스판은 흰색과 검은색이 번갈아가면서 칠해져있어야 한다. 인접한 칸이 같은 색이면 안된다.N X M 크기의 보드를 8 X 8 사이즈로 잘라 체스판을 만드려고 한다.이렇게 잘라서 만든 체스판은 색이 잘못된 경우 새로 칠하려고 한다.자를 수 있는 체스판의 경우 중에서, 새로 칠하는 횟수가 가장 적은 경우의 최소 개수를 출력한다.문제를 풀기 위해선 두 가지 포인트를 해결해야 한다.첫째, N X M 사이즈의 보드를 어떻게 체스판 사이즈로 나눌 것인가.둘째, 새로 칠하는 횟수를 어떻게 구해야 할 것인가. 첫째는 만들어질 수 있는 체스판의 경우의 수는 (N - 7) * (M - 7)이 된다.(0,0)을 첫 번째 칸으로 가지는 체스판부터, (..

문제https://www.acmicpc.net/problem/18111  풀이마인크래프트의 땅 고르기 작업을 한다. 땅 고르기란, 범위 내의 블록 높이를 같은 상태로 만드는 작업이다.땅 고르기 범위는 N X M 크기이다.하나의 블록을 캐면 2초가 걸리고, 그 블록이 인벤토리에 저장된다.하나의 블록을 설치하면 1초가 걸리고, 인벤토리에서 꺼낸 블록을 사용한다. 인벤토리에 블록이 없다면 설치할 수  없다.땅의 높이는 최소 0, 최대 256이다. 블록은 최대 64,000,000개가 주어질 수 있고, 맵의 크기는 최대 500 X 500이다.맵 전체의 땅을 고르는데 걸리는 최소 시간을 구해야 한다. 만약 시간이 같다면 땅의 높이가 더 높은 경우를 출력한다. 주어진 맵의 크기가 크지 않아 브루트포스 알고리즘을 사용..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49994 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 게임 캐릭터에게 상하좌우로 한 칸씩 움직이는 명령을 내린다. 명령어는 순서대로 UDLF이다. 게임 캐릭터는 좌표평면 (0,0)에 위치하고, 좌표는 5X5 크기이다. 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구한다. 움직인 총 이동거리에서 한번 가본 길을 지날 때는 이동거리에 포함시키지 않는다는 뜻이다. 또한 좌표평명 밖으로 이동하는 명령어가 입력된 경우, 그 명령은..

문제https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  풀이게임의 스테이지 별로 실패율을 구해, 실패율이 높은 스테이지부터 내림차순으로 스테이지 번호가 담긴 배열을 구해야 한다.실패율이란, '스테이지에 도달한 플레이어 수'에서 '스테이지를 클리어하지 못한 플레이어 수'를 나눈 값이다.전체 스테이지 개수 N과 현재 사용자들이 멈춰있는 스테이지의 번호가 담긴 배열 stages가 주어진다.stages의 1번 인덱스에는 1번 사용자가 멈춰있는 스테이지 번호..

학습 Point시간복잡도점근 표기법 코딩테스트에서 코드를 평가하는 방식은 크게 두 가지이다. 내가 작성한 코드의 결괏값이 테스트 케이스의 결과와 일치하는가? 문제에서 요구한 알고리즘의 성능을 만족하는가? 두 방식은 프로그래머스에서 문제를 풀 때 쉽게 볼 수 있는 '정확성'과 '효율성'이다.결과가 일치하는 것은 쉽게 확인할 수 있다. 하지만 성능을 만족하는 것은 어떻게 확인해야 할까?단순히 생각하자면 입력값을 넣고 출력값이 나올 때까지 걸리는 시간을 측정한다고 생각하면 되겠지만, 이는 컴퓨터의 성능 같은 다양한 외부 요인에 영향을 많이 받는다. 바로 여기서 시간복잡도의 개념이 등장한다. 시간복잡도란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다. 연산 횟수는 전적으로 ..

문제 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 문제의 코드 버블 정렬을 C++로 구현한 알고리즘이다. 버블 정렬에서 swap이 한 번도 일어나지 않은 루프의 위치를 알아내는 코드이다. 버블 정렬에서 swap이 일어나지 않은 루프가 존재한다는 것은 정렬이 끝났다는 뜻이다. 그러므로 루프를 알아낸 즉시 반복문을 종료하는 것이 좋다. 정렬해야 하는 배열의 크기는 최대 500,000인 자연수이고, 요소의 크기는 최대..

문제https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0www.acmicpc.net 풀이0이 아닌 정수 x를 배열에 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고 제거한다.절댓값이 가장 작은 값이 여러 개라면, 그중에 가장 작은 수를 출력하고 제거한다.0이 아닌 수가 주어지면 배열에 입력하고, 0이 주어진다면 위 규칙에 맞게 수를 출력하면 된다.연산의 개수는 1보다 크고 100,000보다 작다.입력되는 정수 x는 -2^31보다 크고 2^31보다 작다.출력..

문제 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 N자리 숫자 중 왼쪽부터 1자리, 2자리, 3자리, ... N자리까지 모든 수가 소수가 되는 숫자를 모두 출력한다. ex) 7331 => 7, 73, 733, 7331 모두 소수이다. N은 1보다 크고 8보다 작다. 출력되는 소수는 오름차순으로 정렬한다. 1자리씩 점점 숫자를 늘려가며 소수인 경우만 가지를 뻗는 백트래킹 문제이다. 1자리는 2, 3, 5, 7만 가능하기 때문에..

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 크기가 N인 수열 A가 있을 때, 각 원소 Ai에 대하여 Ai보다 오른쪽에 있으면서 큰 수 중에서 가장 왼쪽에 있는 수를 오큰수라고 한다. 수열 A가 있을 때, 각 원소들의 오큰수를 구해야 한다. 오큰수가 없다면 -1을 출력한다. 수열 A의 길이와 각 원소의 크기는 둘 다 1 이상 1,000,000 이하이다. 즉, 다중 for문을 사용한다면 무조건 시간 초과가 일어난다. 스택의 원리를 이해하고 이..

문제 https://www.acmicpc.net/problem/2567 2567번: 색종이 - 2 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 풀이 가로, 세로 길이가 100인 도화지 위에 길이가 10인 정사각형 색종이를 도화지와 평행하게 붙인다. 이러한 방식으로 색종이를 여러장 붙였을 때, 둘레의 길이를 구한다. 중간에 구멍이 뚫린 모양도 둘레에 포함한다. 수학적인 방법으로 접근하려고 했지만 중간에 둘레가 생기는 경우를 계산하기 위해서 그리디한 방법으로 접근하였다. 도화지를 크기가 100 X 100인 2차원 배열로 생각한다. 이때 배..