bfs 문제인데, 조금 응용이 필요한 문제였다. 풀이를 고민하다가 두가지 의문이 풀리지 않아서 다른 사람의 풀이를 참고하여 풀었다. 다음에 비슷한 유형의 문제에서는 잘 풀 수 있었으면 좋겠다. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 위에서 말한대로 풀지 못했던 두 가지 의문을 다음과 같이 풀었다. 1) 이 문제는 지금껏 풀었던 문제와 다르게 방문했던 곳을 다시 방문할 수도 있다. 열쇠를 구하러 갔다가 다시..
bfs문제 중 조금 어려운 수준에 속하는 문제다. 그동안 배열을 이용하면서 bfs를 수행했는데, 이 문제는 배열의 인덱스끼리 서로 내용을 바꾸어야하는 점에서 풀이를 생각해내지 못했다. 상하좌우 모두 방문해야하는데, 그때마다 배열의 내용을 바꾸면 다음 방문에 영향을 끼치기 때문이다. 매 방문마다 바뀌는 배열을 모두 저장할 수도 없는 것이고.. 그러면 어떻게 해야할까 생각을 하다가 풀지 못하고 다른 사람의 풀이를 참고하게 됐다. 배열이 아닌 간단하게 string을 쓰는게 흥미로웠다. https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc...
bfs문제를 풀던 중 조금의 응용이 있는 문제다. 다른 사람의 풀이를 참고해서 풀었기 때문에 정리해보려한다. www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net #include using namespace std; int n,m, secureCnt=0, result=2500; int lab[50][50] = {0,}; int visited[50][50]; int dx[4] = {0,-1,0,1}, dy[4] = {1,0,-1,0}; bool virus_visited[10..
요즘은 백준으로 유형별 문제를 풀고 있다. 그 중에서도 bfs(너비 완전 탐색)문제들을 풀고 있다. 처음에는 조금 쉬운 문제 위주로 풀어서 금방 풀었지만, 조금씩 어려운 문제를 풀다보니 조금 더 응용을 요하는 것 같다. 풀이 방법을 고민하다가 다른 사람의 풀이를 참고했다. 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이..
[ 프로그래머스 ] 정수 삼각형 (C++)
전형적인 DP 문제다. 뭐.. 어렵지 않게 풀었다. 나는 재귀 방식으로 풀었는데, 다른 사람의 풀이를 보니까 굳이 재귀방식으로 풀지 않아도 되는 방법도 있어서 정리해보려한다. 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다..
이제 Level3을 풀게되니까 난이도가 갑자기 올라갔다.. 이번 문제도 재귀함수와 set을 이용하여 풀어서 구현은 간신히 했으나 시간초과..😨 이제부터는 구현도 어렵지만 구현보다는 효율적인 알고리즘과 방법을 생각하는 것이 관건이다..! 그 방법을 생각해내면 금방 풀 수 있지만 그 방법을 생각하는 것이 어렵다 ㅠㅠ 그래서 이번 문제도 다른사람의 풀이를 조금 참고하여 풀었다. 일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀..
처음에 이 문제 풀 때 다 풀지 못했다. 이 문제는 효율성 테스트가 있어서 효율적인 알고리즘을 생각해야한다. 무식한 방법으로 매번 for문을 돌려서 체크하는 것은 정확성 테스트에서는 맞을 수 있어도, 효율성 테스트를 넘어가지 못한다. 이 문제를 풀려했던 날에 컨디션이 안좋았던 것도 있고, 내 실력이 조금 부족해서도 있겠지만 해결할 방법이 생각나지 않았었다. 결국 어떻게 문제에 접근해야하는지 카카오 해설을 참고했고, 쉽게 풀 수 있었다. 내가 스쳐 생각했던 방법과 비슷했지만 시도해보진 않았었는데 이게 맞았었다니..! 문제를 풀면 풀수록 해시 즉, unordered_map 을 사용해야하는 문제가 많다는 것을 느낀다. 카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종..
문자열과 정렬을 이용한 문제다. 클래스를 이용하여 어렵지 않게 풀었지만 그냥 정렬만을 이용하여 간단히 푼 풀이를 봤다. 충분히 나도 생각할 수 있는 수준이었다. 풀이를 보고 이해한 후에 다시 한번 풀어봤다. 다음에 비슷한 문제를 풀 때는 이렇게 간단하게 풀 수 있었으면 좋겠다. 그 때 생각이 났으면 좋겠다는 바람으로 정리를 해보려고 한다. 근데 속도는 내 코드가 훨씬 빠르게 나오는데 뭐가 더 좋은 코드인걸까..?! 어렵당 😨 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 ..