알고리즘/BOJ 썸네일형 리스트형 15649번 15649번 - N 과 M (1) 개인적으로 이런 간단한 기본 문제가 있으면 좋겠다고 생각했는데 문제가 생겼다. 문제를 풀다보면 응용해서 써야하는 자주 접하는 기본 문제인 것 같다. 그래서 재귀를 이용해서 풀었고 , 비트연산을 이용해보기도 하였다. 12345678910111213141516171819202122232425262728293031323334353637#include int n, m;int num[9];bool used[9];void go(int cnt){ if (cnt == m) { for (int i = 0; i 더보기 5427번 5427번 - 불 BFS 문제 두가지 요인을 같이 BFS를 통해서 움직여줘야 한다. 큐에 움직이는 사람과 번지는 불을 같이 넣으면서 함께 이동시켜줘야 한다. 그래서 나는 일단 사람을 이동시키고 불을 이동시키는 방법으로 BFS를 구현해주었다. 큐는 FIFO 이라는 점을 이용하여 일단 사람의 위치를 큐에 먼저 넣어주고, 그 다음에 불의 위치를 큐에 넣어주었다. 그리고 while 문 안을 돌면서, 큐에서 꺼낸 값이 사람의 위치인가 불의 위치인가를 파악했다. 사람의 위치라면, for문을 돌면서 상하좌우에 사람을 이동시킨다. 단 사람은 ' . ' 이라는 빈 공간으로만 움직일 수 있다. 그리고 만약 사람의 위치일때 map의 가장자리에 존재한다면 탈출 할 수 있다는 뜻이므로 cango를 true로 만들고 while .. 더보기 1331번 1331번 - 나이트 투어 시뮬레이션 문제. 주어진 순서대로 나이트가 움직여야 하기 때문에, 입력을 받으면서 map 변수에 0번부터 35번까지 순서를 입력해주었다. 그 후에 0~35번까지 for문을 돌면서 , 각 각의 나이트가 움직일 수 있는 8가지 방향을 체크했다. 시작점인 0번째 나이트가 8가지 방향을 돌면서, 다음으로 이동해야할 1번 칸이 존재하면 움직인다. 1번째 나이트가 8가지 방향을 돌면서, 다음으로 이동해야할 2번 칸이 존재하면 움직이다. . . . 마지막 35번째 나이트가 8가지 방향을 돌면서, 다음으로 이동해야할 0번째 시작점이 존재하면 움직인다. 이런식으로 문제를 풀어나가면서 만약 탐색해서 다음 칸을 찾지 못하면 INVALID 가 된다. 하지만 마지막까지 다 탐색할 수 있다면 VALID.. 더보기 1952번 1952번 - 달팽이2 간단한 시뮬레이션인 줄 알았는데, 은근히 뭔가 안돼서 계속 고쳤다. 일단 처음에 메인 함수의 while 문에서 코드를 간결하게 하려고 해보았지만, x+dx[dir] 이 사용되는 곳에 따라 바뀌어야 하기 때문에 if 문에서 x+dx[dir], y+dy[dir] 부분과 if문 벗어나서 그 부분이 다르기 때문에 한번 다시 써줘야했다...최적화 안됨 그리고 범위가 벗어나는 경우를 처음에는 무조건 돌면서 가운데로 들어오기 때문에 map[x+1][y], map[x-1][y], map[x][y-1], map[x][y+1] 이 모두 1이 되는 지점에서 break를 걸어주면 된다고 생각했다. 하지만 생각해보니 1,1 , 3,1 처럼 방향 변화가 전혀 없을 수 있는 map 이 존재했기 때문에 그런걸.. 더보기 6378번 6378번 - 디지털 루트 정답률에 비해서 생각보다 쉬운 문제였다. 문제의 핵심은 1000자리의 숫자는 정수형 변수로 표현할 수 없기 때문에 문자열로 표현한다는 점인 것 같다. 따라서 string 객체로 해당하는 문자를 받아들이고, 그 문자를 한 문자씩 읽어들이면서 값을 계산하는 과정을 반복하면 된다. getNum 함수에서 for문을 돌면서 각 자리의 수를 더해서 ret 라는 정수 배열에 넣어준다. 그리고 ret 라는 값이 10 이상이면 다시 ret 값을 string 으로 바꾸고 재귀함수를 구현한다. 만약 ret 값이 원하는 한자리 수 값이 되면 리턴하면서 출력한다. ###to_string : 헤더 파일에 있는 int 형 변수를 string으로 변환시켜주는 함수 12345678910111213141516.. 더보기 2636번 2636번 - 치즈 이번 문제는 DFS를 이용해서 문제를 풀 수 있었다. 기본적인 아이디어는 치즈가 아닌 부분을 DFS로 탐색하면서, 치즈가 아닌 부분의 근처에 있는 치즈만을 2로 변경시켜준다. DFS가 종료된 이후에는, 체크된 2의 값들을 카운트하고, 다시 0으로(치즈가 사라졌으므로) 값을 변경시킨다. 이런식으로 2로 변경된 치즈가 없을 때까지 while문을 진행하면 시간값과 치즈갯수를 구할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include using namespace .. 더보기 12761번 12791번 - 돌다리 간단한 BFS문제 나올 수 있는 8가지 경우를 큐에 포함시켜서 문제를 풀면된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include#includeusing namespace std; int a, b, n, m;int dist[100001];bool check(int now){ return (now = 0 && dist[now]==0);}int main(){ cin >> a >> b >> n >> m; queue q; q.push(n); dist[n] = 0; while (!q.e.. 더보기 15683번 15683번 - 감시 상반기 대기업 SW 역량 평가로 나왔는데, 풀었던 문제였다. 브루트포스로 하나씩 문제를 쪼개면 풀 수 있는 문제였다. 나는 실제 시험장에서 fill_map을 makeMap 함수안에 각각 구현해서 코드가 굉장 히 더러웠었던 기억이 난다ㅋㅋㅋ 일단 모든 CCTV를 90도로 돌려가면서, 최소의 사각지대를 만들어야 한다. 그래서 재귀함수로 모든 케이스를 탐색하도록 구현했다. 근데 일단 조금이라도 속도를 줄이고자, 90도로 돌렸을 때 나올 수 있는 가짓수를 dir_num 배열에 넣어줬다. CCTV 1번은 4방향이 모두 다르다, 하지만 CCTV 2번 같은 경우에는 2가지 경우만 존재하고, 5번 같은 경우에는 1가지 경우만 존재한다. 그리고 이를 통해서 getMIN 함수에서 for문으로 몇가지 .. 더보기 이전 1 2 3 4 5 6 ··· 40 다음