Coding_Test_C++
BaekJoon 11779번: 최소비용 구하기 2(C++)
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이법 1) m개의 반복을 통해 들어갈 값들은 단방향 그래프임을 잊지 말자 2) a에서 b까지 가는 버스의 값이 여러 개 주어질 수도 있다. (min 함수를 활용하여 더 적은 것을 입력 값으로 활용하는 것을 배제하면 7%쯤에서 error가 발생한다.) 3) 다익스트라 알고리즘을 활용하여 최소 비용을 구해야 하는 문제이다. 기존의 다익스트라 문제와 달리 경로를 구해야..
BaekJoon 2573번: 빙산(C++) + 문제 오류
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제의 예제인 그림 3번에 오류를 발견했다. 그림 3은 다음과 같이 설명되어 있으나 정확한 정답으로는 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 4 0 0 0 0 3 2 0 0 0 0 0 0 0 0 0 0 위의 정답과 같은 세 덩이의 배열이 되어야 한다. 풀이법 1) while 반복을 통해, 덩이의 차이 없이 완전히 녹은 경우를 파악하여 0을 출력해야 한다. (allMe..
BaekJoon 1600번: 말이 되고픈 원숭이(C++)
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이법 1) BFS를 활용하는 문제이며, 문제에서 주어진 w,h 값이 정확히 무엇인지를 먼저 확인하는 것이 중요하다 2) 체스의 knight 처럼 움직일 수 있는 배열과, 상하 좌우로 움직일 수 있는 배열을 따로 만들어 주었다. int vx[4] = { 1,0,0,-1 }; int vy[4] = { 0,1,-1,0 }; int bx[8] = {-1,-2,-2,-1,1,2,2,1};..
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) 두개의 배열과 bfs를 활용하면 쉽게 풀 수 있는 문제이다. 2) 현재의 값을 queue에 차근 차근 넣고, now+u>f 일경우 continue로 배열에 넣지 않는다. 3) now-d f >> s >> g >> u >> d; bfs(); }
BaekJoon 7662번: 이중 우선순위 큐(C++)
https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이법 1) 제한시간이 6초이기에 넉넉하다고 생각하여, for문이나 정렬을 하게 되면 무조건 시간 초과가 나는 문제이다. 2) 문제를 해결함에 있어 중복이 가능하고 RBTree의 형태를 가진 set 자료형을 사용하였다. 3) 값을 insert하게 되면 오름차순으로 알아서 정렬이 되기에, set 자료형을 사용한다면 쉽게 문제를 풀 수 있다. set 자료형 사용 시 주의 사항 auto it=set..
BaekJoon 18870번: 좌표 압축(C++)
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이법 1) 두개의 배열을 만들어서 좌표를 압축하기 위해 sort 알고리즘을 두 번 반복하여 문제를 해결했다. 2) 첫번째 입력 값에 대하여, 현재의 값과 index를 담을 수 있는 배열을 만들어 현재의 값을 오름차순으로 정렬시켰다. 3) 두번쨰 배열의 경우, 오름차순 된 첫번째 배열의 크기에 맞게 index를 새로 부여하여 새롭게 만들어야 하는 ..
BaekJoon 1620번: 나는야 포켓몬 마스터 이다솜(C++)
https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이법 1) Map 자료형을 두개 사용하면 쉽게 풀 수 있는 문제이다. 겹치지 않는 string 배열이 두개 있다고 생각하여, map map를 만들어 둠으로서 시간복잡도에서 벗어나지 않게 코딩할 수 있었다. 2) map.count() 함수를 이용하여 해당 key 값에 맞는 value 값이 있는지 확인하여, 입력에 따라 다른 map 자료형에 접근하여 값을 꺼내올 수 있게..
BaekJoon 2096번: 내려가기(C++)
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이법 1) 메모리의 제한이 4MB이므로 최소한의 배열을 이용하여 풀어야 하는 DP 문제이다. max와 min 모두 2차원의 3x2배열을 만들어서 최대 값과 최솟 값을 구하였다. 2) 자세한 이해는 코드를 보며 공부하는 것이 더 효율적이리라 생각한다. (1차원 배열로는 min max 값을 정확하게 구할 수 없으므로 나머지 연산자를 활용하여, 최대와 최솟값을 구해두었다.) 점화식을 잘못 세운 분들을 위한 Hidd..
Programmers Level 3: 멀리 뛰기
https://programmers.co.kr/learn/courses/30/lessons/12914# 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 풀이법 1) DP를 활용하면 쉽게 풀 수 있는 문제이다. (queue를 활용하여 풀 수 있으나 시간 초과에 유의해야 한다.) 2) 개인적으로 kakao 프로그래머스 level2 문제보다 쉽다고 생각했기에, 오래 걸리지 않고 문제를 풀 수 있었다. arr[1]=1 arr[2]=2 arr[3]=3 arr[4..
Programmers Level2: 메뉴 리뉴얼
https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 풀이법 1) Map 자료형과 조합(Combination)을 이용한 구현 문제이다. 2) map 자료형에 몇 번의 해당 값이 나왔는지를 확인할 수 있도록 하고 course 배열 안의 값에 따라 이를 확인하여 result를 만드는 과정이 중요한 부분이었다. string s = orders[j]; sort(s.begin(), s.end()); vector ind; fo..