관광이 블로그

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

안녕하세요, 감자코딩의 감자입니다. 이번시간에 살펴볼 문제는 백준 알고리즘의 11724번 문제인데요. 이 문제는 그래프의 연결요소를 찾아보는 문제입니다. ♣ 1. 문제연결 요소의 개수 성공시간 제한메모리 제한제출정답맞은 사람정답 비율3 초256 MB155697734510847.318%문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.출력첫째 줄에 연결 요소의 개수를 출력한다.예제..

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

안녕하세요 감자 코딩에 감자개발자입니다.이번 강의는 vscode에서 python 환경을 구축을 해보겠습니다. 1. vscode 홈페이지에 접속하여서 각자 OS환경에 맞는 vscode를 다운로드 받습니다. 저는 MAC OS 10.14환경에서 진행하였습니다. 2. vscode메인화면에서 shift + command + p 명령어를 실행하여 작업을 실행합니다. 명령어 실행후에 >Python 을 입력한후 Python: Select Interpreter를 클릭합니다. 클릭을 하게 되면 환경을 Setting을 완료하게 됩니다. 3. 그 이후 환경을 구축하고자하는 Python 버전별로 맞추어야하는데요 바로 (2번) 과정을 실행이후에 뜨는 화면입니다. 바로 버전환경을 맞출것을 선택해야합니다. 저는 Python 3.6...

안녕하세요 감자 코딩 & 감자개발자입니다. 이번 강의부터 알고리즘의 핵심인 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..

안녕하세요 감자 코딩 & 감자 개발자입니다. 이번에 살펴볼 문제는 11656번 문제입니다. 바로 접미사 배열을 활용하는 문제인데요. 문자열을 토큰을 잘 잘라내어 정렬까지 할 수있냐하는 문제입니다. 문제 링크https://www.acmicpc.net/problem/11656 접미사 배열 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB43722701219263.555%문제접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다. baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, o..

안녕하세요 감자 코딩 & 감자 개발자입니다. 이번에 살펴볼 문제는 10824번의 문제인 "네 수" 라는 문제입니다.가장 큰 핵심 키워드는 자료형 변수의 범위에 따라 문제를 해결 할 수 있냐입니다.문제 링크https://www.acmicpc.net/problem/10824 네 수 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB82403042254837.295%문제네 자연수 A, B, C, D가 주어진다. 이때, A와 B를 붙인 수와 C와 D를 붙인 수의 합을 구하는 프로그램을 작성하시오. 두 수 A와 B를 합치는 것은 A의 뒤에 B를 붙이는 것을 의미한다. 즉, 20과 30을 붙이면 2030이 된다. 입력첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤..

안녕하세요 감자 코딩 & 감자 개발자 입니다.이번에 살펴볼 문제는 전에 포스팅했던 문제들을 종합적으로 생각할 수 있었던 문제입니다.ROT13문제인데요. ASCII 코드와 입력에 있어서 복합적인 문제라고 생각하시면 될 것같습니다. 문제 링크https://www.acmicpc.net/problem/11655 문제ROT13은 카이사르 암호의 일종으로 영어 알파벳을 13글자씩 밀어서 만든다. 예를 들어, "Baekjoon Online Judge"를 ROT13으로 암호화하면 "Onrxwbba Bayvar Whqtr"가 된다. ROT13으로 암호화한 내용을 원래 내용으로 바꾸려면 암호화한 문자열을 다시 ROT13하면 된다. 앞에서 암호화한 문자열 "Onrxwbba Bayvar Whqtr"에 다시 ROT13을 적용하..

안녕하세요 감자 코딩& 감자 개발자 입니다. 이번에 살펴볼 문제는 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을 출력한다. 단..