꾸준함

문제 링크입니다:https://www.acmicpc.net/problem/1003algospot에서 동적계획법 문제를 풀다보니 아직 미흡한 것 같아서 백준 온라인 저지에서 동적계획법 기초 문제를 풀어봤습니다. 물론 동적계획법을 사용하지 않아도 되는 문제이지만 동적계획법을 연습하고자 메모이제이션을 사용하였습니다. /*N이 주어졌을 때, fibonacci(N)을 호출할 경우 0과 1이 각각 몇번 출력되는가?*/#include #include //memsetusing namespace std; int N; //주어진 숫자int save = 2; //이미 구한 수는 다시 구하지 않는다int cache[2][41]; //메모이제이션 void fibonacci(int n){ if (N >= save) { for (..

문제 링크입니다:https://algospot.com/judge/problem/read/MORSE확실히 난이도:상과 난이도:중은 차이가 있는 것 같습니다.이 문제는 오버플로를 막기 위해 최대치를 미리 선정해둔 것과 다이나믹 프로그래밍을 사용하지 않는 풀이가 인상적이였습니다. #include #include #include #include //memsetusing namespace std; //모든 모스 신호를 만드는 완전 탐색 알고리즘/*//signal: 지금까지 만든 신호//con: 더 필요한 - 개수//pro: 더 필요한 o의 개수void generate(int con, int pro, string s){ if (con == 0 && pro == 0) { cout 0) generate(con, pro..

문제 링크입니다:https://algospot.com/judge/problem/read/OCR여태까지 봤던 문제들 중에서 개인적으로 제일 어려운 문제라고 생각합니다.Viterbi algorithm(비터비 알고리즘)을 이용하여 푸는 문제인데 문제해설을 세번이나 정독했는데도 아직 부족하다는 느낌이 듭니다.다음 문제를 풀기 전에 Viterbi algorithm을 충분히 익혀야겠습니다... /* OCR은 사람이 쓰거나 기계로 인쇄한 글자를 스캔한 이미지를 다시 기계가 읽을 수 있는 문자로 변환하는 과정이다. 과거에 인식했던 수많은 문장들을 분석해 원본 문장의 형태를 파악하려고 한다 //중략 어떤 문장을 단어별로 인식한 결과가 주어졌을 때, 원본일 조건부확률이 가장 높은 ㅁ누장을 찾아내는 프로그램을 작성하시오 *..

문제 링크입니다:알고리즘 설명이 다 되어있기 때문에 그대로 코드만 작성해주면 됩니다. /*Lune 알고리즘은 신용카드의 번호가 맞는지 확인할 때 쓰인다.최대 16자리 숫자가 주어졌을 때 카드 번호가 맞으면 true 틀리면 false를 반환하시오 알고리즘은 다음과 같다:1.자릿수가 홀수이면 홀수번째 숫자들에 2를 곱한다 자릿수가 짝수이면 짝수번째 숫자들에 2를 곱한다.2.두배를 했을 때 해당 숫자가 9를 넘긴다면 각 자릿수끼리 더하거나 해당 숫자에서 9를 뺀다3.모든 자릿수의 숫자를 더한다.4.10으로 나누었을 때 나머지가 0이면 true, 그 외의 경우 false이다*/#include #include using namespace std; class Kata{public: static bool valida..

문제 링크입니다: http://www.codewars.com/kata/55ab4f980f2d576c070000f4/train/cpp직접 그려가면서 하면 정말 간단한 문제입니다. 이런식으로 규칙이 있기 때문입니다. /*8*8 체스보드에서 친구와 게임을 하고 있다.첫번째 열에는 1/2, 2/3, 3/4, 4/5, 5/6, 6/7, 7/8, 8/9두번째 열에는 1/3, 2/4, 3/5, 4/6, 5/7, 6/8, 7/9, 8/10세번재 열에는 1/4, 2/5, 3/6, 4/7, 5/8, 6/9, 7/10, 8/11마지막 열에는 1/9, 2/10, 3/11, 4/12, 5/13, 6/14, 7/15, 8/16 체스보드에 모든 숫자가 입력되었다면 게임 참가자들은 모두 동전을 던진다.앞면이 나오면 체스보드에 적혀있..

