Algorithm

    Algorithm/BOJ

    BOJ] 14502. 연구소

    BOJ] 14502. 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 2017년 SW역량테스트 기출문제 풀었던 문제지만, 떠올릴 겸 다시 풀어보았다. 생각보다 막힌 부분이 있었지만..

    SWEA] 2112. [모의 SW 역량테스트] 보호 필름
    Algorithm/SWEA

    SWEA] 2112. [모의 SW 역량테스트] 보호 필름

    SWEA] 2112. (모의 SW 역량테스트) 보호 필름 2112. (모의 SW 역량테스트) 보호 필름 문제의 저작권은 SWEA에 있습니다 초기 접근 방법 처음에는 부분집합의 개수로 접근을 하고, 만들어진 부분집합으로 조합을 만들고 나서 약품주입 및 품질확인 과정을 진행한 뒤에 최소 주입횟수를 갱신시켜주는 방법을 사용하였다. 이 방법은, 내가 부분집합을 구하는 방법에서 가장 작은 개수부터 생성되는 것이 아니었기에((1) (1,2) (1,3) (1,2,3) (2)...) 최소 주입횟수를 갱신하는데 까다로운 면이 있었다. 최종 접근 방법 완전탐색으로 접근하면 가능은 하겠지만, 그것보다는 더 파워풀하게 접근해보자. tArr(초기 행 저장 배열)을 적극 활용한다면(초기 접근에서도 사용은 했지만 복잡하게 꼬였다)..

    SWEA] 2105. [모의 SW 역량테스트] 디저트 카페
    Algorithm/SWEA

    SWEA] 2105. [모의 SW 역량테스트] 디저트 카페

    2105.(모의 SW 역량테스트) 디저트 카페 2105. (모의 SW 역량테스트) 디저트 카페 문제의 저작권은 SWEA에 있습니다 대각선을 잘 그리면 되는 문제. 삼성공채 SW 역량테스트를 준비하기 전날에 풀까말까 하다가 안풀고 다른 구현문제를 풀었었는데, 이 문제를 풀고 시험을 봤다면 시간이 부족하지는 않았을텐데 라는 후회를 하게 만든 문제. 여하튼, 나중에 이 문제를 풀때 역시 2019 하반기 공채 삼성 SW역량테스트 오전 1번문제를 풀듯이 풀어봤는데, 생각보다 빡빡하고 시간도 오래걸렸다. (모든 경우의 수를 조건문으로 고려하는 구현방법으로 풀어서) 단순히, 방향과 프루닝(가지치기), 조건을 건 백트래킹을 사용하면 굉장히 파워풀하고 직관적이며 간단한 코드를 짤 수 있다. dfs 백트래킹 짱짱 혹시 비..

    SWEA] 1949. [모의 SW 역량테스트] 등산로 조성
    Algorithm/SWEA

    SWEA] 1949. [모의 SW 역량테스트] 등산로 조성

    SWEA] 1949. (모의 SW 역량테스트) 등산로 조성 SWEA 1949. (모의 SW 역량테스트) 등산로 조성 문제의 저작권은 SWEA에 있습니다 문제의 핵심은 위 규칙 중 3번을 고려하는 것. 처음에는 bfs에 조건을 걸고 산을 깎을 때 dfs로 확인하는 방법을 고려했으나, 결국 dfs 백트래킹으로 하는 것이 확실하고 직관적으로 보여 수정해서 다시 푼 문제. dfs + 백트래킹 방법을 처음부터 적용했더라면, 30분-1시간내에 풀었겠지만, 방황하다가 시간을 조금 더 소요했던 문제였다. 코딩하기 전, 여러 상황을 고려하고 글로 써보고 타이핑을 진행하지만 아직도 많이 부족하다. 그래도 dfs 백트래킹을 적용해서 한번에 성공했을 때는 나름 기뻤던 문제. dfs 백트래킹을 연습하기에 좋은 문제. 1 2 3..

    Algorithm/BOJ

    BOJ] 2805. 나무 자르기

    BOJ]2805.나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 이분탐색(Binary Search) 문제. . 0부터 나무의 가장 높은 높이를 찾아서 그 사이의 값들을 ..

    Algorithm/BOJ

    BOJ] 4179. 불!

    BOJ] 4179. 불! https://www.acmicpc.net/problem/4179 4179번: 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간 www.acmicpc.net 기본적으로 BFS알고리즘을 적용하지만, 한번 더 생각이 필요! 보통 2가지 방법으로 접근하는 것 같다. 불 한번 퍼지고, ..

    Algorithm/BOJ

    BOJ] 16283. Farm

    BOJ] 16283. Farm https://www.acmicpc.net/problem/16283 16283번: Farm 문제 목장 주인인 상배는 양과 염소들을 같이 기르고 있다. 기르는 양과 염소는 각각 한 마리 이상이다. 양과 염소는 같은 사료를 먹고, 양 한 마리는 하루에 사료를 정확히 a 그램 먹고, 염소 한 마리는 하루에 정확히 b 그램을 먹는다고 한다. 상배는 매일 아침 양과 염소가 각각 몇 마리인지를 확인하는 작업을 한다. 양과 염소가 각각 몇 마리인지 확인할 때, 양과 염소들이 돌아 다녀서 정확하게 그 수를 구하는 것이 쉽지 않았다. 대신에 양과 염소가 전체 www.acmicpc.net 연립방정식을 세워랏 연립방정식 세우기 문제의 조건 빼먹지 않기 해가 두개이상이어도 -1출력. 2의 조건때..

    SWEA] 4796. 의석이의 우뚝 선 산
    Algorithm/SWEA

    SWEA] 4796. 의석이의 우뚝 선 산

    SWEA] 4796. 의석이의 우뚝 선 산 SWEA 3131. 100만 이하의 모든 소수(Link) 문제의 저작권은 SWEA에 있습니다 시간초과 날 것 같았지만 그래도 깡으로 구현했다가 역시나 시간초과를 맞이했던 문제.. 구현하는 규칙을 찾는게 아니라, 수학적인 규칙을 찾는게 포인트 숫자를 나열하고 꼭지점(가장 높아졌다가 내려오는 부분)을 기준으로, 문제의 규칙이 깨지는 순간까지의 올라가는 횟수(UP)과 내려가는 횟수(DOWN)을 곱하면 된다. 규칙이 깨지면 다시 UP/DOWN은 0으로 초기화. 다시 규칙(우뚝 선 산)의 조건을 찾는다. - 두번째 숫자부터 끝까지 탐색하면서, 이전의 숫자가 현재의 숫자보다 작다면 UP++ 그렇지 않다면 down++ 단, 구별해주기 위한 조건을 더 넣어서 down하다가 u..

티스토리툴바