관광이 블로그

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

안녕하세요 오랜만에 포스팅하는 감자코딩입니다. 기말고사 기간때문에 포스팅을 요새 자주 못하였는데요, 방학을 맞이하여 알고리즘을 꾸준히 시작하려고합니다. 그러면 바로 들어가겠습니다. 이번에 알아볼 문제는 프로그래머스 문제중 하나인 "스킬트리" 라는 문제입니다. 문제 설명 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → ..

DP안녕하십니까 감자 코딩에 감자 개발자입니다. 이번에 살펴볼 문제는 백준 알고리즘 DP문제인 쉬운계단수 문제 입니다. 처음에 DP를 접근하시는 분이라면 조금 어려우실 수 도 있으십니다만, 천천히 같이 풀어보도록하죠. 문제 쉬운 계단 수 성공 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 256 MB 35683 10788 7812 28.467% 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, ..

안녕하세요, 감자코딩에 감자개발자입니다. 이번에 살펴볼 알고리즘 문제는 백준알고리즘 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 크기의 직사각..

안녕하세요, 감자코딩에 감자개발자입니다. 대학생분들은 중간고사 시즌이실텐데요. 저 또한 그렇지만 이번에 중간고사 시험을 하나만 치르게됩니다 : ) 이번에 살펴볼 알고리즘 문제는 백준알고리즘 11726번 2*n 타일링 문제입니다.저번에 살펴봤던 문제는 1로 만들기 문제였었는데요, 이번엔 재미가 아주 있는 타일링 문제입니다. DP적인 사고를 만들기에 충분한 문제인데요.바로 들어가겠습니다 :) 1. 문제 2×n 타일링 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB3599713221995434.803%문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력첫째 줄에 n이 주어..

안녕하세요, 감자코딩에 감자개발자입니다.제가 이번에 포스팅할 내용은 DP의 대표적인 문제인 1로만들기 문제인데요.이번에 복습겸 다시 공부를 하게 되면서 시간복잡도 부분에 대해서 조금 더 포스팅 해보려고해요. 전에 Bottom-up 방식과 Top-Down방식으로 매우 세세하게 포스팅하였지만, 시간복잡도 부분에 대해서는 제가 설명을 제대로 하지 못한 부분이 있었다고 판단이 들어 추가 포스팅을 하겠습니다. 전에 올렸던 포스팅입니다. 처음이신분들은 한번 보시고 오시면 도움이 되실겁니다. [알고리즘] 백준 알고리즘 1463 1로 만들기(Top-Down/Bottom-Up, 피보나치수열) C++https://kgh940525.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6..

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

안녕하세요 감자 코딩 & 감자개발자입니다. 이번 강의부터 알고리즘의 핵심인 DP문제를 많이 풀어보게 될것인데요. DP(Dynamic Programming)동적계획법 이라고 불리오는 방법으로 문제를 풀어볼 예정입니다. 사실 이문제에 대해서는 전에 Java로 포스팅해놓은적이 있습니다만, 자세한 사항을 설명해놓지 않아서 이번기회에 C++로 재 포스팅하겠습니다. 일단 문제풀이에 앞서서 동적계획법(DP)에 대해서 간단히 복습을 하고 시작하겠습니다. 아주전에 제가 한번 정리해놓은 자료가 있는데요. 그쪽을 참고하셔도 됩니다. 관련 링크(동적계획법 DP) http://kgh940525.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DPDynamic-Progamming..

안녕하세요 감자 코딩& 감자 개발자 입니다. 이번에 살펴볼 문제는 2743번의 알고리즘 문제인 단어길이 문제 입니다. 상당히 쉬운문제라서 포스팅을 하지 않으려고 했으나, 시간복잡도면에서 한번더 생각해볼 수 있었던 문제여서 포스팅 하겠습니다. 문제 링크https://www.acmicpc.net/problem/2743 문제알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 영어 소문자와 대문자로만 이루어진 단어가 주어진다. 단어의 길이는 최대 100이다. 출력첫째 줄에 입력으로 주어진 단어의 길이를 출력한다. 예제 입력 1 pulljima예제 출력 1 8 어떠신가요? 문제는 너무 쉽지요? 그래서 포스팅을 하지않으려고 했습니다. 하지만! 쉬울수록 한번더 생각해보아야..

오늘도 1일1-3알고리즘을 풀어보기위해 등장한 감자코딩에 감자개발자입니다. 이번에 살펴볼 문제는 10820 문자열 분석 문제입니다. 문제 링크 https://www.acmicpc.net/problem/10820 문제문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오. 각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있다. 입력첫째 줄부터 N번째 줄까지 문자열이 주어진다. (1 ≤ N ≤ 100) 문자열의 길이는 100을 넘지 않는다. 출력첫째 줄부터 N번째 줄까지 각각의 문자열에 대해서 소문자, 대문자, 숫자, 공백의 개수를 공백으로 구분해 출력한다. 예제 입력 1 This is StringSPACE 1 SPACE S..

안녕하십니까 감자코딩에 감자개발자입니다.이번에 살펴볼 문제는 백준알고리즘의 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:..