문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 숫자와 공백으로 이루어진 문자열에서 숫자를 뽑고, 최댓값과 최솟값을 찾는 문제이다. C++에서는 파이썬처럼 split 함수를 사용할 수 없기 때문에, split함수를 직접 구현하거나, 문자열에서 특정 문자를 구분자로 활용해 부분적인 문자열을 추출하는 방법으로 라이브러리와 getline을 활용해 공백을 분리해줄 수 있다. #include #include #include #include using namespace std; int main(){ // 공백 분리할 문자열 선언 str..
문제 링크 5569번: 출근 경로 상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대 www.acmicpc.net 문제 풀이 이번 문제는 최단거리 경로 찾기이다. 추가적으로 제약사항이 존재하는데, "이 도시는 교통 사고를 줄이기 위해서 교차로를 돈 차량은 그 다음 교차로에서 다시 방향을 바꿀 수 없다. 즉, 교차로에서 방향을 바꾼 후, 1 블록만 이동한 후 다시 방향을 바꿀 수 없다." 라고 한다. 따라서 이 경우, 동쪽과 북쪽(x, y 방향이라고 하자)방향으로만 이동해 2가지의 방향이라고 생각할 수 있지만, x방향으로 바꿀 수 있는지의 유무, y방향으..
문제 링크 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 문제 풀이 이번 문제는 DP 문제이다. "예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다."라는 문구에서, 피보나치 수열의 향기가 느껴졌다. 첫째 날과 둘째 날을 A, B라고 했을 때, 두 값을 구하기 위해 피보나치 수열을 통해 규칙을 찾을 수 있었다. 첫째 날 : A ..
문제 링크 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 문제 풀이 이 문제는 [0, 0]에서 최단경로로 [N, M]에 도달하기 위한 방법의 수를 구하는 문제이다. 다들 한번씩 경로에 1을 표시해서 총 몇가지의 길이 존재하는지 문제를 풀어봤을 것이다. 이것을 알고리즘으로는 DP로 풀 수 있다. 공사중인 도로 만약 [1, 1]인 지점으로 가기 위해서는 최단거리이므로 무조건 [0, 1] 혹은 [1, 0]을 통과해야 한다. 따라서 [1, 1]까지의 경로는 [0, 1]까지의 경로와 [1, 0]까지의..
문제 링크 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 풀이 이 문제는 두 문자열 사이에 공통적으로 존재하는 부분 문자열 중, 가장 길이가 긴 문자열을 찾는 문제이다. 이 문제를 풀기 위해서는 LCS 알고리즘을 사용해야 한다. LCS 알고리즘 이 알고리즘은 길이가 가장 긴 부분 문자열을 문자열1의 길이 * 문자열2의 길이 만큼의 시간복잡도로 찾을 수 있다. 문자열1의 i번째 문자와 문자열2의 j번째 문자가 같다면, 문자열1의 i-1번째 문자와 문자열2의 j-1번째 문자 배열의 결과에 1을 ..
데이콘의 기본 연습대회로 머신러닝에 대해 공부해보았다. 대회 정보 라이브러리 및 데이터 준비 import numpy as np import pandas as pd import seaborn as sns import matplotlib.pyplot as plt import matplotlib import mglearn import joblib import math from sklearn.model_selection import train_test_split, validation_curve, cross_val_score, GridSearchCV from sklearn.neural_network import MLPClassifier from statsmodels.graphics.tsaplots import p..
8주차의 문제 주제는 트리였다. 문제 선정에 있어, 트리 구조에 대해 배워보고싶기도 했고, 트리 카테고리에서 문제를 많이 풀어본 경험이 없어서 선정했다. 그런데, 생각보다 알고리즘 문제를 푸는 입장에서는 트리를 구현해서 문제를 해결하는게 아닌, 다른 방법들을 통해서 문제를 푸는게 더 효율적이었다. 대체로 그래프 쪽 문제와 많이 연관되어있던것 같았다. BOJ.2078 무한이진트리 문제 링크 BOJ.11725 트리의 부모 찾기 문제 링크 BOJ.1240 노드사이의 거리 문제 링크 BOJ.15805 트리나라 관광 가이드 문제 링크 BOJ.22856 트리 순회 문제 링크
이번 주 알고리즘 스터디 주제는 dfs && bfs였다. 워낙 방대하고 나에게는 어려운 부분이라 그래프부터 정리를 해보려 한다. 그래프 그래프는 어떤 자료나 개념을 표현하는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조이다. 이 때, 정점의 위치나 간선의 순서는 그래프의 정의에 포함되지 않는다. 따라서 다른 모양임에도 같은 그래프를 표현할 수도 있다. 그래프의 종류 그래프의 정의는 위처럼 간단하지만, 표현하고자 하는 대상에 따라 여러가지 변형된 형태를 가질 수 있다. 정점이나 간선에 추가적인 속성을 부여할 수도 있고, 제약을 둘 수도 있다. 대표적으로는 방향 그래프가 있으며, 각 간선이 방향이라는 새로운 속성을 가진다. 반대로 무향 그래프는 각 간선에 방향이 없는 그래프를 뜻한다. 또..
