관광이 블로그

감자코딩입니다. 이번에 살펴볼 내용은 C++ STL중 하나인 forward_list 입니다. single linked list(단일 연결 리스트) 자료구조를 이용하여 만든 시퀀스 컨테이너이며, std:list기준으로 작성된 컨테이너다. std::forward_list 특징 std:list는 양방향 std::forward_list 단방향 Flow std::list보다 삽입/삭제 속도가 빠름 std::list 양방향인 std::list에 비해 메모리를 적게 사용 삽입과 삭제는 지정한 요소의 다음 요소만 가능 구현의 복잡성과 성능 문제 때문에 std::list에서 제공하는 insert와 erase를 제공하지 않음. Single Linked List는 STL로 forward_list 로 구현되어있고, C+11 ..

안녕하세요 감자코딩에 감자개발자입니다. 이번에 살펴볼 주제는 해싱에 대한 소개입니다. 간략히 요약하여 공부용으로 작성하였습니다. 해싱 개념 설명 데이터 관리/유지 자료구조 리소스 해시 함수(hash function) ————> 해시값(hash value) [이름] [해싱 과정] [index(hash value) : data ] 해시 테이블의 장점 해시충돌이라는 발생 가능성이..

안녕하세요 감자 코딩에 감자개발자입니다. 이번에 살펴볼 문제는 대표적인 플러드필 알고리즘중 하나인 단지번호붙이기를 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보다 크거나 같고, ..

안녕하세요 감자코딩에 감자 개발자 입니다. 이번에 살펴볼 문제는 DP 문제인 이친수 문제입니다. 문제 이친수 성공 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 34368 13003 9725 36.158% 문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다. ..

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

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