본문 바로가기
[백준 알고리즘] 15684번 사다리 조작 다음 본 문제는 또 삼성 상반기 문제 였던 사다리 조작문제입니다. 15684 사다리 조작 전 이 문제 손도 못 댔었는데.. 그 이유가 방법을 모른다는 것이긴 하지만..! 감이 완전 안오던 문제였어요. 이제 와서 풀어보고 느낀 것이지만, 정말 기초적인 개념이 매우 중요한 문제 였던 것 같습니다. 이번 문제는 전에 풀었던 감시문제와 비슷하게 순열 조합 개념이 들어갑니다. 정말 당황 스럽게도… 답은 전수 조사 였습니다. 삼성은 약간 DFS, BFS랑 조합을 섞은 시뮬레이션같은 문제를 좋아하나 봅니다.ㅋㅋㅋ vector T; int arr[4] = {1,2,3,4}; vector com; void swap(int *a, int *b ){ int tmp; tmp = *a; *a = *b; *b = tmp; } v..
[백준 알고리즘] 15683번 감시 안녕하세요! 오랜만에 포스팅을 하게 되었네요ㅎㅎ 이번에 풀어본 문제는 2018 상반기 삼성 SW역량 테스트 문제인 감시문제입니다.15683번: 감시 저도 상반기에 시험봤던 문제인데, 풀지 못했던 문제였는데..ㅠㅠ 다시 푸니까 감회가 새롭네요!!! 이 문제를 풀면서 느낀건 n이 1000 이하의 수라면 n^2의 연산도 매우 짧다는 걸 느꼈습니다. 먼저 문제를 풀기 위해선 중복 순열을 알고 있어야 합니다. 제가 최근에 경우의 수 순열, 조합, 중복 순열에 개념이랑 코드를 포스팅했었습니다.제가 이 문제를 처음 접근했을 때는 감시 범위가 가장 큰 카메라를 먼저 설정하는 방식으로 문제를 풀었는데, 자꾸 틀렸다고 해서 적용해보았는데 맞더라구요.이를 중복순열을 적용한다는 건 결국 각 감시 카메라에 대해서 가능한 모든 ..
[경우의 수] 순열, 조합, 중복 순열 이번엔 경우의 수를 구하는 순열, 조합, 중복순열에 대해서 알아보겠습니다. 여러분이 많이 알고 있는 경우의 수구하는 알고리즘인데, 이를 넘어서 해당 성분들까지 구해보는 경우를 구해봅시다!! 순열(Permutation) 먼저 순열이 어떤 건지 알아봅시다. 기호로 표현하면 nPr이라고 표현합니다. 해석하자면 n개의 성분에서 r개를 뽑아 나열시킨 경우의 수가 되겠네요.대표적인 예로 줄 세우기가 될텐데, 순열은 방향성이 있는 경우의 수입니다. 즉 123이랑 321은 다르다는 거죠.먼저 순열의 경우의 수를 구하는 식을 보면 이러합니다.한번 구현해보기에 앞서서 순열이 데이터를 선택하는 절차를 보면 이렇게 되겠죠. 그림처럼 선택된 데이터를 제외한 리스트에서 다른 데이터를 가져오는 방식으로 데이터가 선택됩니다. 제가 ..
[STL] Sort,Queue,Priority_Queue 이번에는 STL의 sort, que, priority_que의 사용법에 대해서 정리해보겠습니다. 사용법은 무지 간단한데, 잊지 안기 위해..!! Sort sort는 STL중에 가장 많이 쓰는 것 같네요. 진짜 개꿀. 라이브러리는 algorithm입니다. #include sort의 사용법은 매우 간단합니다. sort(정렬할 주소의 첫 번째 값, 정렬할 주소의 마지막 값, 정렬 기준); 정렬할 주소의 첫 번째 마지막 값은 잘 아실테니 넘어가겠습니다. 중요한건 정렬 기준입니다. 간단하게 less, greater가 있습니다. less() : 이걸 넣을 경우엔 오름차순으로 정렬이 됩니다. greater() : 이건 반대로 내림차순으로 정렬이 되죠. 물론 이것만 알아도 충분하지만, 스스로 정렬 기준을 정할 수 있습..
[백준 알고리즘] 6593번 상범빌딩 이번에 풀어본 문제는 백준의 상범 빌딩입니다. 6593번: 상범 빌딩 3차원의 간단한 BFS문제입니다. 다익스트라 알고리즘 분류로 들어가서 풀었는데 왠 BFS인지..ㅋㅋ 너무 간단하게 해결!! 많은 분들이 이렇게 풀긴 하지만, 전 처음 해봤는데 좌표를 이동 시키는데 해당 이동 값을 저장시킨후에 for문을 돌리는 방법이 보기에 편한 것 같더라구요. 그림을 보면 좌표의 이동이 이렇게 되는 것을 알 수 있습니다. 좀 헷갈리긴 하지만, 가만 생각해보면 맞다는 것을 알 수 있습니다.그러면 이렇게 표현할 수 있겠네요. int moveH[6] = { -1, 1, 0, 0, 0, 0}; int moveX[6] = { 0, 0, 0, 0,-1, 1}; int moveY[6] = { 0, 0,-1, 1, 0, 0}; 이렇..
[백준 알고리즘] 2178번 미로찾기 이번에 풀어본 문제는 백준의 미로 찾기문제입니다.2178번: 미로 탐색 문제는 정말로 미로찾기 문제이고, 주어진 미로에서 도착지까지 가는 최소 칸 수를 구하는 문제입니다. 처음엔 재귀함수로 풀었는데, 도착지가 있는 경우엔 재귀함수를 사용하는 것이 애매하더라구요. 그래서 queue로 접근해보았습니다!! 시작점(1,1)을 queue에 push한다. 현재 기준점을 기준(queue의 front)으로 위, 아래, 오른쪽, 왼쪽 4 방향을 검색한다. 끝 정말 전형적인 BFS, DFS문제입니다!! 제가 처음 문제를 풀었을 때는, 이렇게 풀었어요. 위와 동일 queue에 집어넣는 것은 (x,y좌표와 (x,y)까지 가는 칸수) 도착지 까지 간 경우 기존 도착지 까지 간 칸수와 최근 들어온 칸수를 비교해서 작은 값으로 설..
[CodeGround] 괄호 문제 이번에는 코드그라운드의 괄호문제 입니다. codeground 문제를 간단하게 말하면 괄호 순서가 올바르게 된 부분 문자열의 최대 길이를 구하라는 겁니다!! 괄호 문제는 사실 유명하죠!! 여러 곳에서 나오는 문제 중 하나입니다. 이 문제는 괄호의 성질을 잘 생각해보면 간단하게 풀 수 있는데, 한번 봅시다. [{}()] 이런 경우는 올바른 괄호가 되겠죠. 모두 잘 닫혔으니까.[]{)[] 이런 경우는 가운데 {)이거 때문에 제대로 되지 않겠네요. 괄호는 한번 열리면 같은 모양으로 반드시 닫혀야 하는 성질이 있죠. 이를 잘 생각해보면 가장 최근에 열린 괄호는 먼저 닫혀야 한다.라는 결론이 나오네요!! 조금 느낌이 오시나요?? 정답은 stack에 있습니다!! stack으로 풀면 해결은 되는데 코드그라운드에서는 t..
핵심 친구 찾기 문제 이번에 풀어본 문제는 삼성 소프트웨어 역량테스트라는 책에 있는 모의고사 문제인 핵심 친구 찾기문제입니다!! 먼저 문제에 대한 설명은 이러합니다. 담임 선생님이 새 학기가 되서 학생들 친구관계를 조사하고 있어요. 여기서 선생님은 핵심 친구를 찾으려고 하는데,핵심 친구란 해당 친구가 빠지게 되면 친구관계에서 연결 되지 않는 친구가 생기는 경우 그 친구를 핵심 친구라고 해요. 예를 봅시다. 이런 친구관계 그래프가 있다고 합시다. 여기서 만약 3번 친구가 없다고 생각하고 다시 친구 관계도를 봅시다. 오호 3번 친구가 없어도 나머지 친구들이 잘 이어져 있네요. 이런 경우 3번 친구는 핵심 친구가 아니게 되는거죠. 이번엔 6번 친구가 빠졌다고 생각해봅시다.오호 6번 친구가 빠지니까 7,8,9 친구가 다른 애들이랑 ..

티스토리툴바