IT 개발 돼지의 일상

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo "DFS와 BFS 를 이용한 단순 구현, 깊은 복사" 벽돌이 쌓여있는 격자에서 W의 열 중에 깰 수 있는 벽돌들의 경우를 DFS를 이용하여 탐색한다. BFS를 이용해 선택한 벽돌의 숫자 만큼 상,하,좌,우 벽돌을 탐색하여 해당 턴에 삭제될 벽돌들을 넣고 벽돌을 삭제 시킨다. 그리고 공중에 떠 있는 벽돌들을 아래로 내려준다. 이 과정에서 나는 깊은 복사를 사용했다. 시뮬레이션 중에 백트래킹이 힘들 경우에는 깊은 복사를 사용하는 것도 좋은 방법 인 것 같다. map 의 크기가 작다면 옅은 복사나 깊은 복사나 그렇게 큰 차이가 없다고 ..

출저 : https://www.acmicpc.net/problem/2151 "다른 조건을 최소화 하는 경우를 찾으려면 우선순위 큐 혹은 다익스트라!" 해당 문제와 비슷한 유형의 문제들이 많다. 목적지 까지 가는 길에 무엇을 한 최소 횟수를 구하는 등의 문제들이 있다. 다익스트라로 풀거나 우선순위 큐로 풀 수 있다. 나는 우선순위 큐를 사용해서 풀었다. 맨 처음에는 우선순위를 그냥 '-1' 과 '0' 으로만 주어서제대로 탐색이 되지 않았다. 비교 대상과의 차이를 우선순위로 두어서 내가 원하는대로 탐색하게 할 수 있었다. 우선순위 큐를 쓸 때는 디버깅이 힘든 것 같다. 우선순위 체크를 할 때 매우 신중히 해야 할것. 더해서 목적지 까지 찾아가는 문제의 경우 어떻게 하면 중복되는 부분을 체크하고 줄일 수 있는..

출저 : https://www.acmicpc.net/problem/3108 "연결 요소의 개수. 빠진 조건이 없나 다시보자. 그리고 아이디어" 해당 문제를 하루 동안 붙잡고 있었다. 어떤 문제든 주어지는 조건을 잘 봐야겠다. 이 문제는 연결 요소의 개수를 구하는 문제로 처음에는 각 좌표에다가 +500 씩해서 모든 직사각형을 map에 체크하려고 했다. 하다보니 하나의 사각형이 내포되면서 접하고 있는 사각형 두개의 경우 탐색이 불가능한 것을 알았고, *2를 해서 벌려 놓을까 하다가 비효율적인 것 같아서 아래 방법으로 풀었다. BFS를 통해서 연결된 직사각형을 구한다. 이 과정에서 각각의 직사각형들이 서로 연결되어 있는지 확인해야 하는데, 나는 연결 되어 있 지 않은 경우를 체크했다. 비교는 x1,y1,x2,..

출저 : https://www.acmicpc.net/problem/9177 "조금더 빨리 돌아갈 수 있게 최적화를 시키자." 두 개의 문자열을 가지고 다른 문자열을 만들 수 있는지 없는지 확인하는 문제이다. 나는 DFS로 문제를 풀었다. 조건들이 문제를 굉장히 쉽게 만들 고 있었다. - 순서를 지켜서 문자열을 조합해야 하고- 모든 문자열을 사용해야 한다. 코딩을 다 하고 돌려보니 시간초과가 났다. 이상하다... 굉장히 심플해서 뭔가 더 성능을 높일만한 부분이 없는거 같은데 라고 생각하고, 이렇게 풀면 안되나?라고 생각했다. 테스트 케이스를 만들어서 돌려보다가 문자열 A, B에 없는 문자가 C에 들어 있을 때, 재귀 횟수가 굉장히 높았다. 그래서 set을 이용하여 문자열의 포함 여부를 DFS 실행 전에 미..

몇일전에 남이섬을 놀러갔다왔어요. 가평 근처는 자주 가봤었는데, 남이섬은 처음이라 은근히 기대했지만, 결론부터 말하자면, 사실 뭐 별거 없더라.. ^^;;; 우선 배를 탑니다. 성인 일반인이 13,000 원 정도 했던 것 같습니다.원래 짚트랙을 타고 들어가려고 했는데 사람이 많아서 인지, 원래 스케쥴이 있는건지 한 시간 반 대기 더라구요. 가격도 입장료 포함이긴 했지만 인당 4만원 정도로 비싸서 깔끔하게 포기. 둘이 6만원이면... 회를 먹겠따.. 남이섬 안에도 은근히 먹을게 많았슴다. 파전도 있었고, 스파게티, 떡 별거 다있어요. 아 그리고 선착장 입구에 여자 화장실은 겁나게 붐비던데, 남이섬에서 선착장을 바라보고, 오른쪽 편에 있는 매점 옆에도 화장실이 있더라구요. 사람들 다 모르는거 같았슴다. 엄청..

