DGOS

[2019 KAKAO BLIND RECRUITMENT] 뉴스 클러스터링 - C++

level2

문제 뉴스 클러스터링 문자열 사이의 유사도를 검사하는 문제입니다. 두 문자열에 대해 각각 두 글자 씩 끊어서 다중집합을 만들고, 두 집합의 교집합에서 합집합을 나눈 값이 유사도입니다. 만약 문자열 “FRANCE” 와 “FRENCH”가 주어진다면 각각 (FR, RA, AN, NC, CE), (FR, RE, EN, NC, CH)의 집합이 만들어지며, 교...

Posted by dongjune on December 26, 2020

[프로그래머스] 소수 만들기- C++

level2, 에라토스테네스의 체

문제 프로그래머스 소수 만들기 풀이 우선 소수를 판별하는 것에는 에라토스테네스의 체를 사용했습니다. 에라토스테네스의 체는 이 포스팅 에서 자세히 다뤄보았습니다. 3가지 수를 합해서 나올 수 있는 모든 수들의 소수 체크를 해줘야 합니다. 그렇기 때문에 일정범위 안에 있는 수 들이 소수인지 아닌지 판별할 때 유리할거라 생각하여 에라토스테네스의 체 알고리즘...

Posted by dongjune on December 23, 2020

[2019 KAKAO BLIND RECRUITMENT] 오픈채팅방- C++

프로그래머스

문제 프로그래머스 - 오픈채팅방 풀이 우선 이름의 갱신을 편리하게 하기위해 unordered map을 사용하였습니다. map은 key 값이 중복되지 않는다는 특성이 있기 때문에 다음과 같이 간편하게 Id의 이름을 갱신할 수 있습니다. 1 2 3 4 5 unordered_map<string,string> um; // [key:value] = ...

Posted by dongjune on December 22, 2020

[프로그래머스] 튜플- C++

level 2

문제 프로그래머스 튜플 풀이 문제에서 ((2), (2, 1), (2, 1, 3), (2, 1, 3, 4))는 튜플 (2, 1, 3, 4)를 나타내고 ((1,2,3),(2,1),(1,2,4,3),(2)) 역시 튜플 (2, 1, 3, 4)를 나타냅니다. 자세히 보시면 가장 많이 나오는 숫자 순으로 정렬하면 되는 것을 알 수 있습니다. 2가 4개 나오니까...

Posted by dongjune on December 21, 2020

[프로그래머스] 땅따먹기- C++

level 2, DP

문제 땅따먹기 풀이 DP를 사용하여 풀이했습니다. 다음은 bottom up 방식의 재귀함수입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int findMax(int y,int x,vector<vector<int>> &land){ // 기저사례 if(y==n-1) ret...

Posted by dongjune on December 20, 2020

[프로그래머스] 다음 큰 숫자- C++

level 2, 비트마스크

문제 다음 큰 숫자 풀이 1. 이진수로 변환해서 풀기 처음에는 정수를 string 타입의 이진수로 변환하는 함수를 만들어서 풀었습니다. 다음은 정수를 string 이진수로 변환하는 함수입니다. 1 2 3 4 5 6 7 8 9 10 11 // 정수 n을 이진수로 변환 string getBinary(int n) { string ret=""; ...

Posted by dongjune on December 20, 2020

[프로그래머스] 가장 큰 정사각형 찾기- C++

level 2

문제 가장 큰 정사각형 찾기 풀이 다음과 같은 입력이 있습니다. 한눈에 봐도 가장 큰 사각형의 크기는 3x3 = 9 입니다. 9라는 답을 어떻게 도출할 수 있을까요? 2차원 배열의 요소들을 반복문으로 순회합니다. 이때 값이 0이라면 정사각형을 만들 수 없기 때문에 그냥 지나갑니다. 1이 나오면 왼쪽, 위, 왼쪽 대각선의 요소들을 검사합니다. 이때 다...

Posted by dongjune on December 20, 2020

[프로그래머스 [월간 코드챌린지 시즌1]] 쿼드압축 후 개수 세기- C++

level 2

문제 쿼드압축 후 개수 세기 풀이 분할 정복을 사용하여 풀 수 있는 문제입니다. 재귀 함수를 사용하여 현재 검사하는 정사각형의 모든 수가 같지 않다면 사각형을 4등분으로 나눠서 재귀함수를 호출해줍니다. 만약 현재 검사하는 정사각형의 모든 수가 같다면 0 또는 1의 개수를 1 증가시킨 후 재귀함수를 호출하지 않고 바로 return 해줍니다. 저는 처...

Posted by dongjune on December 19, 2020

[백준] 1932번 정수 삼각형 - C++

DP, 다이나믹 프로그래밍

문제 1932번 정수 삼각형 풀이 삼각형의 꼭대기에서부터 아래층으로 내려옵니다. 내려오면서 선택 된 수들의 합이 최대인 경로를 구하는 문제입니다. 저는 재귀함수를 통해 구현했습니다. 재귀 함수 안에서 현재 위치의 아래와 대각선 오른쪽의 재귀함수를 호출하여 두 값중 더 큰 값을 메모이제이션 해줬습니다. 다음은 구현한 재귀함수입니다. 1 2 3 4 5 ...

Posted by dongjune on December 18, 2020

[백준] 2579번 계단 오르기 - C++

DP, 다이나믹 프로그래밍

문제 2579번 계단 오르기 풀이 문제의 포인트는 계단을 1칸씩 또는 한 칸 뛰어서 오를 수 있다. 계단을 3칸 연속으로 오르면 안된다. 계단마다 점수가 있다. 마지막 계단에 반드시 도착해야 한다. 마지막 계단에 도착할 때까지 지나올 수 있는 계단의 최대 값을 구한다. 반복문과 재귀함수 2가지 방법을 사용하여 코드를 작성해봤습니...

Posted by dongjune on December 17, 2020

[2019 KAKAO BLIND RECRUITMENT] 뉴스 클러스터링 - C++

level2

[프로그래머스] 소수 만들기- C++

level2, 에라토스테네스의 체

[2019 KAKAO BLIND RECRUITMENT] 오픈채팅방- C++

프로그래머스

[프로그래머스] 튜플- C++

level 2

[프로그래머스] 땅따먹기- C++

level 2, DP

[프로그래머스] 다음 큰 숫자- C++

level 2, 비트마스크

[프로그래머스] 가장 큰 정사각형 찾기- C++

level 2

[프로그래머스 [월간 코드챌린지 시즌1]] 쿼드압축 후 개수 세기- C++

level 2

[백준] 1932번 정수 삼각형 - C++

DP, 다이나믹 프로그래밍

[백준] 2579번 계단 오르기 - C++

DP, 다이나믹 프로그래밍

FEATURED TAGS

ABOUT ME