혼종 꼬지마루

https://www.acmicpc.net/problem/18192 음... 정~~~~말 오랜만에 문제를 풀려고 앉았는데.... 재밌는 문제라해서 들어가 봤더니 이런 세상에?? 마치 B형 시험과 같이, 주어지는 header나 cpp파일을 include 해야 되는 문제.... 문제도 뭔가 되게 긴장되게 생겼지만, 문제가 B형에 비해서 상당히 허술하다.... 비교를 하자면, B형은 내가 생각할 때 크게 두가지로 나뉘는 것 같다.1. 충실히 구현만 하면 풀 수 있다. 하지만,,,, 최적화 부분에서 score가 메겨지는 유형2. 구현이 거지같이 힘들거나 어려운 문제 그러나 이 문제는 그냥.... 허술하기 짝이 없다;; 주어지는 조건이라고는 함수 호출 2500번이 끝.... 한마디로 주어지는 최적화 답과는 달라도..

https://www.acmicpc.net/problem/17070이 문제와 상당히 유사하고, 2019/10/13 - [Algorithms/DP] - [백준] 17070 - 파이프 옮기기에 위 문제의 풀이를 포스팅 하였으니 왜 같다고 생각한지 확인 해보시길... 먼저 이 문제는 dfs로 풀면 아주, 상당히, 시간이 걸릴 문제다. 그렇기 때문에, dfs에 dp를 먹여서 가지도 쳐 주고, 무한 루프도 쉽게 찾을 수 있다. 한번 끝까지 간(범위를 벋어나거나, 구멍에 빠지거나) 한 동전은 돌아오며 그 길이를 저장한다. 즉, 좌표에 끝까지 갔을 경우, 최대 몇번까지 움직일 수 있는지를 저장한다. 한마디로 구멍이나, 범위를 벋어난 동전은 재귀 호출에 return 할때 1, 2, 3....순으로 돌아오는 좌표에 저장..

https://www.acmicpc.net/problem/1103위의 문제와 상당히 유사했고, 한번 유사문제를 풀어봤기 때문에 '음... 이런 느낌으로 풀면 되겠네?' 하고 슥슥 했는데 한번에 통과됨... 풀어놓고도 왜 된거지? 했음 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 일단 이 문제는 dfs + dp의 유형이라고 본다. 한번 탐색했던 경로에 경로의 갯수를 저장, 즉, 끝까지 한번 가면 돌아오는길에 그 포인터에 이전에 갯수를 더해주고 저장한다. 최초에 목적지에 도착한 파이프는 그 지점에서 1개의 경로를 가지기 때문에 1을 return 받는다. 그럼 return 된 1이 이전의 좌표의 visit 배열에 더해주고 저장한다. 바로 이전 점에서 다른 경로를 탐색하고, return 받을 수 있다면 return 받은 값을 더하고 저..

문제 이름 한번 잘 지었네..... f**k만 몇번을 외쳤던가.... A+등급을 딸 때 풀었던 문제라 쉽게생각하고 건드렸다가 문제 출력조건이 조금 달라서 맞왜틀 이러고 1시간을 날려먹은 문제 문제 조건도 애매모호한 부분이 있고, 출력 답의 예시라도 설명을 해줬으면 좋았을 문제.... 먼저 출력은 2가지만 생각하면 된다. 정상 종료, loop로 인해 정상종료가 불가능한 경우 정상 종료는 문제가 없는데 loop를 설정하는거에서 문제가 많다.... 일단 풀이를 차근히 해보도록 하겠다. 먼저, 이 문제의 핵심은 [, ]일때 점프하는 index를 어떻게 잘 정해주는가이다. 간단히 stack으로 해결할 수 있다. 일단 명령어를 입력받고, 순회하며 stack으로 쌍을 지어 점프 포인트를 만들어 주면 된다. 그 외에는..

TRIE란 TREE를 응용한 문자열 알고리즘이다. Wiki에서는 hash map을 대신할 수 있다고 되어 있는데 실제로 그렇다. 단순하게 이진트리가 아니라, 문자열을 순차적으로 순회하며 tree를 구성해주게 되는데, trie를 사용하는 장점 중 하나는 저장과 동시에 정렬이 된다는 점이다. 삼성전자 상시 역량테스트를 준비하면서 hash를 공부하는 사람들이 많은데, 사실 데이터양이 많아질수록 직접 구현한 hash일수록 index충돌이 많이 일어나서 생각보다 AutoK를 하는 경우가 생길것이다. 물론 hash에 충돌이 안나게하는 여러가지 기법이 있지만.... key값이 그리 길지 않다면 trie를 hash처럼 사용하는 것을 선호하는 편이다. 위의 그림(Wiki 참조)과 같이 문자를 하나의 key값으로 삼으며 ..

