Coding_Test_C++
String 공백 단위로 나누는 방법
1. istringstream 과 getline 함수를 이용하는 것이 가장 빠를 것이라 생각하여 하나를 확실하게 알고자 한다. (다양한 방법론을 모두 검색해본 결과 코드가 간략했으므로 해당 방법을 암기하고자 한다.) #include #include #include #include #include using namespace std; int main() { string s = "string with space has to be splited"; istringstream is(s); string buf; while (getline(is, buf, ' ')) { cout
Programmers Level 2: 큰 수 만들기(C++)
https://programmers.co.kr/learn/courses/30/lessons/42883# 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이법 1) 스택을 이용하여서 문제를 해결하였다. 2) 스택이 비어있는 경우는 해당 index의 값을 넣어 주었다. 3) 들어갈 수 있는 값의 개수를 지정하였고, 스택의 맨 위의 값보다 현재의 값이 큰 경우, 스택을 지속적으로 비워 주었다. 이때 넣을 수 있는 남은 값과 스택의 크기를 합하여 값의 개수보다 큰 경우만 반복을 지속하였다. if(st.top()k && st.top()
BaekJoon 2140번: 지뢰찾기(C++)
https://www.acmicpc.net/problem/2140 2140번: 지뢰찾기 지뢰찾기는 N×N에서 이뤄지는 게임이다. 보드의 곳곳에는 몇 개의 지뢰가 숨겨져 있고, 지뢰가 없는 칸에는 그 칸과 인접(상하좌우 및 대각선)해 있는 8개의 칸들에 몇 개의 지뢰가 숨겨져 있는 www.acmicpc.net 풀이법 1) 그리디와 탐색을 진행하여서 문제를 진행하였다. 2) 움직일 수 있는 상하좌우 각 대각선을 배열에 담아서 이를 활용하였으며, 전체를 순회하면서 값은 찾아 주었다. 3) 상하좌우 각 대각선의 값이 0보다 커서 탐색할 수 있다면 답인 answer를 증가시키고 각 값들을 -1씩 해주어서 가능한 모든 경우의 수를 탐색해 주었다. #include #include #include #include #i..
Programmers Level 2: 2019 카카오 개발자 겨울 인턴십 튜플(C++)
https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{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] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 풀이법 1) 문자열을 활용한 정렬과 구현 문제이다. 2) 2차원 정수형 배열을 만들고 { } 사이에 있는 값들을 다 일일이 넣어주었다. 이때 가장 바깥쪽 대괄호는 생략하였다. if(s[i]=='{') { s1=""; check=true; } else if(s[i]=='}'){ temp[j].push_back(s..
BaekJoon 1946번: 신입 사원(C++)
https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이법 1) 정렬을 활용한 그리디 알고리즘으로 해결할 수 있었으나, 풀이에 오랜시간 걸렸던 문제이다. 2) 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 지키기 위해서, 서류 심사 성적을 기준으로 들어온 값을 정렬 하였다. 3 6 1 4 7 3 2 5 4 2 3 6 1 4 4 2 5 7 5..
BaekJoon 1474번: 밑 줄(C++)
https://www.acmicpc.net/problem/1474 1474번: 밑 줄 세준이는 N개의 영어 단어를 이용해 길이가 M인 새로운 단어를 만들려고 한다. 새로운 단어는 N개의 단어를 순서대로 이어 붙이고, 각 단어의 사이에 _을 넣어서 만든다. 이렇게 만든 새로운 단어 www.acmicpc.net 풀이법 1) 규칙을 찾으면 쉽게 풀 수 있는 그리디 알고리즘이었다. 2) 가장 중요한 부분은 'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z' 이며, 사전 순으로 가장 앞서는 단어를 출력해야 한다는 것이다. 3) 입력 받은 값들을 토대로 m의 길이와 단어의 길이를 통해 최소 _가 들어갈 개수를 파악해 주었다. 이후 추가적으로 _를 넣을 ..
BaekJoon 16928번: 뱀과 사다리 게임(C++)
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이법 1) BFS와 구현이 합쳐진 문제였으며 쉽게 풀 수 있는 문제였다. 2) 1차원 배열과 방문을 표기할 배열을 선언해 주었으며, 주사위로 나올 수 있는 값인 1부터 6까지를 일일이 넣어보고, 사다리가 있는 경우 사다리를, 뱀이 있는 경우 뱀을 타도록 코딩을 진행했다. 3) 방문하지 않은 값만 새롭게 방문하도록 코딩을 진행했으며 100이 나오는 경..
BaekJoon 16236번: 아기상어(C++)
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이법 1) BFS와 구현이 합쳐진 문제였으며 고려해야할 예외처리가 많아서 힘들었던 문제이다. 2) 현재 아기 상어의 크기보다 작은 값이 있는 경우 탐색을 계속 진행하며, bfs를 반복하며 탐색을 진행했다. 작은 값이 존재하나 갈수 없는 곳이 존재하면 탐색을 중지하였다. 3) 현재 아기 상어의 크기만큼 아기 상어가 물고기를 먹으면 사이즈가 증가하는 것을 꼭 고려해 주어야 하며 아기 상어가 ..
BaekJoon 14891번: 톱니바퀴(C++)
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이법 1) 깔끔한 풀이를 기대하고 들어왔다면.. 죄송하지만 해당 풀이는 도움이 크게 되지는 않습니다. 2) Deque을 사용하면 더 쉽게 풀 수 있다는 것을 문제를 보고 눈치 챘지만, 안 쓴지 너무 오래되었으며 검색 없이 정해준 30분이라는 시간 제한 내에 어떻게든 풀기 위해 조건을 빡 구현하여 배열로 문제를 풀었습니다. 3) checkOne, CheckTwo, CheckThree 라는 bo..
BaekJoon 18111번: 마인크래프트(C++)
https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이법 1) 시간초과를 고려하여 이분 탐색을 실시했으나 실패하여 BruteForce로 문제를 해결하였다. 2) 값을 입력 받음과 동시에 값 중 가장 작은 값과 가장 큰 값을 지정하였다. 3) 이후 for문을 통해 가장 작은 값 부터 가장 큰 값까지 search를 실시하여 가능한 경우의 수 중 가장 시간이 적게 걸리는 것과 그 중 가장 높이가 가장 높은 것을 출력하였다. 4) 이를 파악 시에는 인..