자료구조&알고리즘/알고리즘 - 기업 코딩 테스트
-
[알고리즘 문제 풀이][DFS] 백준 1012번 - 유기농 배추자료구조&알고리즘/알고리즘 - 기업 코딩 테스트 2021. 10. 9. 16:24
백준 1012번 유기농 배추입니다. (삼성 SW 코딩 테스트 유형 - DFS) - 문제 설명: https://www.acmicpc.net/problem/1012 - 문제 풀이: 본 문제는 기업 코딩 테스트 유형에서 많이 보이는 가벼운 함정이 있으므로, 문제 풀이를 보기 전에 먼저 문제를 풀어볼 것을 추천드립니다. 아래와 같은 배추밭이 있을 때, 배추 (1) 가 연속된 곳에는 지렁이를 하나만 두면 됩니다. 그래서 아래 예시의 경우, 뭉쳐있는 1이 5군데가 있으므로 5마리의 지렁이가 필요하게 됩니다. 1100000000 0100000000 0000100000 0000100000 0011000111 0000100111 연속된 배추를 구해야하기 때문에 본 문제는 DFS 로 풀이하면 됩니다. 왼쪽 위에서부터 탐색..
-
[알고리즘 문제 풀이][시뮬레이션] 백준 1194번 - 달이 차오른다, 가자.자료구조&알고리즘/알고리즘 - 기업 코딩 테스트 2021. 9. 27. 23:44
백준 1194번 달이 차오른다, 가자. 문제입니다. (삼성 SW 코딩 테스트 유형 - BFS) - 문제 설명: https://www.acmicpc.net/problem/1194 - 문제 풀이: 미로의 출발점 (0) 에서 도착점 (1) 까지 최단 거리를 구하는 문제입니다. 벽 (#) 으로 막힌 곳은 지나갈 수 없습니다. 이 문제에서 가장 중요한 것은 열쇠 (a ~ f) 를 먹어야만 문 (A ~ F) 를 열 수 있다는 것입니다. 아래의 예시를 보면 출발점 (0) 부터 시작해서 a 열쇠를 먹고 A 문을 연 후에 c 열쇠를 먹고 C 문을 열어야 도착점 (1) 로 갈 수 있습니다. ※ 풀이시 주의해야할 점은 도착점 (1) 이 단 하나만 존재하는 것이 아닙니다. 여러곳이 존재하는데 그 중 가장 빨리 도착하는 곳을 ..
-
[알고리즘 문제 풀이][시뮬레이션] 백준 3954번 - Brainf**k 인터프리터자료구조&알고리즘/알고리즘 - 기업 코딩 테스트 2021. 8. 23. 23:35
백준 3954번 Brainf**k 인터프리터 문제입니다. (GCPC 2012년도 B번 문제 / 삼성 A형 기출 복원문제) - 문제 설명: https://www.acmicpc.net/problem/3954 - 문제 풀이: 본 문제는 Brainf**k 언어로 구성된 문장과 인풋이 들어오면 그것을 해석하는 인터프리터를 구현하는 문제입니다. 복잡한 알고리즘이 아닌 스택 & 구현 능력이 필요한 문제였습니다. 다만 문제에서 해석이 어려운 부분은 이 문제에서 정의하는 "무한루프" 가 무엇인가인데, 본 문제의 질문검색 게시판의 토론 결과를 보면 특정 시점부터 탈출하지 않는 가장 안쪽 루프가 됩니다. [[]] 이런 식으로 루프가 중첩된 경우, 가장 바깥쪽 루프는 안쪽 루프에 갇혀 영원히 탈출할 수 없지만, 정확한 무한루..