출처 : https://www.acmicpc.net/problem/2933 "조건을 잘 읽어보자. 슈발" 이 문제때문에 하루를 다날렸다. 문제를 이해하는데만 해도 굉장히 오랜 시간이 걸렸다. 클러스터가 뭔데... 땅에 붙어 있는 미네랄에서 막대로 인해 부셔져 공중에 둥둥 떠 있는 미네랄 조각을 클러스터라 한다. 얼음 덩어리는 상,하,좌,우가 인접한 얼음의 집합이다. 그냥 막대를 던져 얼음 덩어리를 깼을 때, 생기는 각각의 얼음덩어리 중 상,하,좌,우가 지면과 맞닿아 있지 않는 얼음덩어리를 공중에 있다고 한다. 이렇게 공중에 있는 얼음덩어리는 중력에 의해 모양을 유지하며 아래로 떨어지게 되는데, 지면에 닿거나, 다른 얼음 덩어리를 만날 때 까지 떨어진다. (단, 떨어지는 얼음의 모양은 변하지 않는다. 즉,..

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo "시뮬레이션" 단순 시뮬레이션 문제로써 각 지점에서 최대 배터리 충전 용량을 구하는 것이다. 여기서 중요한 것은 움직이는 매 순간마다 사용자 A와 B가 어떤 BC를 선택해야 배터리 충전 용량이 최대가 되는지를 판별하는 것이다. path[2][A] 배열을 만들어서 매 시간마다 사용자 A 와 B 가 접근할 수 있는 모든 BC를 체크 한 후, getMax 라는 함수를 통해 A와 B가 선택 가능한 BC의 모든 조합을 조사해 그중에서 최대 배터리 충전량을 구하는 식으로 문제를 해결했다. 삼성 역량 테스트 문제의 시뮬레이션이 점점 복잡해지는..

출처 : https://www.acmicpc.net/problem/1953 "연결 요소들을 탐색해! 아이디어가 필요한 BFS" 해당 문제와 같이 이분( 팀을 나누거나, 선택/비선택 등 ) 하는 문제는 주로 비트마스크를 사용했다. 하지만 비트마스크는 비트 연산이므로 N이 32자리를 넘어서는 수에 대해서는 사용하지 못한다. 해당 문제의 경우 n이 최대 100이므로 비트마스크를 사용하지 못한다. 그렇다면 탐색을 통해 팀을 나누어 주어야 한다. 팀이 될 수 있는 경우로 모든 경로를 탐색한다면 오래 걸릴 듯 했다. 따라서 1번 노드를 시작으로 같은 팀이 절대 될 수 없는 것들을 먼저 분류 했다. 풀다 보니, 연결 요소의 개수를 탐색하는 것과 비슷했다. 1번 노드 부터 서로 싫어하는 노드들의 연결 요소를 따라 탐색..

출처 : https://www.acmicpc.net/problem/3187 "BFS 탐색" 해당 문제는 울타리로 나눠진 구역 안에 양과 늑대에 수에 따라 늑대가 죽는지 양이 죽는지 판별하는 문제로 단지영역나누기 와 비슷한 문제이다. 따라서 BFS 탐색으로 울타리가 아닌 지점을 모두 탐색하여 영역 내 양과 늑대의 수를 파악하고, 그 결과에 따라 양 > 늑대 이면 늑대를 죽이고, 양

출처 : https://www.acmicpc.net/problem/1613 "플로이드와샬!" 사건의 전후 관계에 대해 묻고 있다. 플로이드와샬은 음수 가중치를 계산할 수 있다는 점이 다익스트라와 다르다. 문제에서 친절히 -1,0,1 과 같이 힌트를 주었다. 주어지는 사건 x,y 에 대해 1 과 -1 을 부여한다. x y 순으로 주어진다면 아래와 같다. map[x][y] = 1 ;map[y][x] = -1; 그렇 다면 x y 두 사건의 관계를 x < y 라고 하자. 이렇게 되면 이제 우리가 찾아야 할 것은 x < (...) < y 의 관계를 만족하는 다른 사건들과의 관계 이다.이를 아래와 같이 계산한다. 가장 바깥쪽 for문이 우리가 찾을 (...) 에 해당한다. for (int a = 1; a j 라면,..