Heap이란 입력으로 들어온 데이터를 2진 트리의 형태로 나타내어 순서대로 정렬? 해주는 것이라고 생각하면 쉬울 것이다. 자식 노드에 있는 값은 항상 부모노드의 값보다 작아야(혹은 정렬기준에 따라 커야) 함으로 입력과 동시에 정렬이 된다. Heap을 사용하는 가장 대표적으로 사용하는 우선순위 queue, heap sort가 있다. 그 중에서도 heap sort를 구현해 보았으며, 정렬 기준을 함수로 선언하여 던져주는, 즉, algorithm 헤더에 있는 sort와 최대한 비슷하게 구현해보았다. 정의된 시간 복잡도는 heap sort는 O(nlogn)이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464..

삼성전자 수시 역량테스트 B형을 준비하기 위해서 필요한 reference code를 직접 구현하면서 정리를 해보는 중 어짜피 queue나 stack은 딱히 구현할 연습은 없어보임....원래 stl을 안썻으니.... 하지만 map이나 sort는 해본적이 없고, 우선순위 queue같은 것도 미리 구현을 해보면 좋을 것 같다는 생각이 들었다. 그 중에 이 글은 map을 대체로 사용할 수 있는 hash를 구현해 보았다. 여기서 가장 중요하게 기억해야 할 것은 5381이라는 골든 넘버! hash를 구현하다 보면 다른 key값이지만, 이미 할당된 index를 참조하는 경우가 있다. 이런 index 충돌이 일어나게 되는 것이 최소화시키는 것이 5381이라고 한다. 자세한 것은 아래의 코드를 보면서 참조하면 될 것 같..

삼성전자 상시테스트 문제와 상당히 유사하다고 해서 풀어보았는데..... 돌리는게 귀찮은 문제라고 결론을 내려본다 단순히 dfs로 돌리는 순서를 정해주면서, 최소값을 찾는 배열을 만들어 주느냐가 관건이다 항상 말하지만 나는 stl을 안쓰고 짜는 것을 선호하지만, 이 문제는 색종이 붙이기와 같이 dfs함수가 return되었을 때 map이 그 depth에서 만든 map으로 원복되는 것을 원하기 때문에 vector를 선언해서 사용했다 1. map을 선언하고, map을 rotation시키는 좌표를 입력받는다 2. dfs로 전체 탐색 하면서, 순서를 저장하는 것이 아닌, 그때마다 돌려준다.- 저장했다 한번에 돌려줘도 되지만, 비효율적이라고 생각이 들었기 때문 3. depth가 K에 이르면, 문제의 조건에 따른 각 ..

이것 또한 삼성전자 기출이라고 한다 그냥 BFS라고 생각해서 풀었다가 예외처리를 겁나 해준..... dfs와 함께 섞어서 사용하지만, 메인은 bfs라서 bfs에 올림 최적화나 코드 정리따위는 하고 싶지않아서 그냥 간단하게 코드정리만 하고 포스팅 1. 언제나 그렇든 map을 입력을 받는다- 입력을 받으며 바이러스는 따로 구조체배열에 저장하고, 벽과 바이러스가 없는 구간의 공간을 count해준다 2. dfs를 돌면서 virus를 M개만큼 선택하며 큐에 담아준다 3. bfs에 들어가면, 큐에 담긴 K개의 좌표를 visit배열에 표기하고, st값을 올려주면서 virus(순회한 virus로 정의했음)의 갯수를 올림 4. bfs를 돌면서 조건에 맞게 단순 bfs를 돌지만, virus가 있는 공간을 지날때, map[..

삼성전자 19년 상반기 기출이라고 해서 예~~~~전부터 풀어보려고 했지만.....귀찮아서 미루고 미루다가 드디어 풀어보았다 ㅋㅋㅋ 어려워 보이고, vector를 쓰면 편할 것 처럼 보이지만 범위가 명확하고, 굳이 vector를 쓰지 않아도 될 것 같아서 그냥 풀었다 1. 입력되는 확인할 target 좌표와 3x3행렬을 입력받는다. 2. 함수는 총 5개를 만들었다. target좌표를 확인할 함수, 행렬을 한줄씩 계산하고 바꿔줄 함수, R, C에 들어갈 각각의 함수를 만들었다. 3. for문으로 dab을 count하게 만들었고, for문이 돌 때 가장 먼저 target좌표의 답을 확인 4. R, C의 길이를 확인하여 CalR, CalC함수를 호출 5. CalR기준으로, 행을 순회하며 열의 값을 tmp_arr..