본문 바로가기

Algorithm

백준 15683 감시 Java 2019. 9. 19. 삼성 SW 역량테스트 기출문제이다. CCTV의 종류는 5가지이고 회전이 가능하다. 따라서 0 -> 동, 1 -> 서, 2 -> 남, 3 -> 북 이라고 할 때 1번은 1, 2, 3, 4 = 4가지 2번은 01, 23 = 2가지 3번은 02, 03, 12, 13 = 4가지 4번은 012, 013, 023, 123 = 4가지 5번은 0123 = 1가지이다. DFS로 1~5까지 수를 만났을 때 수에 맞는 각각의 경우를 감시할 수 있는 범위를 배열에 표시해준 다음에 DFS를 다음 수로 재귀 호출하고 돌아와서 표시해준 수를 다시 0으로 만들어 주는 백트래킹 방식으로 해결하였다. 이렇게 하면 DFS를 타고 타고 모든 경우의 CCTV 범위의 사각지대의 수를 찾을 수 있다. monitor라는 메소드를 만들어서 현재 위..
백준 2607 비슷한 단어 Java 2019. 9. 19. 한국정보올림피아드 초등부 4번, 중등부 2번 문제인 비슷한 단어이다. 내 힘으로 풀긴 풀었지만 꽤 어려웠던 문제 같은데 이런 문제를 풀어내는 초등학생, 중학생이 있다니 더욱더 분발해야겠다. N개의 단어가 주어지는데 첫 번째 단어와 N-1개의 단어들 중에 비슷한 단어의 개수를 출력하면 되는 문제이다. 비슷한 단어는 기준이 되는 문자나 주어진 문자 중 한 문자를 골라서 하나를 추가하거나 하나를 빼거나 하나의 문자를 다른 문자로 바꿨을 때 두 개의 단어가 같으면 비슷한 문자이다. 아예 단어 구성이 같은 단어도 카운트해줘야 한다. 처음엔 기준이 되는 문자열에서 만들 수 있는 모든 비슷한 단어를 구하는 방향으로 구현했는데 열심히 구현하고 틀렸다. 어떻게 구현할까 생각을 많이 했는데 초등부 문제라는 점을 감안해서 ..
백준 17140 이차원 배열과 연산 Java 2019. 9. 17. 삼성 SW 역량테스트 문제인 이차원 배열과 연산이다. 시뮬레이션 문제인데 나한텐 어려웠다.. 요즘 조금복잡한 시뮬레이션 문제를 못풀어내고 있다. 이 문제는 생각해야되는 포인트가 0이 채워지는 부분과 정렬해야 되는 부분, 행과 열에 크기가 100이 넘어가지 않는 부분이다. 내가 캐치하지 못했던 점은 가장 큰 열 또는 가장 큰 행을 MAX라고 할 때 행의 길이가 row이고 열의 길이가 col인 배열을 R 연산하면 [row][MAX] 인 배열이 나오게 되고 C 연산하면 [MAX][col] 인 배열이 나오게 된다는 점이다. 이 포인트를 캐치했다면 0을 채우는 부분을 해결할 수 있다. 나오게되는 값을 채워놓으면 빈자리는 알아서 0이 남기 때문이다. ArrayList를 사용하지않고 기본 배열을 사용하면 편하다. 정..
백준 15686 치킨 배달 Java 2019. 9. 13. 삼성 SW 역량테스트 기출 문제인 치킨 배달 문제이다. 구현하기 쉬운편의 문제이지만 해결하는데 생각보다 오래 걸렸다. 문제에서 주어진 치킨집과 집의 거리를 구하는 공식을 사용하지 않고 BFS로 치킨집과 집의 거리를 구하려고 했던 잘못도 있고 M개의 치킨집을 살릴 때의 모든 경우를 DFS로 구해내는데 조금 시간이 걸렸다. 왜냐하면 재귀 호출시에 파라미터로 어떤 List나 배열을 넘길 때 List나 배열이 추가되고 초기화 되는 부분이 헷갈린다. 그 부분이 헷갈려서 자꾸 문자열로 처리하려는 습관이 있었는데 이 문제, 야구게임 문제 등 몇 개의 문제를 풀면서 확실히 개념이 잡힌 것 같다. 모든 경우를 구할 때 문자열보단 배열을 초기화하는 방식이 훨씬 빠르므로 다른 문제에 적용해보면서 더 연습해봐야겠다. 문제를 ..
백준 14500 테트로미노 Java 2019. 9. 11. 삼성 SW 역량테스트 기출문제인 테트로미노이다. 5가지의 테트로미노 중 하나를 놓았을 때 점수의 합이 최대인 경우 점수의 합을 출력하면 된다. 5가지의 테트로미노를 하나씩 놓아보면서 점수의 합이 최대일 때를 찾아내는 방법밖엔 없는 것 같았다. 테트로미노의 종류가 5개인데 회전도 가능하고 대칭도 가능하기 때문에 5가지의 경우만 검사해보면 되는 것이 아니라 꽤 많은 경우를 검사해봐야 한다. 물론 이렇게 구현하면 실행 속도가 가장 빠르지만 5가지의 테트로미노의 대칭, 회전 포함 모든 경우를 다 따로 검사하는 건 너무 코드가 길 것 같아서 DFS를 통한 백트래킹으로 모든 경우를 검사해보기로 했다. DFS로 상하좌우를 탐색하다가 4번째까지 탐색했을 때 그 합의 최대값을 구하는 방법으로 진행했으나 계속해서 틀렸다...
2019 KAKAO 매칭 점수 Java 2019. 9. 6. 6. 매칭 점수 정답률: 6.12% 문제 풀러 가기 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다. 그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다. 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다. 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시) 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다. 한 ..
백준 2293 동전 1 Java 2019. 9. 2. 동적 프로그래밍 문제인 동전 1이다. dp[K]에는 가치가 K일 때 경우의 수를 저장한다. N만큼 주어진 동전의 가치 별로 K를 만드는 경우의 수를 구해서 dp배열에 누적합을 시켜준다. 동전 문제의 특징인 누적합을 시켜준다는 포인트를 생각해서 점화식을 생각해보면 1 2 3 4 5 6 for(int i=1; i
2019 KAKAO 후보키 Java 2019. 8. 27. 3. 후보키 정답률: 16.09% 문제 풀러 가기 프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다. 그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다. 후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다. 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 ..

티스토리툴바