Coding_Test_C++
BaekJoon 18352번: 특정 거리의 도시 찾기(C++)
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이법 1) 다익스트라를 활용한다면 쉽게 풀 수 있는 문제였다. 2) 들어올 수 있는 입력 값중 N번까지의 도시가 300,000개가 될 수 있기에, 정적 배열을 사용하기 보단 동적 배열을 활용하여 문제를 풀어 주었다. (N이 작은 입력 값이 존재할 경우 메모리의 낭비가 발생할 수 있기 때문이다.) 3) X에서 시작한 각 no..
Programmers Level 2: 괄호 변환(C++)
https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 풀이법 1) 재귀와 구현을 적절히 섞은 Kakao스러운 문제였다. 2) [용어의 정의] 파트에 구현해야 할 부분이 상세히 적혀 있으므로, 이를 따라 간다면 쉽게 풀 수 있는 문제였다고 생각한다. 3) 들어오는 문자열 p에 대해서 for문으로 탐색하며, left와 right 값을 비교하였다. 이 둘이 같아 지는 경우가 '균형 잡힌 괄호 문자열'이 되는 경우이기에, ..
Programmers: 완전탐색 > 소수 찾기(C++)
https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 풀이법 1) DFS 기반의 알고리즘을 활용하여, 완전 탐색을 통해 문제를 해결 하였다. 2) 첫 번째 값으로는 0이 들어갈 수 없기에 이 부분을 구현해 주었으며, 방문하지 않은 노드들을 방문하며, size를 키워 모든 경우의 수를 탐색하였다. 3) 겹치는 숫자가 없게 담긴 동적 배열 vec에서 소수의 개수를 확인해 주었고 정답을 얻을 수..
BaekJoon 2628번: 종이 자르기
https://www.acmicpc.net/problem/2628 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 풀이법 1) 규칙을 찾아 구현함으로서 정답을 얻을 수 있던 문제이다. 2) 가로로 4번 선을 자를 경우, 행 기준 4번 보다 작은 배열의 값들을 모두 1씩 증가시키는 방식으로 문제를 해결하였다. 문제에서 주어진 다음의 예시의 경우 위의 풀이 방식을 활용하면, 10 8 3 0 3 1 4 0 2 4 4 4 4 3 3 3 3 3 3 4 4 4 4 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 ..
BaekJoon 2615번: 오목(C++)
https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 풀이법 1) 문제에서 주어진 정의에 따라 알맞게 구현하는 것이 가장 핵심이었던 문제이다. 세로로 일자인 것을 제외하고는 가장 왼쪽에 있는 돌의 위치를 출력해야 한다는 점과, 육목(6개가 연결되는 것)이 되면 안된다는 점을 제대로 인지해야 풀 수 있는 문제였다. 2) dfs()기반의 재귀 알고리즘을 사용했지만, visited배열과 같은 방문한 곳을 check하지 않았기에 제대로된 dfs알고리즘을 사..
BaekJoon 2635번: 수 이어가기(C++)
https://www.acmicpc.net/problem/2635 2635번: 수 이어가기 첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다. www.acmicpc.net 풀이법 1) 실버 수준의 문제로 구현이 어렵지 않으며 brute force로 답을 찾으면 되는 문제이다. 2) 들어 오는 입력 값이 30000 이하의 양수이므로, 이보다 작은 값을을 for문을 통해서 반복시켰으며 음수가 나오는 경우 동적 배열에 새로운 값을 넣는 것을 중단 시켰다. 3) 이후 만들어진 배열의 크기와 현재 최대 사이즈를 비교하여, 만들어진 배열의 크기가 더 큰 경우, 최종 배열에 담고, 사이즈를 갱신시켰다. #include #include #include #include #include #in..
BaekJoon 14500번: 테트로미노(C++)
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이법 1) 배치할 수 있는 총 경우의 수가 19가지가 되므로 일일이 쓰는 것 보다는, DFS 기반의 알고리즘을 활용하는 것이 좋다. 일일이 구현하다가, 지쳐서 다른 분들의 블로그를 찾으니 크기가 'ㅜ'모양을 제외하고는 모두 크기가 4인 DFS로 구현하면 가능하다는 점을 확인할 수 있었다. 2) 재귀 기반의 DFS로 'ㅜ'를 제외한 다른 모양들의 최대 합을 구하려 하였고, 'ㅜ', 'ㅏ', 'ㅓ'..
BaekJoon 5014번: 스타트 링크(C++)
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이법 1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다. 2) 항상 현재 stairs 기준으로 내려가서 올라가거나, 올라간 후 내려가는 경우를 고려해야 하기에, 하나의 stairs에 가능한 down과 up 을 모두 고려해 주어야 풀 수 있다. 3) 범위를 고려하여 항상 1보다 크고 f보다 작은 칸을 이동하는 것으로 코딩을 진행하였다. #include #include #i..
BaekJoon 2636번: 치즈(C++)
https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이법 1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다. 2) 입력값인 arr배열에 직접적으로 값을 변경하면 bfs 알고리즘 내에서 문제가 생길 수 있기에 arr2배열을 만들어서 바뀌는 입력값을 일시적으로 담았다가 추후에 다시 arr배열로 바꾸어 주었다. 3) 모든 치즈가 녹는 경우를 확일할 수 있는 allVisited 함수를 만들어 두어 이를 while문에 활용하였..
BaekJoon 2589번: 보물섬(C++)
https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 풀이법 1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다. 2) BFS알고리즘을 기준으로, x,y,count 변수를 각각의 queue에 담아 주었다. 시작점을 기준으로 가장 멀리 있는 값을 temp라는 변수에 갱신시키며 해당 BFS 알고리즘에서 가장 큰 값을 가져오려 하였다. 3) 시작점을 어디에 잡는지가 중요한 문제이기에, 들어갈 수 있는 모든 'L'(땅을 설치..