고슴도치의 IT여행

풀이 문제 : 백준 1463번 : 1로 만들기 풀이 언어 : C++ 알고리즘 : DP 문제링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 요약 접근 방식 가능한 연산이 세가지 뿐이니까 세가지 연산을 모두 해보고 횟수가 가장 적은 것을 누적하며 구하고자 하는 값까지 찾아올라가는 방식으로, dp 알고리즘을 사용했다. 코드 #include #include using namespace std; int dp[1000000]; int main() { dp[1] = 0; dp[2] = 1; dp[3] = 1; int n; cin >> n; for (int ..

풀이 문제 : 백준 9095번 : 1,2,3 더하기 풀이 언어 : C++ 문제링크 : https://www.acmicpc.net/problem/2742 2742번: 기찍 N 자연수 N이 주어졌을 때, N부터 1까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 문제는 겁나 쉽다. 시간초과 겁나 쉬운 문제가 시간초과가 났다.. 시간초과난 코드는 다음과 같다 #include #include using namespace std; int main() { int x; cin >> x; for (int i = x; i > 0; i--) { cout x; for (int i = x; i > 0; i--) { cout

풀이 문제 : 프로그래머스 구명보트 풀이 언어 : C++ 알고리즘 : 그리디 문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42885# 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제요약 구명보트에 최대 2인이 탈수 있고, 무게제한이 있다. 사람들의 몸무게와 무게제한이 주어졌을때, 최소 몇개의 구명보트를 이용해야만 모든 사람들을 구할 수 있는지 알아내야한다. 첫번째 접근방식 (실패) sort를 해서 무게가 적게 나가는 사..

풀이 문제 : 백준 9095번 : 1,2,3 더하기 풀이 언어 : C++ 알고리즘 : DP 문제링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 요약 입력 값을 1, 2, 3의 합으로 나타낼 수 있는 모든 방법의 수를 구해야한다. 1 + 2 와 2 + 1 는 다른 것으로 취급된다. 접근 방식 일단 입력되는 값이 11 미만의 정수이고, 각 케이스마다 값이 정해져 있다는 점을 파악했다. 또한 입력 값의 수가 커짐에 따라 정답인 수의 크기도 커진다.. 여기서 피보나치와 비슷하다는 느낌을 받았다. 1 : 1 (1) 2 : 2 / 1+1 ..

코딩테스트에서 DP 알고리즘은 단골 문제로 나온다. 그런데도 많은 사람들이 어려워하고, 나 또한 매우 어려워한다. 이번 기회에 개념을 확실히 다지고 DP 를 정복하고자 한다!! 피보나치 수열 DP 알고리즘의 대표적인 예시이다. 예시를 보면서 DP를 이해해보자. 피보나치 수열은 점화식으로 표현할 수 있다. 이 점화식을 따라서 알고리즘을 짜기 위해서는 재귀 함수를 이용해야한다. int fib(int n){ if (n==1 or n==2){ return 1; } return fib(n-1) + fib(n-2); } 그런데 이런식으로만 작성하면 구하고자 하는 값이 커질때는 시간이 너무 오래 걸릴 수도 있다는 한계점이 있다. 왜냐하면 이미 구한 값을 계속 구해야하기 때문이다. n이 1이거나 2일때가 나올때까지 계..

글쓴이는 코딩테스트를 위한 준비로 C++ 공부를 하고 있으며, 다음 내용은 글쓴이가 자주 헷갈리는 string 함수만 정리해 놓은 것임을 알립니다! 앞으로 이야기할 함수들은 모두 헤더파일 string에 있는 아이들이다. #include .find() int findPos = input.find(cmp,pos); pos의 위치부터 cmp 문자열을 찾아서 발견 index값을 리턴해주는 메서드다. cmp("123")가 temp에 몇개 있는지 세는 알고리즘이다. string temp = "12345671234567"; string cmp = "123"; int cnt=0; int pos=0; while(1){ int findPos = temp.find(cmp,pos); //pos값이 계속 바뀌면서 cmp를 찾는..

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 문제 접근 방법 1. 스트라이크, 볼 갯수로 경우의 수 나누기 처음에는 스트라이크, 볼 갯수에 따라 경우의 수를 나눠서 구하려고 했다. if strike == 0 : elif strike == 1 : elif strike == 2: else: if ball == 0: ... 위와 같이 하려다가 경우의 수가 너무 복잡해져서 짜놓은 코드를 다 지우고 다시 생각해보았다. (그런데 다른 분들 풀이를 보니..

문제풀이 사이트에서 제공되는 문제가 아닐때는 본인 스스로 시간제한 판단을 해야한다. 이럴때는 실행시간을 재는 코드를 추가하면 된다. import time start = time.time() # 시작시간 # 코드 작성 end = time.time() # 종료시간 print("time :", end - start) # 실핼시간 = 종료시간 - 시작시간

그리디 알고리즘 (Greedy) : 탐욕법. 매순간 가장 좋아보이는 것 선택, 이 선택이 나중에 미칠 영향에 대해서는 고려X 예시 1 : 거스름돈 문제 - 거슬러줘야할 동전의 최소 개수 구하기 - 가장 큰 화폐부터 거슬러주기 #python n= int(input()) #가격은 10의 배수 count=0 for coin in [500,100,50,10]: #배수임 count+=n//coin n=n%coin print(count) ※ 가지고 있는 동전 중에서 가장 큰 단위가 항상 작은 단위의 배수이므로 그리디로 풀 수 있다. 그리디 알고리즘이 먹히지 않는 거스름돈 문제 예시 2 : 800원을 거슬러줘야하는데 화폐단위 500원, 400원, 100원 (배수가 아님) - 그리디로 문제풀이 : 500원 + 100원..