문제 설명 입출력 예제 풀이 코드 연속된 소수의 합을 구하기 위해서는 에라토스테네스의 체를 이용해 N까지의 소수를 구하고, 구한 소수 배열을 바탕으로 투 포인터를 활용해 연속된 소수의 합이 N이 되는지를 확인하여 정답을 구할 수 있다. 에라토스테네스의 체와 투 포인터에 대한 설명은 아래 링크에서 참고할 수 있다. [알고리즘] 투 포인터(Two Pointers)란? 투 포인터(Two Pointers) 투 포인터는 말 그대로 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것 입니다. 투 포인터를 활용하기 위한 조건은 주어진 배열에서 연속된(정렬이 hstory0208.tistory.com [Java/자바] 프로그래머스 - 소수 찾기 (에라토스테네스의 체) 문제 설명 1부터 입력받은 ..
문제 설명 입출력 예제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 코드 배열에서 특정한 합을 갖는 부분 연속 수열을 찾는 것은 투 포인터 알고리즘을 활용하는 대표적인 예이다. 투포인터 알고리즘에 대한 설명은 아래 링크를 통해 확인 할 수 있다. [알고리즘] 투 포인터(Two Pointers)란? 투 포인터(Two Pointers) 투 포인터는 말 그대로 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것 입니다. 투 포인터를 활용하기 위한 조건은 주어진 배열에..
문제 설명 입출력 예제 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 코드 bfs 알고리즘 문제 분류에 있는 문제였지만 구현에 가까운 문제였다. 구현문제 답게 문제의 요구사항에 맞게 구현하여 풀 수 있었다. 이 문제에서 필요한 기능은 상하좌우 동일한 블록 탐색, 블록 제거, 블록 떨어트리기 총 3가지로 해당 기능들을 메서드로 뽑아 코드를 작성했다. 아래의 코드 주석을 통해 문제를 쉽게 이해할 수 있을 것이라고 생각한다. 정답 코드 from collections import deq..
문제 설명 입출력 예제 풀이 코드 이 문제는 2차원 배열이 아닌 3차원 배열 방식으로 풀어야 한다. 내가 3차원 배열로 표현한 방식은 visited[행][열][말처럼 움직일 수 있는 남은수(K)] 이다. 최소한의 동작으로 도착지점에 도착하기 위해서는 k번 말 처럼 움직인 다음 원숭이처럼 움직여야 최소한의 동작으로 도착 가능하다. 정답 코드 from collections import deque import sys input = sys.stdin.readline K = int(input()) W, H = map(int, input().split()) # 열, 행 board = [list(map(int, input().split())) for _ in range(H)] # 말처럼 이동하는 경우 dx_knigh..
문제 설명 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 코드 이 문제는 가능한 모든 경로를 탐색하되, 조건을 만족하지 않는 경로는 중간에 가지치기하여 더 이상 탐색하지 않는 백트래킹 알고리즘을 사용하여 풀 수 있었다. 문제에 대해 설명하자면, 체스에서 퀸은 상하좌우 대각선 모든 방향으로 원하는 만큼 이동할 수 있다. 그렇기 때문에 퀸을 서로 공격할 수 없도록 놓기 위해서는 체스판위의 행, 열 마다 하나의 퀸이 존재해야한다. 처음에는 2차원 배열로 푸는 방법이 더 이해가 쉬울것 같아서 2차원 배열로 문제를 풀고 제출해..
문제 설명 입력과 출력 및 예제 풀이 코드 2차원 배열의 값들을 하나씩 탐색해 해당 부분이 외부 공기와 2번 이상 접촉했는지 확인해야 하므로 BFS를 이용해 문제를 풀 수 있다. 내 코드에서 주의할점으로는 치즈가 있는 부분은 visited 방문 처리 하지 않았다는 점인데 여러 면에서 공기와 접촉이 될 수 도 있기 때문에 이 부분을 방문 처리 해버리게 되면 해당 치즈는 무조건 한 면만 접촉되는 것이 되기 때문이다. 나머지 부분은 주석을 통해 이해할 수 있을 것으로 생각되어 자세한 설명은 생략한다. 정답 코드 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) cheeze = [l..