관광이 블로그

안녕하세요 감자 코딩에 감자개발자입니다. 이번에 살펴볼 문제는 대표적인 플러드필 알고리즘중 하나인 단지번호붙이기를 BFS로 풀어보도록하겠습니다. 이전에 강의에서 DFS로 풀어보았었는데요, 이번에는 BFS로 다시 풀어보려고 포스팅을 하겠습니다. 단지번호붙이기 성공 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 34947 13452 8944 38.168% 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을..

안녕하세요, 감자코딩에 감자개발자입니다. 이번에 살펴볼 알고리즘 문제는 백준알고리즘 11052번 카드 구매하기 문제입니다.이 역시도 DP관련 문제인데요, 하지만 다른점이 하나 있습니다.이번 문제에서는 카드의 최대값을 구하는 문제입니다. 지금 까지 포스팅한 DP문제들은 해당하는 경우의 수들을 구하는 문제였지만, 이번 문제는 한번 더 생각해야할 요소가 있습니다. 바로 들어가겠습니다 :) 1. 문제 카드 구매하기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB161619472702059.036%문제요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는..

안녕하세요, 감자코딩에 감자개발자입니다. 이번에 살펴볼 알고리즘 문제는 백준알고리즘 9095번 1,2,3 더하기 문제입니다.2*n 타일링 문제에 이어서 저희가 공부해왔던 DP를 활용하여 풀면 아주 쉽게 풀 수 있습니다. 문제를 바로 살펴보죠. 1. 문제1, 2, 3 더하기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB27599174891193562.006%문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다...

안녕하세요, 감자코딩에 감자개발자입니다. 이번에 살펴볼 알고리즘 문제는 백준 알고리즘 2*n 타일링 1에 이어서 11726번 2*n 타일링2 문제입니다.저번에 2*n 타일링문제를 잘 풀어보셨다면, 이 문제 또한 수월하게 푸실 수 있을것입니다. 문제부터 살펴보죠. 문제 링크 https://www.acmicpc.net/problem/11727 1. 문제 2×n 타일링 2 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB155599176745859.436%문제2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력첫째 줄에 2×n 크기의 직사각..

안녕하세요, 감자코딩에 감자입니다. 미국여행을 샌프란시스코, LA, 라스베가스, 애리조나 페이지 , 뉴욕 등 자동차여행을 1-2월 한달동안 여행하게 되면서 오랜만에 포스팅입니다. 3월달에 한국 오자마자 인턴 준비 및 학교를 다니면서 포스팅이 늦어졌네요^^ 코딩테스트 대비하기 위해서 꾸준히 포스팅을 할 예정이오니, 자주 방문해주세요^^ 최근에 관심을 가지고 있는 리액트 ,서버 관련 포스팅도 자주 올려보도록 하겠습니다. 이번에 살펴볼 알고리즘 문제는 1707번 대표적인 그래프문제인데요. 그래프 문제중에 BFS,DFS를 사용한 이분 그래프 문제입니다. 문제는 아래와 같이 있습니다. 재귀호출 개념 정리: https://kgh940525.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6..

안녕하십니까 감자코딩에 감자개발자입니다.이번에 살펴볼 문제는 백준알고리즘의 10809문제인 알파벳찾기 문제입니다. 문제 링크https://www.acmicpc.net/problem/10809 문제알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 입력첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 출력각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단..

안녕하십니까 감자코딩에 감자개발자입니다. 이번에 살펴볼 문제는 백준알고리즘의 10808번문제인 알파벳 개수 문제입니다. 문제 링크https://www.acmicpc.net/problem/10808 문제알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 출력단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. 예제 입력 1 baekjoon예제 출력 1 1 1 0 0 1 0 0 0 0 1 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 문제 해결 방법 1) 가장먼저 아스키코드에 대한 ..

안녕하세요 감자코딩에 감자개발자입니다.이번에 풀어볼 문제는 백준알고리즘에 10866문제인 Deque를 사용한 문제입니다. 문제 링크https://www.acmicpc.net/problem/10866 문제정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여덟 가지이다. push_front X: 정수 X를 덱의 앞에 넣는다.push_back X: 정수 X를 덱의 뒤에 넣는다.pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.size:..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by kgh on 2018. 8. 18. * Blog : http://kgh940525.tistory.com * Github : http://github.com/kgh940525 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by kgh on 2018. 8. 18. * Blog : http://kgh940525.tistory.com * Github : http://github.com/kgh940525 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 49603 16098 10473 32.213% 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 ..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by kgh on 2018. 8. 18. * Blog : http://kgh940525.tistory.com * Github : http://github.com/kgh940525 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 49603 16098 10473 32.213% 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 ..

#include #include using namespace std; int main() { int n; // 입력 최대붕어 int fish_price[1001]; // 붕어 가격 int dp[1001]; // 붕어 저장 dp scanf("%d", &n); // 붕어 수 입력 // 붕어 가격 입력 for (int i = 1; i

/* 단지번호붙이기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 19045 7136 5006 38.328% 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N..

안녕하세요 감자 코딩에 감자개발자입니다. 이번에 살펴볼 문제는 DFS와 BFS의 대표적인 문제인 1260번 문제입니다. 문제 링크 https://www.acmicpc.net/problem/1260 /* 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 한 간선이 여러 번 주어질 ..