목록Algorithms (59)
혼종 꼬지마루
이 문제도 똑같이 구현을 잘 해줄 수 있느냐의 문제 입력받은 데이터는 이렇게 구성되어있다. N : 게임 스테이지의 갯수stages : 순서대로 각 유저가 몇번 스테이지에 있는지 입력받고 개인적으로 편하게 구현하기 위해 구조체 배열을 선언해서 만들었다 각 유저가 도달해 있는 stage 바로 앞까지는 해당 유저가 clear한 stage 이므로 check배열을 만들어서 그 스테이지를 끝낸 것으로 간주하고, 구조체 배열에는 그 스테이지에 머물러 있는 사람의 갯수를 넣어준다. 그리고 나서 단순히 for문을 돌면서 나눠주면 끝. 이 때 주의해야할 점이 모든 유저가 stage를 clear한 경우 그 실패한 유저가 0이므로 그대로 나눠주면 runtime error가 난다 이 문제는 단순히 if문 하나로 예외처리 해주면..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18KWf6ItECFAZN(이 글이 문제가 될 시 삭제하도록 하겠습니다.) 이 문제도 K번째 접미어 처럼 TRIE로 풀면 된다. TRIE를 사용하는 이유는 입력과 동시에 자동으로 정렬하는 효과를 볼 수 있기 때문이다. 순회하며 순서대로 탐색하기 때문이다. 일단 입력되는 문자열을 TRIE로 만들어 준다. 순회하며 처음 방문하는 node에 check를 하며 갯수를 세준다. 이때 중복되는, 문제에서 처럼 food 의 경우는 o가 두번 나오게 되는데 node에 check 변수를 넣어주는 이유는 이 중복을 제거하기 위해서이다. 따라서 현재 방문한 노드에 check가 ..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18GHd6IskCFAZN(이 글이 문제가 될 시 삭제하도록 하겠습니다.) TRIE 유형을 다시 공부하게 되는 계기가 되었다. 접미어가 나올 수 있는 갯수가 문자열의 숫자랑 같기 때문에 그렇게 탐색에 많이 걸리지는 않는다. 입력받는 문자열을 모두 TRIE로 접미어화 시켜서 입력한다. 그 후에 문자열을 모두 끝까지 순회하면서 검색한다. 끝에 도달했을 때 숫자를 세면서 K번째가 되는 접미어를 찾는다. 순회하며 탐색할때는 vector로 구현해줘도 되고, 단순히 배열로 해줘도 되는데 간편하게 vector로 구현했다. 123456789101112131415161718..
상당히 구현만을 위한 문제였다.... 이 문제랑 실패율 두 문제 밖에 못풀었는데 오픈 채팅방 문제는 stl을 안쓰고 풀다가 시간초과가 계속 떠서 오래걸림... stl 쓰자마자 바로 통과!! 그냥 문제의 조건에 맞게 구현만 잘해주면 된다. map과 vector, string 만 잘 다뤄주면 된다 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #include using namespace std; vector solution(vector record) { vector answer; vector tmp; vec..
생각보다 시간이 오래 안걸렸던 문제... 디버깅하느라 시간 오래 쓴줄 알았는데 1시간도 안걸렸다 그냥 문제 조건에 맞게 BFS만 잘 던져주면 쓕하고 풀리는 문제였다. 2. 단지 번호 붙이기 처럼 입력된 조건 범위 내에 차이가 나는 국가들을 BFS로 찾으면서 그 값을 더하고, 갯수를 센다. 3. 함수 종료 전, 찾은 국가들은 check배열에 모두 더한 숫자 / 국가 숫자 로 나누어 갱신 4. map이 check배열과 똑같다면 인구 이동이 없었던 것으로 간주하여 while문 탈출, 아니라면 map을 check배열로 갱신하고, 동시에 check배열을 초기화 이 과정만 잘 구현해 준다면 문제 없이 풀리는 문제이다. 123456789101112131415161718192021222324252627282930313..
이 문제를 풀면서 거의 두 시간정도 아기상어 노래를 부른거 같닼ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 문제를 이해하고 구현하는데 1시간 걸렸는데.... 풀고보니 내가 이해한건 90퍼 였다 나머지 10퍼는 디버깅하면서 찾느라 30분 정도 걸림.... 자 문제의 조건에 대해서 생각하며 BFS탐색과 메모이제이션?이라고 해야하나...만족하는 값을 저장하고 갱신하는 방법으로 진행했다. 1. BFS탐색을 통해 최단거리 내의(맨위, 맨 왼쪽->문제의 조건을 만족하는 지점)의 갈 수 있는 곳을 찾는다. 2. 찾았다면 갈 수 있는 지점이라 판단, list에 저장한다. 3. 계속 BFS 탐색이 종료되면 문제의 조건에 맞게 sort한다. 4. 저장된 list[0].dis를 리턴함으로서 거리를 더해 주고, 그 위치를 map에서 삭제한다. 5. 먹..
문제를 조금씩 잘못 이해해서 좀 오래걸렸던 문제... 우선순위 큐를 사용하라는 말이 많았는데 나는 굳이 그렇게 특별히 알고리즘을 사용하지는 않았다 1. 초기에 주어진 양분에서 입력된 나무의 위치를 넣는다. 2. 봄이 찾아온다. 여기서 2중 for문으로 순회하며 나무가 있는 곳은 sort하여 어린 나무 순서대로 양분을 먹인다. 양분을 먹이다 남은 양분보다 많은 나이가 나오면, 그순간부터 dead 구조체 배열에 순차적으로 담아주고, 나무의 갯수와 그 map에서 죽은 나무를 제거한다. 3. 여름이 찾아온다. dead 구조체 배열에 담긴 죽은 나무들을 하나씩 map에 나이의 절반을 더해준다. 4. 가을이 찾아온다. 다시 2중 for문을 순회하며 나이가 5이상인 나무 주변의 8개 방향에 나이 1인 나무를 뒤에다 ..
일단 이 문제는 DFS, BFS 둘 다 가능하지만, 저는 BFS를 선호하기 때문에 BFS로 풀었습니다 1. 입력된 맵정보를 2차원 for문으로 순회하면서 맵이 1인 부분에서 BFS로 영역을 탐색 2. BFS 탐색이 한번 끝날 때 마다 카운트를 올려주면서 영역의 갯수를 구해주면 끝 ICT코테는 영역의 넓이를 구하라고 되어 있는데 이것도 BFS 내부에서 마킹할 때 마다 카운트를 세주면 되는 간단한 문제! 그래도 혹시 모르니 DFS, BFS문제 모두 올리겠습니다 - BFS버전 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#in..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo (이 글이 문제가 될 시 삭제하도록 하겠습니다.) '정말 삼성스러운 문제였다'라고 생각했습니다. 이전에 올렸던 벽돌깨기, 보물상자 비밀번호도 같은 생각이 들었습니다. '출발 위치와 진행 방향을 임의로 선정가능'이라고 제시되어 있기 때문에 핀볼이 놓일 수 있는, 즉 아무런 장애물도 없는 곳에서 모든 방향으로 진행시켜보며 조건만 잘 걸어주면 해결 가능 저는 귀찮아서 그냥 모든 조건을 세부화 시켜서 걸어주었지만, 더 고수분들은 짧게 짰을 것 같다(저도 평균적으로는 긴편은 아니긴 했지만...) 1234567891011121314151617..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo (이 글이 문제가 될 시 삭제하도록 하겠습니다.) 기출문제인 톱니바퀴처럼 문자열을 돌려주면 쉽게 해결 할 수 있는 문제 일단 입력되는 문자열을 N/4만큼씩 잘라서 검사를 해 준다 map으로 문자열을 저장하면 하나의 문자열을 인덱스처럼 사용할 수 있기 때문 이 인덱스에 해당하는 문자열이 존재한다면 dab배열에 담지 않고, 없다면 잘라준 문자열을 16진수 -> 10진수로 바꾸어 dab 배열에 담아준다. 마지막으로 dab배열을 내림차순 정렬 후, K-1번째 숫자를 출력하면 끝 1234567891011121314151617181920212..