분류 전체보기
-
BOJ) 한 줄로 서기알고리즘/백준 2020. 8. 28. 16:33
한 줄로 서기 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 � www.acmicpc.net 풀이 고민하는 시간에 비해 코드가 짧은 문제였다. 처음에는 우선순위 큐에 담아서, 적절한 sorting을 통해 출력하려고 했다. 하지만, 메모리 초과가 떴고 다시 고민했다. 주어진 정보들을 우선적으로 배열에 담고, 마지막부터(키가 제일 큰 사람부터) 자신의 왼쪽에 몇명이 있는지를 인덱스로 그 사람을 추가하면 된다는 것을 알았다. 문제의 예시를 통해 설명하면 더 쉽게 이해가 될 것 같다. 1 2 3 4 2 1 1 0 1~4의 값을 담은 배..
-
BOJ) 톱니바퀴알고리즘/백준 2020. 8. 28. 16:27
톱니바퀴 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 풀이 생각보다 많이 까다로워서 푸는데 한시간정도 걸렸다. 가장 오래걸렸던 부분은 회전하기 전에 각 톱니바퀴들의 좌측과 우측의 극을 확인해야한다는 부분이다. 회전하면서 극을 새롭게 찾으면서 코드를 작성했어서, sholdTurn이라는 boolean 함수를 만들어 움직여야하는지 판별해줬다. 또한, 처음 입력받는 톱니바퀴의 상태는 가장 처음 인덱스가 문제의 설명처럼 좌측부터 있는 것이 아니라, 12시이 가장 맨 처음으로 주어진다는 것이 왜 이렇게 꼬아놓..
-
BOJ) 선분 위의 점알고리즘/백준 2020. 8. 28. 02:01
선분 위의 점 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 풀이 2달 전에 이 문제를 풀다가 계속 시간초과랑 오답이 번갈아 뜨면서 포기했던 문제였다. 오늘도 풀면서 3번이나 틀렸지만 결국 풀어냈다..!! 우선, 문제의 조건에 따라 각 점들은 int형으로 주어지고, 선분의 left, right 범위는 long 타입으로 주어진다. 그리고 완전탐색을 하게되면 가지치기를 엄청나게 잘하지 않는 이상은 시간초과가 뜬다고 생각했다. 그래서 binary search를 이용했다. 점들의 배열을 오..
-
부스트캠프 2020 챌린지 회고 & 멤버십 합격ETC 2020. 8. 27. 16:35
부스트캠프 챌린지 기간동안 일기 형식으로 매주 글을 남기려고 했는데, 정말 너무 바쁘게 지냈고 시간이 금방 지나가버려서 챌린지가 끝나고야 회고하며 적어본다. 정규 교육 시간은 10시 ~ 19시 (9시간)이며, 매 주 동료와 함께 개인 미션에 대한 의견을 나누는 피어세션이 진행된다. 매주 금요일에는 릴레이 프로젝트가 진행되는데, 월~목까지 미션에 지친 캠퍼에게 재밌는 개발 시간을 주기 위한 배려(?)라고 하셨다.... 이 두 개가 챌린지 과정의 스케쥴이다. 정말 간단해 보이지만, 재수할 때 만큼 공부를 하면서 겨우 따라가는 정도였다.. 그 정도로 나에게는 수준 높은 내용들이 많이 나왔다. 1주차 부스트캠프 1주차 정말 정신없이 일주일이 흘러갔다. 처음 OT때만해도 주어진 학습을 빨리 끝내고 하고싶은 공부를..
-
BOJ) 토너먼트알고리즘/백준 2020. 8. 27. 15:43
토너먼트 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 프로그래머스에서 풀었던 문제와 유사한(? 혹은 똑같은) 문제다. 그 당시 엄청 어렵게 풀었었기 때문에, 이번에는 쉽게 푼 분들의 풀이를 익히면서 풀었다. 먼저, 첫번째 방법은 left와 right의 숫자가 같아질 때 까지 /2를 해주는 것(경기를 진행하는 것) left와 right에 +1을 해주는 이유는 첫번째 경기는 1번부터 시작하기 때문이다. (1번 2번 경기 => (1+1)/2 === (2+1)/2 === 1) 두번째 방법은 XOR 연산 후, 2진수..
-
BOJ) 점프알고리즘/백준 2020. 8. 27. 15:30
점프 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 풀이 0,0을 시작으로 n-1,n-1까지 도달할 수 있는 경우의 수를 구하는 문제다. 각 인덱스에 적혀있는 칸만큼 오른쪽 혹은 아래로 움직일 수 있으며, 범위 밖으로는 움직일 수 없고 칸에 적힌만큼 정확히 이동해야한다. 그래서 모든 인덱스를 순차적으로 돌면서 dp 값이 0이 아니고, 해당 인덱스가 움직일 수 있는 값이 0이 아닐 때, dp를 최신화해줬다. 경우의 수를 누적시키며 답을 찾아간다고 생각하면 된다. 처음에는 dfs로 풀려고 생각하다가, 경로의 개..
-
BOJ) 누울 자리를 찾아라알고리즘/백준 2020. 8. 26. 15:46
누울 자리를 찾아라 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 세로와 가로를 직접 검증하는 메소드 두 개를 만들어서 쉽게 풀었다. 하지만, 기준점이 되는 좌표를 정하는 메소드로 만들었으면, 코드를 더 줄이고 중복을 줄일 수 있었을텐데 아쉽다. 확실히 문제 풀 때는 거기까지 생각하기는 힘든 것 같다. 아무튼, 내가 푼 방법은 가로와 세로 좌표를 각각 순차적으로 돌면서 다음 좌표가 빈칸인지 확인하며, 빈칸일 때까지 쭉 이어나가는? 방법이다. map에 직접 하는게 편하겠지만, 가로와 세로 각각 ..
-
BOJ) 섬의 개수알고리즘/백준 2020. 8. 26. 15:38
섬의 개수 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net 풀이 섬의 개수를 찾는 문제로, 인접한 8구역이 땅이면 이동할 수 있다는 조건을 가지고 있다. 제약 조건이 기존 4곳에서 대각선들만 추가됐을뿐, 일반적인 grouping 문제다. grouping 문제는 이전 문제들에서 많이 다뤘기 때문에 큰 풀이는 남기지 않으려고 한다. 다만, 좌 우의 상/하 대각선을 예외처리 없이 검사하기 위해 map의 크기를 입력받은 n,m값 +2로 설정해줬다는 점이 특이하다 정도는 주의할만 하다. 그리고, 한 메소드 당 하나의 기능만 ..