문제 링크입니다:최근 풀었던 문제들처럼 동적계획법을 활용하여 문제를 풀면 됩니다. 또한 backtracking(역추적)을 통해 선택한 물건들을 유추할 수 있습니다. /*여행을 갈 때 캐리어 하나만 가지고 가려고 한다.가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를조사해 캐리어의 용량 w이하로 절박도를 최대화할 수 있는 물거들의 목록을계산하는 프로그램을 작성하시오*/#include #include #include #include #include //memsetusing namespace std; int total, capacity; //총 아이템 양과 가방 용량int volume[100], need[100]; //물건의 부피와 절박도int cache[1001][100];string n..

http://jaimemin.tistory.com/317?category=985009에서는 LIS의 길이만 구했는데 이번에는 직접 최대 부분 수열까지 구해보는 코드입니다. /*최대 증가 부분 수열을 실제로 계산하기*/#include #include #include #include //memsetusing namespace std; int length; //수열 길이int cache[101], S[100], choices[101];//S[start]에서 시작하는 증가 부분 수열 중 최대 길이 반환int LIS(int start){ int &result = cache[start + 1]; if (result != -1) return result; result = 0; int bestNext = -1; for..

문제 링크입니다: https://www.codewars.com/kata/tank-truck/train/cpp수학을 오랜만에 하려니 정말 막막했습니다.인터넷으로 공식을 모두 검색한 결과 풀 수 있었습니다!아래 그림은 부연설명용으로 편집한 그림입니다. /* 이웃집에 탱크 트럭을 모는 아저씨가 산다. 기름이 어느정도 남았는지 표시하는 등이 나가버려서 이웃집 아저씨는 남은 기름으로 배달이 가능한지 판별을 할 수 없는 상태이다. 그래서 트럭을 평평한 땅 위에 둔 다음에 탱크의 연료의 높이를 측정하였다. 운이 좋게도 탱크의 연료통은 완벽한 원기둥이다. 남은 연료의 높이는 h, 지름은 d, 그리고 총 부피는 vt이다. 남은 연료의 부피를 구하시오 */ #include #include using namespace st..

문제 링크입니다: https://www.codewars.com/kata/statistics-for-an-athletic-association/train/cpp문제 해석하는데 걸린 시간 정말 오래 걸렸습니다.처음에 hh|mm|ss가 팀 당 3명씩 출전시켜서 hh, mm, ss 그룹끼리 평균을 내는 문제인 줄 알았다가 한참 지나고 나서야 시간/분/초 기록인 것을 깨달았습니다.또한 hh/mm/ss 중 하나라도 00이라면 NULL 포인터가 들어간다고 문제에 적혀있어서 예외처리하느라 코드가 상당히 지저분해졌습니다.개인적으로 마음에 드는 코드는 아니지만(이쁘지 않고 상당히 지저분합니다 ㅠ) 그래도 풀었다는 것에 의의를 두고 나중에 수정해보겠습니다! /*당신은 지역 스포츠팀의 "컴퓨터 전문가"이다.많은 팀의 육상선수..

문제 링크입니다: http://www.codewars.com/kata/57814d79a56c88e3e0000786/train/cpp문제 해석하는게 진짜 힘들었습니다. 2nd char을 계속 두번째 문자라고만 해석해서 처음에 접근을 완전 엉뚱하게 했습니다.every 2nd char이라고 하면 짝수번째 인덱스에 있는 문자라고 해석했어야했네요. /*문자열을 암호화하는 방법:짝수번째 문자들을 모두 이어붙인 뒤 뒤에 홀수번째 문자들을 모두 이어붙인다이 것을 n번 진행하시오! 또한 복호화하는 함수도 작성하시오*/#include #include using namespace std; std::string encrypt(std::string text, int n){ int length = text.length(); //..