Algorithm/문제 풀이62 [알고리즘] 가르침 (백준 1062번) 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백트랙킹을 통한 완전탐색을 하는 문제다. 비트마스크와 배열 둘 중 하나를 이용해서 풀 수 있다. 2개의 메모리, 시간 효율 차이는 거의 없다. 그냥 똑같은 수준이다. Solution 공통적으로 행해야 할 것은 우선 가르칠 수 있는 단어가 5개 미만이면 어떤 글자도 읽을 수 없다. 만약 5개 이상이라면 남극언어의 기본 시작단어, 끝단어를 이루고 있는 알파벳들 'a c t n i' 5가지부터 추가시키고 시작한다. 1. boolean 배열로 가르침 여부 체크 .. 2020. 10. 3. [알고리즘] 퍼즐 (백준 1525번) 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 비트마스킹 문제를 찾고 있었는데 비트마스킹으로 풀기엔 시간이 너무 오래걸려서 그냥 배열을 이용해서 풀었다. BFS를 이용해야 하는 문제다. Solution 우선 고려해야할 것은 1차원 배열의 index와 2차원 배열의 row, column을 왔다갔다 해야되는 것이다. 여기서 핵심은 visited, 즉 방문 처리를 무엇으로 할 것이냐 인데 난 int형 배열을 이용해서 처리했다. 문자열을 사용하는 사람도 있는데 문자열로도 성공은 하지만 메모리 사용량 측면에선 int형 배열이 훨씬 효율적이다. 1. 전역 변수 static HashSet visi.. 2020. 10. 3. [알고리즘] 최소비용 구하기 (백준 1916번) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 한 시작점에서 나머지 노드까지의 최소 거리를 구하는, 전형적인 다익스트라 문제다. 사실 다익스트라 문제는 이번이 처음 풀어보는데 생각보다 시간이 오래걸렸다. 계속 8%에서 넘어가질 않아서 한참 고민하고 있었는데 알고 보니 버스는 단방향인데 나는 양방향으로 생각하고 문제를 풀었다.... Solution dist 배열에서 시작점 dist[start] = 0이고 나머지는 무한대로 초기화한다. 각 노드의 edge 정보들을 저장해놓는다... 2020. 10. 2. [알고리즘] 구슬 탈출 2 (백준 13460번) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 삼성 기출 문제이다. 삼성 기출에서 자주 나오는 맵에서 물체들을 동시에 움직이는 시뮬레이션 유형이다. BFS를 활용하여서 빨간 공이 구멍에 빠지는 최단 시간을 알아내야한다. Solution 시뮬레이션 문제 중 물체를 동시에 움직이는 문제는 항상 까다롭다. 이 경우는 보드를 기울일 때 고려해야할 상황이 많다. 상하좌우로 기울일 때, 어떤 공을 먼저 움직여야 동기화가 될 지 움직이다 다른 공을 만나면 멈춰야 됨 움직이.. 2020. 10. 2. 이전 1 ··· 3 4 5 6 7 8 9 ··· 16 다음
