본문 바로가기

알고리즘131

[백준][백트래킹] 6603 로또 로또 문제는 백트래킹을 이용해서 해결합니다. 2019. 10. 7.
[백준][그리디] 11399 ATM ATM문제는 그리디 알고리즘을 이용해서 해결할 수 있습니다. 2019. 9. 23.
[백준][DP] 11727 2Xn 타일링 2 2xn 타일링 2문제는 다이나믹 프로그래밍으로 처리할 수 있습니다. 1칸일 때 타일을 깔 수 있는 방법은 타일을 세로로 까는 방법 1개 입니다. 2칸일 때 타일을 까는 방법은 2X2 타일 하나를 붙이는 것과, 타일 두개를 세로로 까는 방법 2개 입니다. N번째 칸이 추가 될 때 타일 한개를 까는방법은 N-1번의 칸에 타일 한개를 추가하는 방법과 N-2번의 칸에 2개 짜리 타일을 추가하는 방법이 있습니다. N = [N-1] + [N-2] + [N-2] 2019. 7. 23.
[프로그래머스][스칼라] K번째수 https://programmers.co.kr/learn/courses/30/lessons/42748?language=scala 알고리즘 연습 - K번째수 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr object Solution01 extends App { var array = Vector(1, 5, 2, 6, 3, 7, 4) var commands = Vector(Vector(2, 5, 3), Vector(4, 4, 1), Vector(1, 7, 3)) def solution(array: Vector[Int], commands: Vector[Vector[Int]]): Vector[Int] = { def innerSol(array: Vector[Int], command.. 2019. 5. 7.
[알고리즘] 코딩, 알고리즘 연습 사이트 최근 많은 IT회사들이 코딩테스트를 보면서 코딩 연습 사이트가 많이 생겼습니다. 다음의 사이트들에서 연습할 수 있습니다. 코딩 연습파이썬: https://www.pythonpad.co/courses/intro-1/ https://www.pythonpad.co/courses/intro-1/ 출처: https://118k.tistory.com/249#comment12300916 [개발자로 살아남기]https://www.pythonpad.co/courses/intro-1/ 출처: https://118k.tistory.com/249#comment12300916 [개발자로 살아남기] 출처: https://118k.tistory.com/249#comment12300916 [개발자로 살아남기]https://www.p.. 2019. 4. 24.
[백준][삼성SW검정] 14890 경사로 경사로 문제는 시뮬레이션 문제입니다. 문제가 제시하는 조건을 잘 읽고 풀어보면 됩니다. 가로, 세로는 하나의 로직으로 처리하기 위해서 배열 두개로 입력받아서 처리합니다. 1. 배열의 한행을 기준으로 합니다. 2. 순차적으로 읽어가다가 높이차가 1이면 경사로를 계산합니다. 3. 낮은 경우에는 경사로 길이(L) 만큼 앞으로 체크 4. 높은 경우에는 경사로 길이(L) 만큼 뒤로 체크 2019. 4. 8.
[백준] 1260 DFS와 BFS DFS와 BFS문제는 정점사이의 간선을 탐색하는 기본적인 문제입니다. 간선사이의 연결 상태를 표현하는 link배열과 방문여부를 표현하는 visited 배열을 이용하여 해결합니다. 2019. 4. 2.
[백준][삼성SW검정] 14500 테트로미노 테트로미노 문제는 가장 간단하게는 현재 시작점을 기준으로 각 모양별로 회전하여 이동가능한 위치의 배열을 만들어서 모두 더하면 됩니다. (다음 소스의 exceptions 를 확인) ㅗ 모양 외에는 DFS로 현재 시점부터 상하좌우로 4칸씩 이동하면 각 도형이 회전한 모양으로 생성됩니다 이를 이용해서 DFS로 이동하여 4칸 이동했을때의 최대값을 구하면 됩니다 2019. 3. 25.
[알고리즘] Scanner와 BufferedReader의 속도 차이 Java를 이용하여 알고리즘 문제(백준, 토마토, 7576)를 풀어 보다가 스캐너(Scanner)를 이용할 때와 버퍼리더(BufferedReader)를 이용할 때의 속도 차이를 비교해 보았습니다. 동일한 로직을 데이터를 입력 받는 부분만 스캐너와 버퍼리더를 이용하여 시간을 비교해본 결과가 다음과 같습니다. 스캐너시간: 1620 ms 메모리: 335660 KB 버퍼리더시간: 552 ms 메모리: 143148 KB 스캐너를 이용하는 경우 시간은 3배, 메모리는 2배 정도 더 사용하는 것을 볼 수 있습니다. 스캐너- JDK7 소스 [바로가기] 버퍼리더- JDK7 소스 [바로가기] 소스를 확인해 보면 스캐너의 캐쉬는 1024, 버퍼리더는 8192이고, 스캐너는 데이터를 입력받을 때 정규식을 이용하여 입력 값을 .. 2019. 3. 21.
[백준] 7576 토마토 토마토 문제는 BFS를 이용하여 해결할 수 있습니다. 1. 익은 토마토(1)는 큐에 추가, 익지 않은 토마토(0)의 개수를 세어줌 2. BFS로 익은 토마토 상하 좌우의 토마토를 큐에 추가3. 처리일(day)을 추가하고, 다시 반복 4. 모든 토마토가 익었으면 결과를 출력하고, 아니면 -1 출력 2019. 3. 21.
[백준] 11505 구간 곱 구하기 구간 곱 구하기 문제는 세그먼트 트리를 이용합니다. 세그먼트 트리를 이용하여 각 구간의 곱을 미리 계산하여 두고, 각 구간의 곱을 출력합니다. 2019. 3. 20.
[백준][삼성SW검정] 13458 시험감독 시험 감독 문제는 다음과 같이 해결합니다. 1. 시험장 인원에서 총감독관의 인원을 빼고 sum + 12. 나머지 인원이 있으면 부 감독관이 필요한 개수를 sum + () - 나머지 인원 / 부감독관 - 나머지 인원 % 부감독관 - 이 두개를 계산하여 처리 2019. 2. 14.
[백준][삼성SW검정] 12100 2048(Easy) 2048(Easy) 문제는 DFS를 이용하여 해결하였습니다. 1. 먼저 배열을 이동합니다. 2. 배열을 이동방향으로 순회하면서 병합합니다. - 이전 인덱스의 값과 비교해서 동일하면 현재 인덱스에 새로운값을 넣고, 이전 인덱스에 0을 입력합니다. 3. 배열을 이동 방향으로 다시 이동합니다. - 병합에서 발생한 0을 처리하기 위해서 입니다. 2019. 2. 12.
[백준][삼성SW검정] 16234 인구이동 인구이동 문제는 BFS를 이용하여 해결합니다. 현재 위치에서 연합이 가능한 국가를 확인해서 국가의 합을 구해서 인구수를 재배치 하고,이를 계속 반복하여 인구 이동이 없을때까지 진행합니다. 2019. 2. 8.
[백준][삼성SW검정] 14501 퇴사 퇴사 문제는 BFS로 현재 일자부터 순차적으로일을 할때와 하지 않을때로 나눠서 이동해가면서,얻을 수 있는 최대값을 이용하여 이동여부를 결정하면 마지막날의 최대값을 구할 수 있습니다. 2019. 2. 7.
[백준][삼성SW검정] 15684 사다리조작 사다리조작 문제는 완전 탐색을 이용하여 처리합니다. 조합을 이용하여 3개 이하의 사다리를 선택 가능한 모든 경우를 생성하고, 이때 최소 횟수로 선택이 가능한 경우를 출력합니다. 2019. 2. 7.
[백준] 15686 치킨 배달 치킨배달 문제는 먼저 조합을 이용해서 치킨집을 선택하고,도시의 치킨거리의 합을 구하면 되는 문제입니다. 치킨거리는 집을 기준으로 가장 가까운 치킨 거리의 합입니다. 2019. 2. 6.
[백준][슬라이딩윈도우] 11003 최솟값 찾기 최솟값 찾기 문제는 슬라이딩 윈도우 알고리즘을 이용합니다. 슬라이딩 윈도우 알고리즘은 덱(Deque)을 이용합니다. 덱은 큐와 스택을 합친 동작읍 합니다. 먼저 입력한 데이터를 출력할 수도 있고, 뒤에서도 출력할 수 있습니다. 2019. 2. 3.
[백준][DP] 9184 신나는 함수 실행 신나는 함수 실행은 다이나믹 프로그래밍을 이용하여 구성할 수 있습니다. 계산을 위한 점화식은 이미 문제에 나와 있습니다. 이 계산식을 그대로 구현하고, 계산결과를 배열에 넣어두고 동일한 계산은 이전 계산 결과를 사용하면 됩니다. 2019. 2. 2.
[백준] 2151 거울 설치 거울 설치문제는 BFS를 이용해서 다음 경로를 탐색하고 메모이제이션을 이용해서 최소한의 횟수로 이동할 수 있는 지점을 제한합니다. 이동방향은 거울을 설치하는 경우 두가지와 거울을 설치하지 않는 경우 한기지로 선택합니다. 예를 들어 오른쪽으로 이동하는 경우 거울을 설치하면 위, 아래로 이동하고,거울을 설치 하지 않는경우 오른쪽으로 계속 이동하게 됩니다. 모든 경우를 계산하여 도착지점 문의 메모이제이션의 값이 최소 이동 횟수가 됩니다. 2019. 1. 29.
[백준][삼성SW검정] 14889 스타트와 링크 스타트와 링크 문제는 팀을 선택하는 조합을 선택하면 해결할 수 있습니다. 그리고 팀원의 순서는 중요하지 않기 때문에 한번만 선택하면 되기 때문에 첫번째 선수는 1번만 돌면 됩니다. 1, 2, 3, 4 선수일때 1, 2, 3, 41, 2, 3, 41, 2, 3, 4 이렇게 3개의 경우만 선택하면 같은 팀구성이 끝나게 됩니다. 팀구성을 완료하고, 각팀의 점수를 계산해서 차이를 비교하면 값을 구할 수 있습니다. 2019. 1. 15.
[백준][삼성SW검정] 14888 연산자 끼워넣기 연산자 끼워넣기 문제는 주어진 개수의 연산자를 조합해서 처리하는 문제입니다. for문을 이용하여 조합을 생성해내고, DFS를 이용하여 데이터를 처리하면 됩니다. 연산은 연산자 배열에 인덱스 번호에 따라 처리합니다. 2019. 1. 14.
[백준][삼성SW검정] 14502 연구소 연구소 문제는 3개의 벽을 세우는 조합과 벽을 세운뒤 바이러스의 개수를 세어서바이러스 영역이 제일 작을 때의 안전영역의 크기를 구했습니다. - 임시벽은 3으로 표시하였습니다. - 안전역역 = 공백구간 - 바이러스 개수 - 3(임시벽의 개수) 2019. 1. 11.
[백준] 4673 셀프 넘버 셀프넘버는 숫자를 한자리씩 분리하여 더하여 주면 계산할 수 있습니다. 123을 1, 2, 3 으로 분리하는 방법은 10으로 나누어 몫은 다음계산으로 나머지는 더하여 주면 됩니다. 다음 처럼 구하면 됩니다. 123/10 = 12 123%10 = 312/10 = 1 12%10 = 21/10 = 0 1%10 = 1 2019. 1. 9.
[백준][BFS] 1600 말이되고픈 원숭이 말이 되고픈 원숭이는 3차원 배열을 이용해서 해결합니다. 최소 이동횟수를 체크하는 배열을 만들고, x, y 위치로 이동할 때 최소이동 횟수로 도착하면 큐에 추가합니다. 여기에 말로 이동하는 것도 체크해야 하기 때문에 3차원 배열로[말이동횟수][x 좌표][y 좌표] 배열로 최소 이동 횟수를 체크해서 도착위치에 도달하는 최소 횟수를 체크합니다. 2019. 1. 9.
[백준][그리디] 1931 회의실 배정 이 문제는 그리디 알고리즘을 이용하여 해결할 수 있다. 종료 시간을 기준으로 정렬하여 이전 종료시간이후로 가장빨리 시작하는 회의의 개수를 확인하면 된다. https://www.acmicpc.net/problem/1931 2018. 9. 18.
[정렬][java] 거품정렬(버블소트) 버블정렬 구현체는 다음과 같다. 2018. 9. 17.
[백준][그리디] 1049 기타줄 기타줄 문제는 그리디 알고리즘으로 해결한다. 적어도 끊어진 기타줄 만큼 구매할 수 있는 최소한의 돈을 출력하면 된다. 1. 패키지로 구매할 수 있는 최소값, 개당으로 구매할 수 있는 최소값을 구하고,2. 패키지로 구매하는 것보다, 개당구매로 6개를 구매하는 것이 더 싼지 확인하고,3. 끊어진 기타줄 만큼 패키지 구매 + min(개당 구매, 패키지구매) 적어도 끊어진 기타줄 만큼 구매이기 때문에 더 구매해도 되는 것을 생각해서 마지막에 패키지 구매가 최소값인지 확인하면 된다. https://www.acmicpc.net/problem/1049 2018. 9. 12.
[정올] 2616 앱 이 문제는 다이나믹 프로그래밍을 이용하여 해결 할 수 있다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1878&sca=3050 2018. 9. 9.
[백준][투포인터] 2003 수들의 합2 수들의 합2 문제는 투포인터 알고리즘을 이용하여 해결할 수 있다. s(start), e(end) 인덱스를 이용하여, start 로 배열을 증가하면서 sum을 증가시켜 M값과 동일하면 count를 증가하고 end를 증가하면서 sum 을 빼서 동일한 값이 있는지 확인한다. 배열 = {1 2 3 4 2 5 3 1 1 2}일때 start, end는 처음에 0번 인덱스 입니다. start를 증가하면서 1 + 2 + 3을 순서대로 해주면 sum은 6이 되어 M을 넘어서게 됩니다. 이때 end를 증가하면서 sum을 빼주면start가 2번 인덱스이고, end가 0번 인덱스인 시점에 합은 5가 됩니다. 이때 count를 1더해주면 됩니다. 이를 끝까지 반복해주면 됩니다. 2018. 6. 21.

티스토리툴바