전체 글
Programmers : 타겟넘버(C++)
programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) BFS를 이용하면 쉽게 풀 수 있는 문제이다. 2) value와 level을 이용해서 dfs를 순환 시킨다. 이때 level이 numbers 배열의 size와 같아질 때, target과 value의 값이 같으면 answer를 증가 시킨다...
2017 팁스다운: 짝 지어 제거하기
programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 문자가 연속되는 경우에만 이를 삭제한다. 풀이법 1) 효율성과 정확성을 고려한다면 stack을 이용하면 문제를 쉽게 풀 수 있다. 2) 스택의 맨 위 값과 새로 들어오는 값을 비교하여 두 값이 같으면 pop, 다르면 push 해준다 3) 최종 stack의 크기가 0이면 모두 짝 지어서 제거된..
2019 카카오 개발자 겨울 인턴십 : 크레인 인형 뽑기 게임(C++)
programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) 아래에서 부터 쌓인다는 특징을 기억해야 한다. 같은 열 기준으로 행의 값이 커질 수록 0이 아닌 item이 있을 것이니 이를 for문을 이용해서 확인해야 한다. 2) 뽑고 난 후 원래 배열에서 해당 칸의 값은 0으로 초기화 해주어야 한다. 3) 2개가 연속된 경우 지우는 것을 구현하기 위해 stack을 활용하면 문제를..
BaekJoon 2206번: 벽 부수고 이동하기
풀이법 1) BFS를 사용해서 풀 수 있는 문제이지만, 벽을 하나 허물 수 있다는 점에서 BFS가 익숙치 않은 사람들에게는 어려움을 줄 수 있는 문제이다. 2) 핵심은 이미 벽을 허물었는가를 확인하는 것 & visited 배열을 3차원으로 만드는 것이다. 3) visited 배열을 2차원으로 만들 경우 벽을 허물어서 지나간 곳과, 벽을 허물지 않았을 때 갈 수 있는 곳이 겹치게 되면, queue에 새로운 값을 push 할 수 없게 된다. 헷갈려 할만한 부분에 대해 주석을 자세히 달았으니, 이해를 기반한 공부에 도움이 되길 바란다. #include #include #include #include using namespace std; int n, m; int arr[1001][1001]; int vx[4] ..
BaekJoon 1697번: 숨바꼭질
풀이법 1차원 배열과 BFS를 이용하면 문제를 쉽게 풀 수 있었다. 정확한 조건에 대한 이해가 수반되어야 문제를 풀 수 있기에 힌트에 적힌 5-10-9-18-17 부분을 이해하는 것이 중요하다. #include #include #include #include using namespace std; int arr[100001]; bool visited[100001]; int n, k; int minimum=100001; void bfs(int n) { visited[n] = true; queueq; q.push({ n, 0 }); while (!q.empty()) { int now = q.front().first; int count = q.front().second; q.pop(); if (now == k)..
BaekJoon 4179번: 불!
풀이법 BFS를 이용한다면 정답의 실마리를 찾을 수 있는 문제이나, 낮은 정답률이 말해주듯 난이도가 꽤 있는 편이다. 두 번의 bfs를 이용하여, 불이 이동하는 경로를 먼저 구한 후, 지훈이가 이동할 수 있는 경로를 비교하는 방법으로 문제를 해결했다. 해당 문제의 핵심 logic과 검색을 통해 쉽게 구할 수 있는 Hidden TC는 source code 밑에 기술하였다. #include #include #include #include using namespace std; bool visited[1001][1001]; bool visitedF[1001][1001]; char arr[1001][1001]; int ansj[1001][1001]; int ansf[1001][1001]; int vx[4] = {..
BaekJoon 7576번: 토마토
풀이법 BFS를 이용하여 문제를 해결하는 것이 가장 쉽게 문제를 해결할 수 있는 방법이다. countNum 변수를 이용하여 최대 걸리는 시간을 계산한다면 쉽게 해결할 수 있다. #include #include #include using namespace std; int vx[4] = { 1,0,-1,0 }; int vy[4] = {0,-1,0,1}; int arr[1001][1001]; bool visited[1001][1001]; int n, m; int countNum = 0; void bfs() { queue q; for (int i = 1; i > m >> n; for (int i = 1; i arr[i][j]; } } github.com/pearlcrum/CodingTest/tree/main p..
BaekJoon 2178번: 미로 탐색
풀이법 BFS를 이용해서 문제를 해결하였다. 움직일수 있는 count를 queue의 매개변수로 넣어서 계산을 편히 하도록 설계하였다. #include #include #include using namespace std; int vx[4] = { 1,0,-1,0 }; int vy[4] = {0,-1,0,1}; int arr[101][101]; bool visited[101][101]; int n, m; void bfs(int x, int y, int count) { queue q; visited[x][y] = true; q.push({ x,{y,count} }); while (!q.empty()) { int tempx = q.front().first; int tempy = q.front().second.f..
BaekJoon 1926번: 그림
풀이법 BFS를 이용해서 문제를 해결하였다. 기초적인 공식과 같은 풀이 알고리즘을 알고 있다면 어렵지 않게 풀 수 있는 문제이다. (X가 행, Y가 열임을 기억해서 범위를 설정해주는 것이 중요하다) #include #include #include using namespace std; int n, m; int arr[501][501]; bool visited[501][501]; int vx[4] = { 0,1,-1,0 }; int vy[4] = { -1,0,0,1 }; int ea; //그림의 개수 int area;//넓이 void bfs(int i, int j) { ea++; visited[i][j] = true; queue q; int tempArea=0;//비교를 위한 tempea; q.push({ ..
BaekJoon 2193번: 이친수
풀이법 규칙을 구하기 위해 각 항의 개수를 트리 형태로 만들어보았다. 1 1 2 3 5 8 과 같은 규칙을 발견할 수 있었으며, 이는 곧 피보나치 수열에 해당한다. 배열의 크기가 90이상일 수 있으니 꼭 long long형으로 선언해야 한다. #include #include #include using namespace std; int n; long long arr[91]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; arr[1] = 1; arr[2] = 1; for (int i = 3; i