프로그래머스 코딩 문제 (14) 썸네일형 리스트형 [프로그래머스] GPS (2017 카카오코드 본선) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/1837 DP문제이다. 1. 시간을 1씩 증가시키며 1~n까지의 노드가 오는 경우를 생각하며 d[시간][현재 노드]배열에 저장을 한다. (즉 d[시간][현재 노드]는 현재 시간에 현재 노드가 위치할 수 있는 경우 중 최소의 수정 횟수가 저장되어 있다. 2. t를 끝까지 증가시키며 목적지의 값을 구한다. 점화식 : D[i][j] = min(D[i - 1][인접 노드], D[i - 1][j]) + (현재노드와 log의 노드가 다르면 +1 아니면 +0) #include #include #include using namespace std; // 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요. int s.. [프로그래머스] 리틀 프렌즈 사천성 (2017 카카오코드 본선) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/1836# 1. 존재하는 알파벳과 알파벳의 위치를 map에 저장한다. 2. map은 자동 오름차순 정렬이 되니 차례대로 탐색하며 제거가능한 알파벳이 있나 확인 - 알파벳 제거하는 알고리즘은 백트래킹이나 bfs쓰면 된다. (자세한 알고리즘은 코드의 주석 참고) 3. 전부 제거하거나 더이상 제거 못할때 까지 2를 반복 #include #include #include #include #include #include using namespace std; int m; int n; vector board; bool check[102][102]; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; ma.. [프로그래머스] 보석 쇼핑 (2020 카카오 인턴십) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/67258 이번 문제는 투포인터 문제다. 그냥 단순하게 모든 경우의 수 확인한다면 O(n^2)이 나올것이다. 하지만 투포인터를 이용하면 O(n)으로 해결할 수 있다. 1. 보석을 set에 넣어서 보석 종류의 개수를 확인한다. 2. 투포인터(start , end)를 이용하여 증가시키며 확인한다. 2-1 투포인터 범위안에 보석종류가 포함안된게 있거나 start==end라면 end증가시켜 범위 늘리기 2-2 투포인터 범위안에 보석종류가 전부 포함되면 start 증가시키며 범위 축소해보기 3. 확인한 범위 중 최소의 범위 반환 #include #include #include #include #include using na.. [프로그래머스] 방문 길이 (Summer/Winter Coding(~2018)) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/49994?language=cpp 1. 입력으로 들어온 방향으로 움직인다. 2. 움직일 때 지나간 길을 체크해 둔다. - 나는 해당 좌표에서 4방향의 길로 분류하여 체크를 하였다. (현재 좌표에서 지나가야하는 방향 체크, 다음 좌표에서 지나온 방향 체크) 3. 처음 지나가는 길만 answer++해준다. #include #include using namespace std; bool check[15][15][4]; int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; int x = 5; int y=5; int answer = 0; void moving(char c) { int d = 0;.. [프로그래머스] 방금그곡 (2018 KAKAO BLIND RECRUITMENT) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/17683 이번 문제는 시간복잡도를 고려할 필요없는 파씽문제이다. 그렇기에 연산적인 효율보다는 그냥 구현하기 편한대로 구현하였다. 1. 우선 파씽을 한다, 파씽을 하여 재생시간을 구해준 후 재생시간 동안만큼의 악보를 재작성한다. 2. 재작성한 악보에 주어진 음계m이 포함되어 있다면 조건과 일치하는 음악이다. 2-1 조건과 일치한 음악 중에 재생 시간이 가장 긴 것을 고른다. 2-2 재생 시간이 가장 긴 것 중에선 제일 앞쪽 제목을 선택 #include #include #include using namespace std; string m; vector musicinfos; string time_to_minute(st.. [프로그래머스] 매칭 점수 (2019 KAKAO BLIND RECRUITMENT) (level 3) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/42893 파씽 능력과 자료구조 사용 능력을 알아보기 위한 문제로 보여진다. 자신의 url , 외부링크 url , 일치 단어 개수를 찾는 문제이다. 문자열을 파씽해서 값을 얻을 수 있다. 웹페이지 개수가 최대 20개 밖에 되지 않으니 배열에 넣어서 저장하여도 시간복잡도에 크게 영향을 주지 않는다. 하지만 페이지 개수가 많아지면 map을 사용하여야 하니 연습삼아 map으로 구현하였다. 부가적인 설명은 코드 주석에 달아 놓았다. #include #include #include #include using namespace std; class info { public: int index, base_score; vector.. [프로그래머스] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT) (level 3) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/60061 특별한 함정이 없는 구현, 시뮬레이션 문제이지만 머리속으로만 그리다보니 잦은 실수가 발생하였다. 1. build_frame vector의 순서대로 건물을 짓는다. 단 설치할 때 존재할 수 없는 경우에는 스킵한다. 2. 건물을 삭제하라는 명령어가 나올경우에는 우선 건물을 삭제해본다. 그리고 삭제할 때 영향을 받는 건물들만 존재할 수 있는지 확인해본다. 3. 건물이 완성되면 (x축), (y축), (기둥, 보) 이런 순서로 3중 포문으로 vector에 저장을 한다면 굳이 sorting 하지 않아도 문제에서 원하는 순서대로 저장 가능하다. -> 위 설명에서 빨간글씨에 사용하는 함수 기둥의 경우 -> 바닥위에 있.. [프로그래머스] 오픈채팅방 (2019 KAKAO BLIND RECRUITMENT) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/42888 단순한 문자열 문제이다. 하지만 map을 모르는 사람이라면 당황할 만 하다. 문자열과 닉네임을 단순한 배열에 쌍으로 저장한다면 아이디를 찾는데만 해도 존재하는 아이디 개수n 만큼 어마어마한 시간이 걸린다. 하지만 map으로 저장한다면 tree구조 이기때문에 logn이라는 짦은 시간이 걸린다. 1. record를 차례대로 쭉 훑으면서 Enter일 경우 아이디와 닉네임을 쌍으로 저장하고 Change일 경우에는 갱신한다. 이렇게 한번 쭉 훑으면 결국 map에는 아이디에 대해 최신 닉네임이 저장된다. 2. 다시 record를 처음부터 쭉 훑으면서 명령어가 enter, leave일 경우만 최신 닉네임으로 출력해준.. [프로그래머스] 프렌즈4블록 (2018 KAKAO BLIND RECRUITMENT) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/17679 시뮬레이션 문제 1. 네 블록이 같은 곳들 전부 터트려준다(check이차원 배열에 표시) 2. 터트려주면 열마다 밑에서 올라오면서 제자리로 떨어뜨려준다.(자신보다 밑에서 터진 개수만큼 떨구면 됨) 3. 1,2 를 반복하다가 더이상 터지는 곳이 없으면 종료. #include #include using namespace std; int m=6; int n=6; vector board; bool check[32][32]; //터지는 곳 체크 bool explode() //4개 같은블록들 터트리기 { bool is_exploded = false; for (int i = 0; i < m-1; i++) { for .. [프로그래머스] 괄호 변환 (2020 KAKAO BLIND RECRUITMENT) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/60058 문제 자체에 알고리즘이 완벽하게 주어져 있다. 알고리즘이 주어져있지 않았다면 분명히 어려운 문제겠지만 문제에 알고리즘이 자세히 설명되어있기에 그냥 고민할 것 없이 그대로 구현하면 된다. 알고리즘이 그대로 적혀있기에 굳이 설명할 것 없이 넘어가겠다. 전체적인 알고리즘은 그대로 구현하면 되지만 올바른 문자열인지 아닌지 판별하는 함수는 생각해 보아야 한다. 올바른 괄호 문자열 판별은 단순히 스택을 이용해서 알 수 있다. 열린 괄호일 때 stack에 넣어주고 닫힌 괄호일 때 stack에서 빼주면서 쌍을 만들어 준다. 모두 쌍이 만들어지면 올바른 괄호 문자열이다. (코드에서는 stack을 이용하여 구현하였지만 사.. 이전 1 2 다음