알고리즘

Link https://www.acmicpc.net/problem/2583 Note 프로그래머스에서 카카오 문제로 나왔던 문제랑 비슷한문제인데 정작 풀어보지 못했던게 아쉬워서 풀어본 문제.. 문제로는 어피치랑 무지가 나왔던거 같은데 그 때에는 BFS를 잘 몰라서 못 풀었던 문제로 배우고 난 뒤에 다시 한번 풀 기회가 없을까 하던 도중에 발견해서 풀어본 ...

BOJ 7568 덩치

BOJ 1065

Link https://www.acmicpc.net/problem/9663 Note 백준 Back Tracking 기초 문제 Back Tracking 대표 문제라고해서 풀어봤는데 이틀이나 걸렸다. 알고리즘을 2번 고쳤는데 처음에는 15 by 15 배열을 만들어 기록 하는 방식으로 제작했다가 타임아웃의 늪에 빠졌다. 같은 열을 제외하는 부분을 없애고 대...

Link https://www.acmicpc.net/problem/2644 Note 헛다리를 너무 많이 짚은 문제.. 이번에는 queue를 추가하지 않고 간이 형태로 제작해서 사용 처음에 부모가 누구인지만 아는 방법으로 해결하려고 했으나 자식으로 내려가야 되는 경우

Link https://www.acmicpc.net/problem/1107 언어 C++ 17 설명 어떤 멍청이가 버튼을 너무 세게 누르는 바람에 버튼이 고장나서 내가 원하는 채널로 갈때 내가 버튼을 몇번 눌러야 하는지 계산 하는 문제 왜 고장을 낸건지 너무 화가

Link https://www.acmicpc.net/problem/2997 Note 풀어도 이해가 안가는 문제.. 예제 말 뜻을 이해하는데 조금 오래 걸렸다 4 6 8 이면 정답이 10 이라는데 정답이 8이 될 수도 있다고 생각한다.... 4개중 3개만 알려 줬다

Link https://www.acmicpc.net/problem/1325 Note 참 간단해 보이는데 생각보다 생각을 오래 한 문제 조건이 몇가지 존재 했다. 첫번째로는 N이 10000이기에 인접행렬을 사용하게 되면 10000 * 10000 * 4 byte를 사용. 메모리 초과가 나온다. 두번째로는 A가 B를 신뢰한다에서 단방향 그래프라는 것인데,...

Link https://www.acmicpc.net/problem/1427 Note 시간제한 2초 최대 배열 크기 10 Bubble Sort로 구현해도 금방 푸는 문제 문제 찾던중 눈에 걸려서 풀어본 문제 알고리즘 log를 이용하여 자리 수 추출 각 자리 값을

Link https://www.acmicpc.net/problem/1205 Note Sorting 문제 구경중에 정답률이 생각보다 낮아서 풀어본 문제 알고리즘 크기 n 의 벡터 생성 내림차순 정렬 기준 점수보다 큰 점수와 같은 점수 개수를 저장 큰 점수 + 같은 점수 의 수가 랭킹 저장 수와 비교 비교 값이 목표 커트라인보다 작으면 큰 점수 +1 아...

Link https://www.acmicpc.net/problem/1987 Note DFS 문제 조건 시작하는 칸도 포함 : 즉 최대값은 1부터 시작 칸을 기준으로 중복 체크를 하는 것이 아닌 현재 칸의 알파벳을 밟은 적이 있는지를 검사 소스코드 2019-01-01 15:57:20에 Tistory에서 작성되었습니다.

Link https://www.acmicpc.net/problem/11724 Note 자료구조 책에서 DFS / BFS를 설명할 때 예시로 자주 들어지는 문제 방향이 없는 그래프 이기에 간선을 행렬로 저장시 간선을 양방향으로 저장 x y 가 주어진다면 xy와 yx를 둘다 등록해야 한다. 정점의 개수가 최대 1000개 인접 행렬 사용시 1,000 * ...

Link https://www.acmicpc.net/problem/2468 Note BFS 문제 최대 높이까지 전부 탐색해야 하는 경우 처음에 문제 읽을 때 기준이 몇인지 주어져야 하는데 왜 안주어지나 궁금했던 문제 최대 크기가 100 이기에 인접 행렬을 사용 현재 위치를 저장하는 mPoint 구조체를 사용 알고리즘 입력 값을 받으면서 최대 높이를...

Link https://www.acmicpc.net/problem/8595 Note 문자열 중에 히든넘버의 합을 구하는 문제 얼핏 보면 간단해 보이지만 함정이 존재한다. C++의 경우 string 클래스의 method를 이용해서 푸는 알고리즘이 존재하는데 간단히 설명하면 알파벳이 아닌 인덱스를 찾은후 삭제, 삭제된열에서 알파벳의 인덱스를 검색 그 사이...

Link https://www.acmicpc.net/problem/6603 Note DFS를 이용하여 조합을 생성해 출력하는 문제 이와 비슷한 문제도 여럿 존재 하지만 문제 제목이 끌렸다. 최대 숫자가 13개 이기에 DFS로 해도 시간이 100ms 이내로 나온다.

Link https://www.acmicpc.net/problem/2667 Note 4 - Connectivity로 몇개의 개체가 존재 하는지 크기는 얼마인지 오름차순으로 나열하는 문제 입력이 띄어쓰기로 들어오는것이 아닌 line 단위로 들어오는점에 유의하여야한다. n이 25로 제한되므로 최대 개체의 수는 313개 ( 25 * 12 + 13 ) 위치...

Link https://www.acmicpc.net/problem/2839 Note N kg의 설탕을 5 kg과 3 kg의 봉지에 나누어서 배달이 가능한지 묻는 문제 간단하게 생각해서 5로 나눈후 나머지가 3이면 가능하고 아니면 아닌 문제라고 생각했다가 틀린문제 N이 최대 5000, 5kg 으로 나누면 1000, 3kg로 나누면 1666.6번 최대로...

Link https://www.acmicpc.net/problem/1110 Note 크기 어렵지는 않다 문제에서 요구하는 사항을 그대로 구현 하면 되는 문제 더하고 나누고 합치고 소스코드 2019-01-05 19:40:57에 Tistory에서 작성되었습니다.

Link https://www.acmicpc.net/problem/2869 Note 시간제한 0.1초 =====> 반복문을 통해 풀면 Time out 규칙을 통해 결과를 뽑아 내야 한다. V - A 와 A - B를 가지고 결과를 뽑을 수 있는데 한가지 예외 사항이

Link https://www.acmicpc.net/problem/11724 Note 백준 11724 연결 요소의 개수 BFS 버전 알고리즘은 DFS와 동일 소스 코드 2019-01-01 17:14:29에 Tistory에서 작성되었습니다.

Link https://www.acmicpc.net/problem/1152 Note 단어의 개수를 헤아리는 문제 공백이 연속으로 나올 수 없기에 공백에 대한 처리는 문자열의 맨 앞과 끝만 처리 하면 간단한 문제 알고리즘 맨 앞자리가 공백인지 확인 맨 끝자리가 공백인지 확인 문자열에서 공백의 개수를 카운트 공백의 개수 + 1 - (맨 앞자리 공백시 ...

Link https://www.acmicpc.net/problem/1389 Note 케빈 베이컨의 여섯다리 : 위키백과_케빈 베이컨의 여섯다리 를 구현하는 문제 한 사람을 기준으로 친구 관계에 있는 사람들을 이어나가 몇 다리만에 그 사람과 연관이 있어지는지 확인 하는 문제 문제에서는 6단계의 법칙이라 했지만 검색을 하면 여섯다리로 나온다 자세한 내용은...

Link https://www.acmicpc.net/problem/1697 Note 분류는 백트래킹인데 질문 게시판을 보니 왜 백트래킹 문제인지 궁금하다는 문제 일단 BFS로 풀었는데 DFS로 풀면 시간 내에 돌아갈지 궁금하다 Local에서 몇가지 케이스를 돌렸을 때 제한 시간보다 오래 걸렸는데 맞았다고 뜨는거보니 신기하기도 하다 구현은 범위를 구분해...

Link https://www.acmicpc.net/problem/7576 Note 시작지점이 여러군데인 BFS 문제이다. 일수를 구분 해야하기 때문에 오늘에 해당하는 Queue와 내일 확인해야할 Queue로 분리해서 문제를 풀었다. 익은 토마토를 기점으로 주변으로 1칸씩 확산하는 BFS이기에 문제 자체는 간단하다. 또한 box의 내용이 변경되어도 괜...

Link https://www.acmicpc.net/problem/15683 Note 5 종류의 최대 8개의 감시카메라가 최대 8 x 8의 정사각형 방을 감시하는데 최소 사각지대를 구하는 문제이다. 문제 내용도 간단하고 무엇보다 설명이 자세하게 잘 되어있던 문제 예제 또한 많았기에 예제가 정상적으로 전부 돌아간다면 반례는 크게 생각을 하지 않아도 될 것...

Link https://www.acmicpc.net/problem/7562 Note 기본 BFS가 4방향인 점과는 다르게 8방향이고 인접한 칸으로 이동하는 것이 아닌 몇칸 떨어져 있는 위치로 이동하는 것이 특징 이전 BFS문제와 똑같이 구현하고 방향성을 8개로 늘리고 값만 조금 수정하는 것과는 크게 차이가 없는 문제 4방향 BFS를 if - else ...

Link https://www.acmicpc.net/problem/2455 Note 탄사람 - 내린 사람으로 계산하면 아마 틀리지 않을까? 8개의 입력 으로 되어 있으니 탈 때 내릴 때 구분해서 만들자 알고리즘 내릴 때 탈 때 를 구분해 현재 인원수에 + 또는 - 를 한다. 현재 최대 인원수랑 비교해서 최대 인원수를 갱신한다. 출력 소스코드 2...

Link https://www.acmicpc.net/problem/1094 Note 자르고 붙이고 자르고 붙이고 반복문을 통해 구현을 하는 내용이다. 라고 생각할 수도 있지만 위 문제의 분류에는 수학이 포함되어있다. 문제 설명대로 풀면 합을 계산하고 현재 가장 작은 막대기를 계산하고 해야 하지만 위 문제는 2진법에 관한 문제이다. 23의 경우 2진법으...

Link https://www.acmicpc.net/problem/1966 Note 우선순위 가 포함된 큐 이다. 말 그대로 우선순위 큐를 이용하는 문제다. Max Heap을 이용하면 쉽게 풀리는 문제다. 이번 문제는 Max Heap을 이용하지 않고 문제 자체에 충실하게 구현했다. 무한루프를 사용하지 않고 만들고 싶었지만 최근 결과를 보니 거의다 무한루...

Link https://www.acmicpc.net/problem/1759 Note 조금 간단한 백트래킹 0과 1로 이루어진 순열을 만들어 낸다 라고 생각하면 편하다. 모음이 1개 이상 , 자음이 2개 이상일 경우에만 출력하도록 조건을 걸면 된다. 알고리즘 알파벳을 입력받아 - 'a'를 한뒤 사용할 수 있는 알파벳을 식별하는 배열에 넣는다. 현재 알...

Link https://www.acmicpc.net/problem/2580 Note 두뇌 회전으로 많이 푸는 스도쿠를 백트래킹을 이용해서 정답을 찾는 문제 스도쿠의 규칙인 가로, 세로, 박스 안에는 1 ~ 9 까지 단 1개씩만 들어가야 한다. 를 만족시키기만 하면 된다. 가로에서 필요한 값과 세로에서 필요한 값, 박스에서 필요한 값으로 나누어서 세 개...

Link https://www.acmicpc.net/problem/1699 Note 어떤 자연수 N에 대하여 제곱수의 합으로 표현 할 때, 제곱수의 최소 개수를 구하는 문제 간단하게 생각하면 가장 큰 제곱수를 빼면서 0 ~ 3 사이의 결과가 나올 때 그 값을 더해

Link https://www.acmicpc.net/problem/1010 Note 만들 수 있는 다리의 총 합을 구하는 문제 DFS 처럼 생각해서 가지치기를 했더니 최대 다리 개수를 놓았을 경우에 너무 오래 걸렸다. 점화식은 간단하다 RESi = RESi-1 + RESi 예외 조건은 순서가 역전 되지 않게 만들어 주기만 하면 된다. 어렵게 생각하면...

Link https://www.acmicpc.net/problem/1932 Note DP에 대해서 공부해보자! 나올 수 있는 모든 경우의 수를 계산한다.! 하지만 옛 결과를 가지고 계산을 한다! 위 피라미드 문제가 DP에 대해서 학습하기는 편한거 같다. 위의 값에 대해서 왼쪽을 더했을때, 오른쪽을 더했을 때의 값 중 큰 값을 넣으면 된다. 눈에 보...

Link https://www.acmicpc.net/problem/10989 Note 개수가 많아서 시간제한이 3초다, 근데 메모리는 고작 8 MB 배열을 전부 저장하게 되면 메모리는 견디지 못한다. 메모리가 넉넉했더라면 Quick Sort로 구현 해도 정답이 되겠지만 위 문제는 Quick Sort로 구현하는게 아니다. 중복되는 수가 존재하기 때문에...

https://www.acmicpc.net/problem/110571234, 55557 과 같이 모든 자리의 수가 다음 자리 수보다 같거나 큰 수인 경우의 수를 헤아리는 방법최대 입력이 1000 이고 개수를 10007로 나눈 나머지를 구해 한다.long lon

Link https://www.acmicpc.net/problem/1026 Note S 의 값을 최소로 만들어야 하는 문제 위 공식을 통해 최소로 만들기 위해서는 a는 오름차순으로, b는 내림차순으로 정렬하면 된다. 문제에서는 재배열 하면 안된다고 쓰여 있지만 정답과는 관련이 없기에 정렬 해주자 알고리즘 a와 b를 입력 받는다. a를 오름차순 정렬...

Link https://www.acmicpc.net/problem/10026 Note 정상인이 봤을때의 그룹 수와 적록색약인 사람이 봤을 떄 그룹 수를 출력하는 문제 기존 문제와 다른점은 동일시 해야 하는 경우가 존재한다는 것 정상인 입장의 그룹 수는 R G B로 나누어서 그룹 수를 구하면 되지만 적록색약인 경우 R 이나 G일때 R , G를 전부 같은...

Link https://www.acmicpc.net/problem/2292 Note 입력받은 숫자 n이 1을 포함하여 몇번째 외곽에 존재 하는지 푸는 문제 친구가 어떻게 풀지 물어봐서 풀어본 문제 이번 문제는 푸는 방법이 여럿 존재한다. 점화식이 너무 선명하다 1을 기준으로 오른쪽 대각선의 값이 6 * i 를 더한 값이 계속 반복되기 때문 반복문을 통...

조건이 몇개 걸려있어서 약간 까다로웠던 문제얼마나 연결될지 몰라서 일단은 BFS로 풀었다. 기존 문제들과 다른 점이라면 최소 4개가 연결 되어 있어야 하기 때문에무턱대고 방문 했다고 값을 . 으로 바꿔주면 안됬다.일단은 연결 되어있는 개체 수를 저장하고 나중에 그 값이

Link https://www.acmicpc.net/problem/2589 Note 어딘가에 숨어있는 보물의 최단거리의 최대 경우를 탐색하는 문제 DFS는 시도해보지 않았지만 경우의 수가 커질 경우 DFS는 시간초과가 예상이 된다. 모든 육지에 대해서 BFS를 진행해야한다. 20 by 20에서 모든 위치를 L로 초기화 시켜서 돌려보았더니 1초를 살짝 ...

Link https://www.acmicpc.net/problem/2193 Note 0으로 시작하지 않으면서 1이 연속으로 두번 나오지 않는 N 자리의 이진수의 개수를 구하는 문제 각각의 경우를 계산 해보면 1 : 1 ( 1개 ) 2 : 10 ( 1개 ) 3 : 100 101 ( 2개 ) 4 : 1000 1001 1010 ( 3개 ) 5 : 10000...

Link https://www.acmicpc.net/problem/11726 Note 2 x n 에 1 x 2, 2 x 1 타일로 채우는 방법의 수를 구하는 문제 DP의 기초를 다지기에 좋은 문제 먼저 결론부터 말하면 위 문제는 피보나치 수열의 형태를 띈다 2 x 5까지 경우의 수를 계산해 보면 피보나치 수열의 형태를 가진다 주의할 점은 경우의 수를...

Link https://www.acmicpc.net/problem/1149 Note 이웃한 집과 같은색으로 칠하지 않으면서 모든 집을 칠할 때 드는 비용의 최솟값을 출력하는 문제 이전 집의 색을 기억해서 같은 색이면 그 색을 제외하고 최솟값을 구해 마지막까지 칠하는 경우 모든 경우에서 최솟값을 선택하는 그리디 알고리즘을 적용시키면 문제의 정답이 나오지...

Link https://www.acmicpc.net/problem/1912 Note 임의의 수열에 대해서 연속된 수의 합이 최대를 구하는 문제 예제만 보고 양수의 합을 구하다가 다음 수가 음수가 나오면 현재 까지의 합을 남기는 알고리즘을 만들었다가 오답 한개를 추가하고 시작했다. 위 예제에서 -35를 21 뒤에 놓는 형태로 바꾸면 문제에 숨겨진 함정...

Link https://www.acmicpc.net/problem/14888 Note 수 사이에 연산자를 넣어 최대 최소가 되는 경우를 찾아내는 문제 수는 신경쓰지 않고 연산자를 할당하는 부분에 신경을 기울이면 된다. 또한 연산자의 개수가 정해져 있기 때문에 현재까지 몇개를 할당 해 줬는지 기억을 해줄 필요가 있다 연산자가 n-1개가 아니라 n개라면 ...

Link https://www.acmicpc.net/problem/1107 Note 어떤 멍청이가 버튼을 너무 세게 누르는 바람에 버튼이 고장나서 내가 원하는 채널로 갈때 내가 버튼을 몇번 눌러야 하는지 계산 하는 문제 왜 고장을 낸건지 너무 화가난다. 처음으로 백준 게시판에 안된다고 반례 찾아달라고 질문 올린 문제, 테스트케이스만 30개 이상 돌려본...

Link https://www.acmicpc.net/problem/11399 Note 인행의 ATM 기기의 사용시간을 최소로 구하는 알고리즘 그리디 알고리즘이라 분류하고, 알고리즘은 정렬로 짜고, 결과값을 위해서는 DP를 사용한다. 정렬하고 전 사람이 사용하기까지 걸린 시간에 내 시간을 더한다. 다 합친다. 알고리즘 사람들의 사용 시간을 오름차순으...

Link https://www.acmicpc.net/problem/11047 Note 내가 가지고 있는 동전의 종류를 가지고 동전이 최소로 몇개만 있으면 되는지 푸는 문제 일상생활에서 내가 잔돈을 어찌 냈더라? 지폐를 안쓰고 내가 동전을 낸다면 어떤 순서로 낼지 생각해보자, 거스름돈이 없게 만들면서 알고리즘 내가 낼 수 있는 가장 큰 동전부터 값이...

Link https://www.acmicpc.net/problem/10610 Note 왜 30을 존경하는지 모르는 미르코덕에 길거리에서 찾은 수를 가지고 30의 배수가 되는 가장 큰 수를 만들어야 한다. 리모콘부터 시작해서 세상에는 정말 독특한 친구가 많다 이 문

Link https://www.acmicpc.net/problem/2875 Note 백준대학교에서는 총장님의 권력이 막강해 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는데 올해는 인턴십 때문에 사람을 빼야한다. 최대한 사람좀 많이 남겨보라는 총장님의 지시를 이행하는 문제 최대가 100번이기에 반복문을 사용해도 괜찮다. 생각을 그대로 옮기면 되는...

Link https://www.acmicpc.net/problem/1049 Note 최대 100줄짜리 기타를 치시거나 6현 기타 17개를 동시에 치실줄 아시는 세계적인 기타 플레이어 김지민씨가 새로운 줄을 사거나 교체 해야할 때 가장 싸게 사면 얼마에 살 수 있는지

Link https://www.acmicpc.net/problem/1475 Note 다솜이가 플라스틱 숫자로 방 번호를 만들 때 필요한 세트의 최소 개수를 구하는 문제6과 9를 같은 문자로 취급 하면서 개수를 셀 때만 다른 문자로 취급하는게 중요한 문제숫자는 길어야 8자리 수 이다. 6이 남아 있으면 9로 대체 할 수 있고 9가 남아 있으면 6으로 대체 ...

Link https://www.acmicpc.net/problem/1157 Note 알파벳 대소문자로 이루어진 단어가 주어지면, 그 단어에서 가장 많이 쓰인 알파벳을 대문자로 출력한다. 대, 소문자를 구별하지 않으면서 출력은 대문자로 해야한다. 라는 조건은 편하게 하려면 대문자로 계산하는게 마음 편한다로 보인다. 따라서 입력 받은 단어에 대해서 소문자...

Link https://www.acmicpc.net/problem/7569 Note 7576번 토마토의 3차원 버전 문제, 익은 토마토가 상하좌우 뿐만이 아닌 위 아래 칸으로 번지는 경우에 대해서도 계산 해야 하는 문제 과거 7576번 토마토 문제를 푼 경험이 있다면 간단한 문제다. 익은 토마토를 기준으로 위칸이나 아래 칸으로 가는 경우를 추가해 주면...

Link https://www.acmicpc.net/problem/14502 Note 바이러스가 유출 되었을 때 벽 3개를 이용해서 최대한 많은 안전한 공간을 만들어야 하는 문제이다. BFS와 Brute Force를 동시에 사용 해야 하는 문제 바이러스가 퍼지기 전에 벽을 3개만 더 추가해서 최대한 많은 공간을 확보 해야 한다. 문제를 풀 때 크게 새...

Link https://www.acmicpc.net/problem/9019 Note 네 개의 명령어가 있는 계산기를 사용해 시작값이 목표값 까지 가는 최단 과정을 요구하는 문제 4가지의 연산 경로 (D S L R)가 존재하고, 현재 결과를 저장 해야하며 최소한의 명령어를 생성 해야 한다. Brute Force로 얼핏 가능해 보이지만 질문 게시판을 찾...

Link https://www.acmicpc.net/problem/1600 Note 말이 되기위한 원숭이가 자신의 능력과 말을 흉내내는 능력을 섞어 쓰면서 시작지점에서 목표 지점까지 최대한 빠르게 가는 방법을 알아내는 문제다. 움직일 수 있는 경우의수는 총 12가지로 현재 위치에서 인접한 위치로 움직이는 경우와 체스의 나이트처럼 움직이는 방법이다. 이...

Link https://www.acmicpc.net/problem/2661 Note 1, 2, 3으로 이루어진 수열 중 인접한 두개의 부분 수열이 동일한 하지 않은 최솟값 수열을 출력하는 문제이다. 첫 자리를 제외하고 나머지 자리는 2번씩 검색해야하는 느낌이 드는 문제이다. 시간 제한이 1초인 점이 의심스럽다. 하지만 위 문제는 간단히 생각하면 앞자리...

Link https://www.acmicpc.net/problem/1003 Note 문제에 나와 있는 소스 코드를 기반으로 0이 출력되는 경우와 1이 출력 되는 경우의 수를 출력하는 문제 저 함수를 직접 코드화 시켜서 printf 문 대신 0 인덱스를 1씩 추가시키면 시간 초과의 늪으로 들어간다 테스트 케이스 범위도 좁은 만큼 시간 제한도 0.25초로...

Link https://www.acmicpc.net/problem/1405 Note 통제할 수 없는 미친 로봇이 n번의 행동 중 로봇의 이동 경로가 단순한 경우의 확률을 구해 내는 문제 앞선 문제의 경우와 다른 점은 확률을 구해야 한다는 점이 가장 눈에 띈다. 이동 경로를 구해야 되는 문제이기 때문에 BFS/DFS를 사용 해야 한다. 하지만 이번 문제...

Link https://www.acmicpc.net/problem/5567 Note 상근이가 결혼식에 학교 동기 중 자신의 친구와, 친구의 친구를 초대할 때 상근이가 초대할 친구의 수를 구하는 문제이다. 동기의 수가 최대 500명이기 때문에 인접리스트를 써도 무방하다. 또한 a - b가 친구이면 b - a도 친구라는 점에서 양방향 그래프로 추가 하면 된...

Link https://www.acmicpc.net/problem/1978 Note 100개 이하의 주어진 수 중 소수인 수의 개수를 구하는 문제 분류에 적혀있는 에라토스테네스의 체를 연습하기 위한 문제이다. 2 이상의 수 에 대하여 소수인 수의 곱 값은 소수가 아니다 라는 정의를 이용한다. 대표적인 소수 2를 기준으로 4, 6, 8, 은 2의 곱이므...

Link https://www.acmicpc.net/problem/1652 Note 영식이가 누울 수 있는 자리의 갯수를 가로와 세로로 구분해서 출력해주자. 입력은 문자열로 주어진다. 문자 사이에 공백이 없다. 한번에 받아야 한다. 수학탭에 있지만 왜 수학문제인지 조금 궁금하다. 문자열 처리에 좀 더 가깝지 않을까 하는 의문이 들기도 한다. 가로와 세...

Link https://www.acmicpc.net/problem/1076 Note 저항에 있는 색 3개를 가지고 현재 저항의 값이 몇인지 출력 하는 문제 현실의 저항에서 오차 범위를 제외한 문제 역시 수학보다는 문자열 처리가 조금 더 알맞지 않을까 하는 문제이다. 색의 첫번째 두번째는 두자리 수의 각각 10의 자리 1의 자리를 의미하고 세번째 자리는...

Link https://www.acmicpc.net/problem/1726 Note 공장의 로봇을 제어하는 명령어 2가지를 통해 지정한 시작 지점에서 목표 지점까지 이동하고 바라보게 하는 최소시간을 구하는 문제 최소시간, 이동 2가지 키워드에서 BFS를 사용해야 한다. DFS를 사용하게 되면 상당히 오랜 시간이 걸릴 뿐더러 최소 명령을 확인하는 문제이...

Link https://www.acmicpc.net/problem/5427 Note 불이난 건물에서 상근이가 탈출 하려고한다. 상근이가 얼마만에 탈출 할 수 있는지 알아보자 일단 탈출 할 수없는 경우가 존재하기 때문에 경건한 마음으로 문제를 풀어보자.. 불과 상근이의 이동중 먼저 BFS를 사용해야 하는 부분은 불이다. 불이 먼저 번진 것으로 가정해야 ...

Link https://www.acmicpc.net/problem/1074 Note 그림과 같이 2^N by 2^N 배열을 Z 모양으로 순차적으로 방문한다고 할 때 r, c 좌표의 값이 몇 번째로 방문이 되는지를 알아내는 문제 수학 탭에서 문제를 발견해 들어왔다. 기존 문제들이 r, c가 주어진다면 특정 공식에 의해 값이 추출 되는 방식이어서 여러 값...

Link https://www.acmicpc.net/problem/2864 Note 5와 6을 잘못 볼 수 있는 상근이가 A와 B를 보고 생각할 수 있는 최댓값과 최솟값을 출력한다. 소스코드 2019-01-29 20:54:24에 Tistory에서 작성되었습니다.

Link https://www.acmicpc.net/problem/1356 Note 어떤 수를 10진수로 표현한 후 그 수를 두 부분으로 나눠 각 부분의 자리수의 곱이 일치하는 경우가 존재하는 수를 출력한다. 유진이란 말을 듣고 떠오른건 미스터 션샤인의 유진 초이... 주어지는 수를 통해 두 부분으로 나눈 후 각 자리의 곱이 일치하는 경우가 존재하면 ...

Link https://www.acmicpc.net/problem/1920 Note N개의 정수가 들어있는 배열 A에서 M개의 값이 들어있는 배열 M에 각각의 값이 N에 존재하는지 확인하는 문제 문제 탐색의 속도를 묻는 문제라는 느낌이 강한 문제였다. 그렇다면 방법은 Binary Search 하나밖에 없다. Binary Search 를 사용하기 위해서...

Link https://www.acmicpc.net/problem/14786 Note A, B, C가 주어졌을 때, Ax + Bsin(x) = C를 만족하는 x를 찾아야 한다. 정말 잘 구한거 같은데 왜 틀리는지 알 수 없던 문제. 맞은 사람도 많지 않고 질문도 많지 않았다. tc로 사용했던 것도 다 맞았는데 너무 많이 틀렸었다. 알고리즘은 단순하다....

Link https://www.acmicpc.net/problem/2572 Note R G B 3가지 색깔이 있는 보드게임 카드를 가지고 문제의 룰을 통해 얻을 수 있는 최대 점수를 구하는 문제 처음에 접근을 카드를 기준으로 접근을 한게 아닌, 정점을 기준으로 접근을 했더니 아니나 다를까 메모리가 터졌다. 문제의 접근을 현재 위치와 이번에 내는 카드를...

Link https://www.acmicpc.net/problem/4179 Note BOJ 5427 - 불 문제와 유사합니다. 설명 및 알고리즘 - > 링크 소스코드 2019-02-01 04:09:01에 Tistory에서 작성되었습니다.

Link https://www.acmicpc.net/problem/12761 Note 동규와 주미가 돌 다리 위에 있다. 동규가 한번에 +-1 칸을 이동하거나 스카이콩콩을 이용해 +- A B 칸만큼 이동하거나 현재 위치의 A B 배 만큼 이동할 때 동규는 주미를 최소한으로 이동해서 만나는 경우를 구하는 문제 일단 문제 자체가 일직선 상의 돌 다리 위 ...

Link https://www.acmicpc.net/problem/1963 Note 소수를 좋아하는 창영이가 4자리 소수인 현재 비밀번호를 다른 4자리 소수인 비밀번호로 바꾸려고 할 때. 한번에 한 자리씩 바꾸어서 다른 비밀번호가 되는 최소의 경우의 수를 출력한다. 소수에 집착하는 창영이 그리고 비밀번호를 한 번에 한 자리 밖에 못바꾸는 괴상망측한 게...

Link https://www.acmicpc.net/problem/2309 Note 아홉 명의 난쟁이 중 일곱명을 선택해 난쟁이의 키가 100이되는 경우에 난쟁이의 키를 오름차순으로 출력하자. 오름차순으로 출력 하기 위해 9명의 난쟁이를 먼저 오름차순으로 정렬하자. 9명중에 7명을 조합하는 재귀 함수를 만든다. 합이 100이면 출력하자. 최종 경우에 합...

Link https://www.acmicpc.net/problem/14501 Note 정말 부러운 상황에 있는 백준이가 퇴사를 하려한다, 상담 계획이 주어져 있을 때, 최대로 돈을 많이 벌 수 있는 금액을 출력해주자. 백준이가 퇴사 하기 전까지 최대한 많은 상담을 해야한다. 백준이가 돈을 더 벌기 위해서 일을 일부러 건너 뛰는 경우도 존재 한다. 또한...

Link https://www.acmicpc.net/problem/2573 Note 지구 온난화로 인하여 빙산이 녹아 내릴때 주어진 빙산이 녹아 2개 이상의 빙산으로 분리 될 때 까지 얼마만큼의 시간이 걸리는지 알아내는 문제 먼저, 빙산이 녹는 양은 0이 아닌 현재 위치를 기준으로 상하좌우 4방향의 값이 0인 즉 바닷물인 부분의 수 만큼 녹아 내린다....

Link https://www.acmicpc.net/problem/6593 Note 정육면체가 금! 으로 되어있는 상범 빌딩에서 시작지점과 탈출지점이 알려질 때 얼마나 빠르게 상범 빌딩에서 탈출 할 수 있는지 구하는 문제 각 변의 길이가 1인 단위 정육면체의 금! 으로 되어있는 상범빌딩에 갇혔다. 한 번에 움직일 때 1분이 걸린다. 구해야 하는 경우가...

Link https://www.acmicpc.net/problem/1342 Note 문자열 S의 문자를 재 배치 하였을 때 모든 문자가 인접한 문자와 같지 않은 문자열의 개수를 찾는 문제 문자열을 재 배치 할 때 현재 위치를 기준으로 양옆을 생각하지 않고 이전 문자가 무엇 이었는지만 기억 하면 된다. 문자열을 진짜로 재 배치 한다는 생각보다 앞자리부터...

Link https://www.acmicpc.net/problem/1339 Note 단어로 된 수학 문제를 푸는 숙제를 받은 민식이를 도와주자. 각 알파벳에 대해서 0 ~ 9 사이의 숫자를 대입했을 때 합이 최대는 값을 찾아주자 백트래킹으로 풀기에는 생각보다 간당간당한 문제 처음에는 사용되는 알파벳에 9부터 역순으로 값을 대입해 보는 방법을 사용했지만...

Link https://www.acmicpc.net/problem/16922 Note I V X L 4개로 구성된 로마 숫자 N개를 이용하여 서로 만들 수 있는 다른 수의 총 가지 수를 출력하는 문제. 한개의 경우에 대해서 총 4개의 가지가 존재하는 전형적인 브루트 포스 문제 앞에서 미리 탐색을 한 경우에는 경우의 수에 추가 하지 않도록 확인 하는 변...

Link https://www.acmicpc.net/problem/1717 Note 0 ~ n 까지 총 n + 1개로 구성된 집합이 합 연산과 두 원소가 같은 집합에 속해 있는지 구하는 연산을 진행 할 때 같은 집합에 속하는지 확인 하는 연산에 대해서 결과 값을 출력해주어야 한다. Dis-Joint Set에 대한 기초적인 문제, 추가로 위 문제에서는 ...

Link https://www.acmicpc.net/problem/4195 Note 친구를 모으는 것이 취미인 민혁이가 자신의 친구 관계를 줄 때, 두 사람의 친구 네트워크에 현재 몇명이 있는지 구하는 프로그램을 만들어주자. Disjoint-Set을 이용하여 친구 관계를 Tree형태로 저장한다, 또한 입력되는 순서에 따라 결과 값이 다르게 저장된다. ...

그래프의 정보가 주어지고, 그래프의 일부 내용이 변경 되었을 때 주어지는 질의에 대해서 답을 출력해주는 프로그램을 작성한다.여태껏 문제와는 문제를 보는 방식이 조금 달랐던 문제. 좋은 내용을 배웠다.주어지는 질의에 대해서 질의를 역순으로 해결해 나가면서 정답은 질의 순

Link https://www.acmicpc.net/problem/2463 Note 정점과 가중치가 있는 간선으로 이루어져있는 그래프에서 특정 방식으로 된 연산을 진행 할 때 연산의 총 합을 구하는 프로그램을 작성하자 처음에 봤을 때 이해가 조금 안됬던 문제. 연산은 쉽게 이해가 가지만 총 합이라는 의미가 이해가 잘 안갔었다. 결론은 주어지는 모든 정...

Link https://www.acmicpc.net/problem/2805 Note 환경에 관심 많은 상근이가 목재 절단기를 이용해 나무를 잘라 원하는 길이를 가져가기 위해 설정 하는 높이의 최대 값을 구하자 환경에 관심이 많으면 나무를 자르지 말지.. 왜 고통스럽게 ㅠㅠ 이분 탐색 문제라는 느낌이 들지만 기준을 잡기 너무 어렵다. 그리고 범위를 이동...

Link https://www.acmicpc.net/problem/2110 Note 도현이가 언제나 와이파이를 즐기기 위해 공유기 C개를 설치하려고 할때 인접한 공유기 사이의 거리를 가능한 크게 해서 설치 하려한다. 그 때 최대 값을 출력해주자 문제가 이해가 안간다. 코드를 봐도 모르겠다. 스터디에서 코드를 받고 코드를 보고 이해하려 했으나. 문제가 ...

Link https://www.acmicpc.net/problem/1072 Note Spider Solitaire를 즐기는 형택이가 현재 게임 승률에서 몇 판 더 했을 때 자신의 승률이 바뀌는지 알아보자. 처음에는 예외를 잡는 부분이 생각보다 어려웠다. 최대 시도를 10억번을 기준으로 이분 탐색을 진행해서 10억이 넘어가면 -1로 출력하는줄 알았으나....

Link https://www.acmicpc.net/problem/1541 Note 양수, +, -로 구성된 식에 적절한 괄호를 추가해 결과 값을 최소로 만드는 경우의 값을 출력한다. -가 등장하는 순간 그 뒤에 + 식을 전부 괄호로 묶으면 괄호 안의 결과 값을 빼는 모습이 된다. 즉 -가 등장하기 전 까지의 합과, 등장한 후의 합을 빼면 그 결과 값...

Link https://www.acmicpc.net/problem/14891 Note N, S극 중 하나를 가진 톱니 8개를 가진 톱니바퀴 4개가 입력된 값에 따른 회전을 한 뒤의 상태를 특정 점수를 통해 표현한다. 문제 자체는 크게 어렵지 않다. 현재 상태를 기준으로 돌아가야 할 톱니와, 돌지 않아야할 톱니를 구분 하기만 하면 된다. 다만 탐색을 진...

Link https://www.acmicpc.net/problem/6324 Note URL이 주어질 때 URL을 프로토콜, 호스트, 포트, 경로 4개로 분해해서 보여주는 문제. 처음 시도 했을 때로부터 무려 5개월만에 해결한 문제. 출력 형식을 맞추는게 생각보다 까다로웠다. 보이는 대로 처리 하면 바로 틀렸습니다가 나오는데. 프로토콜이나 호스트에 대해...

Link https://www.acmicpc.net/problem/16944 Note 큐브러버가 리듬 테트리스에서 비밀번호를 만들 때 규칙을 지킨 비밀번호를 만들기 위해 현재 비밀번호에서 몇자리를 더 수정 해야 하는지 구하는 문제 설명은 길지만 내용은 간단한 문제 비밀번호의 조건을 크게 길이가 6글자를 만족 하는지, 숫자 ~ 특수문자 까지의 조건을 몇...

Link https://www.acmicpc.net/problem/10757 Note 최대 10의 1만 제곱의 범위의 수 2개가 주어질 때 2개의 합을 구하는 결과를 작성하시오 원하는 모습으로 구현은 됬지만 코드가 보기보다 스파게티 코드가 됬다. 전가산기를 구현한다는 느낌으로했지만 생각보다 많이 꼬였다. 제약사항 10의 1만 제곱의 범위를 받을 수...

Link https://www.acmicpc.net/problem/12100 Note 과거 유행했던 2048 게임을 모방한 Easy버전의 2048게임을 구현하자. 2048 게임을 해봤다면 문제 내용은 쉽게 이해 할 수 있는 문제. 단 새로운 블록이 추가 되지 않고. 결과값으로는 만들 수 있는 최대값을 출력 해야 한다. 최대 5번 이동을 한다는 제약, ...

Link https://www.acmicpc.net/problem/13458 Note 총 감독관이 a명을 감시하고 부 감독관이 b 명을 감시할 때 모든 시험장에서 필요한 감독관의 수를 구하여라. 알고리즘 자체는 쉽다. 각 시험장에는 총 감독관 1명만이 필수로 배치 되어야하고, 나머지 인원을 감시하기 위해서 부 감독관이 배치가 된다. 각 시험장에 총 감...

Link https://www.acmicpc.net/problem/14499 Note 모든 면에 0이 적혀있고, 지도 위를 움직이면서 값이 복사되고 지도의 값이 바뀌는 특별한 주사위 게임이 있다. 명령이 주어졌을 때 위를 향하고 있는 주사위의 눈의 값을 출력해주자. 문제 내용은 아주 간단하다. 다만 구현에 있어서 가장 난해한 부분은 주사위를 어떤 방식...

Link https://www.acmicpc.net/problem/3190 Note Dummy라는 도스 게임의 규칙을 적용하여 뱀이 몇 턴만에 죽는지 구해보자. 처음 문제를 구현 할 때 머리를 90도 회전 한다는 규칙을 90도 회전 후 1칸 진행으로 이해해 구현해 예제가 잘못됬다고 생각했었다. 머리를 90도 회전 한다는건 90도 회전하는 것으로 1턴을...

Link https://www.acmicpc.net/problem/17070 Note 시작 지점에서 가로로 놓여있는 파이프를 연결해 목적지에 연결 할 수 있도록 파이프를 배치 하는 방법의 가지 수를 출력해주자. 이번 삼성 A형 1번 문제에서 몇가지 조건이 빠진 문제다. 나머지 조건은 똑같다. 크게 다른 점이라면 문제가 조금 친절한 점 정도일까.. 파이...

Link https://www.acmicpc.net/problem/16675 Note 민성이랑 태경이가 양손 가위바위보를 할때 누가 이길지 판단해주는 프로그램을 작성하자 소스코드 2019-03-31 23:22:52에 Tistory에서 작성되었습니다.

Link https://www.acmicpc.net/problem/16674 Note 주어진 수가 2018과 관련 없는 수인지, 관련있는 수인지, 밀접한 수인지, 묶여있는 수인지 구분해서 출력해주자 양의 정수 n의 범위가 int 범위에 포함 되지만 처리는 문자열 처리와 비슷하기에 입력을 문자열로 받는다. 각 자리의 수를 헤아리기위한 배열을 두어 각 자...

Link https://www.acmicpc.net/problem/16676 Note 다이어리를 꾸미려는 근우를 위해 스티커 팩을 몇 개 사야하는지 알려주자 결과값 = 문자열 길이 라고 생각하면 함정이 빠지게 된다. N을 출력한다면 문제가 없지만 0 ~ N 까지이기 때문에 각 자리 숫자가 최대로 중복되는 경우를 생각 해야 한다. 처음으로 각 자리가 중...

Link https://www.acmicpc.net/problem/15947 Note 커피를 마신 석환이가 "아기 석환" 노래를 부를때 n 번째로 부르는 단어가 무엇인지 출력해주자 크게 고려할 사항이 없다. 14번마다 내용이 반복되기 때문에 경우를 나누어주면 된다. tururu와 turu가 계속 ru의 개수가 늘어나기 때문에 경우만 나누어서 출력해준다...

Link https://www.acmicpc.net/problem/16563 Note 입력되는 n개의 수의 소인수들을 오름차순으로 출력한다. 소수를 구하는게 가장 큰 관건, 에라토스테네스의 체를 이용하여 소수 목록만 구하면 된다. 오름차순이기때문에, 2부터 시작해서 비교하면 된다. 알고리즘 에라토스테네스의 체를 통해 1 ~ 100만 사이의 소수를 ...

Link https://www.acmicpc.net/problem/1037 Note N의 n개 진짜 약수가 주어질 때 N을 구하는 프로그램을 만들자 N의 약수중 1과 N이 아닌 약수를 진짜 약수라고 한다. n이 홀수 일 떄와 짝수일 때가 있는데 홀수일 경우는 N이 제곱수이다. N을 구하기 위해서는 최대 값과 최소 값만 알면 상관이 없지만, 이번 문제에...

Link https://www.acmicpc.net/problem/1212 Note 주어진 8진수를 2진수로 출력하자. 문제는 크게 어렵지 않다. 8진수와 2진수의 관계만 안다면. 2진수를 3자리씩 묶어 10진수로 변환하면 8진수가 된다. 위 문제는 반대로 만들면 된다. 알고리즘 8진수를 입력 받는다. 첫자리인경우 1,2,3 에 한정해 직접 출력한...

Link https://www.acmicpc.net/problem/1463 Note 주어진 n을 특정 연산을 통해 1로 만드는 횟수의 최소값을 구한다. 문제 분류가 DP지만 BFS로 해결된다. 결과값이 최대 10만이기때문에 가능한것 같다. 3으로 나눈경우, 2로 나눈경우, 1 뺀 경우 3개로 나누어서 BFS를 진행한다. 알고리즘 n을 입력 받는다....

Link https://www.acmicpc.net/problem/1977 Note M ~ N 사이에 존재하는 완전 제곱수를 찾아 수의 합과 최소값을 출력하자. 완전제곱수의 개념만 알면 쉽다. 최적화도 가능하지만 최대 범위가 100 이기 때문에 1부터 진행하자. 1부터 제곱 했을때 M ~ N 사이에 있다면 합에 더하고 최소값을 갱신한다. 알고리즘 ...

Link https://www.acmicpc.net/problem/1789 Note 서로 다른 N개의 자연수의 합으로 이루어진 n 이 주어질 때 N의 최대 값을 구하여라. 1 ~ X 까지의 합이 처음으로 n보다 커지는 X를 구하면 된다. 알고리즘 N을 입력 받는다. 1부터 1 씩 증가하며 ( i + 1 ) * ( i + 2 ) / 2가 n보다 커지...

Link https://www.acmicpc.net/problem/1904 Note 00 또는 1 로만 구성된 길이가 N인 2진 수열의 개수를 구하자 N이 5일 때 까지의 결과값들은 1, 2, 3, 5, 8 이다. 피보나치 수열이다. 알고리즘 n을 입력 받는다. 1 ~ 100만까지의 피보나치 수열을 구한다. 각각의 값은 15746으로 나눈 나머지로...

Link https://www.acmicpc.net/problem/1964 Note 그림과 같은 오각형의 점의 개수를 45678로 나눈 나머지를 출력한다. 그림 속 값이 늘어나는 일정한 규칙을 찾자. 과거 도형과 겹치는 부분을 제외하면 길이가 1 늘어난 변이 3개 존재하고 겹치는 점이 2개 존재한다. % 연산자의 특성을 고려해 결과값을 계산해 나가면 ...

Link https://www.acmicpc.net/problem/14890 Note N x N 지도가 주어졌을 때 l길이의 경사로를 놓아 지나갈 수 있는 경로의 갯수를 출력해준다. 경사로를 놓기 위해서는 높이의 차이가 1이어야한다. 또한 경사로는 겹쳐서 놓을 수가 없다. 범위를 벗어나서는 안된다. 경사로의 개수는 무제한이다. 위 조건을 만족 하기 위...

Link https://www.acmicpc.net/problem/6588 Note 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있는지를 검증하는 프로그램을 작성한다. 두 홀수 소수의 합을 구하기 위해서는 일단 소수를 구해야 한다. 에라토스테네스의 체를 이용하여 소수를 구한다. 짝수인 소수는 2 단 한개밖에 없다. 출력에 있어 b - a가...

Link https://www.acmicpc.net/problem/17103 Note 골드바흐의 추측 : 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 를 만족하는 경우의 수를 출력해주자. 소수를 구하기 위한 에라토스테네스의 체를 이용하면 된다. 두 소수가 같아도 된다. 알고리즘 에라토스테네스의 체를 이용하여 소수를 구한 후 저장한다. TC...

Link https://www.acmicpc.net/problem/1080 Note 0과 1로 이루어진 행렬 A B에 대해서 특정 연산을 통해 A를 B로 바꾸는 연산의 최솟값을 구하는 프로그램을 만들자. 처음에는 이 문제가 왜 그리디 알고리즘인지 궁금했다. 질문 게시판에는 이미 같은 생각을 가진 다른사람이 있었다. 0,0을 뒤집을 수 있는 경우는 0,...

Link https://www.acmicpc.net/problem/16236 Note 작고 귀여운 아기상어가 혼자 힘으로 물고기를 먹으며 얼마나 있는지 출력해주자. 삼성 A형 출제 문제 답게 문제를 열심히 읽어야한다. 다시 한번 더 느꼈다. 먼저 주어진 조건을 생각해보면 아기 상어는 자신의 몸집보다 작은 물고기만 먹을 수 있다. 아기 상어는 자신의 몸집...

Link https://www.acmicpc.net/problem/5670 Note 핸드폰의 자동 완성 기능과 비슷한 프로그램을 만들었을 때 평균 몇 회의 시도를 해야하는지 출력하자. 여러 문자열을 처리 해야하는 문제다. 앞서 풀었던 문제는 정적으로 처리 했던 것과는 다르게 동적 메모리가 필요하다. 트라이를 정적 메모리로 잡고 있기에는 메모리 낭비가 ...

Link https://www.acmicpc.net/problem/17143 Note 낚시왕이 낚시를 하며 잡은 상어 크기의 총합을 출력해주자. 시뮬레이션의 정석이라는 생각이 든 문제. 낚시왕은 1부터 가로의 끝까지 천천히 한칸씩 움직인다. 상어는 바라보고 있는 방향으로 자신의 속도만큼 움직인다. 벽에 부딪히는 상황이 오면 상어는 방향을 바꿔 남은 거...

Link https://www.acmicpc.net/problem/17144 Note 미세먼지와 공치청정기가 있는 환경에서 미세먼지가 확산과 이동이 t번 반복 후 남아있는 미세먼지를 출력하자. 미세먼지가 퍼지는 방법, 공기청정기를 기준으로 공기의 이동까지 크게 예외를 생각할 부분이 없다. 미세먼지 확산 시 상하좌우를 확인 후, 미세먼지의 감소 양이 정...

Link https://www.acmicpc.net/problem/2206 Note 벽을 한번 부술 수 있는 상태에서 0,0 에서 n,m 으로 갈 수 있는 최단 거리를 출력해주자. 과거에 비슷한 유형의 문제를 푼 적이 있다. 방문 체크를 할 때 벽을 부순 상태에 따라서 사용해야 하는 방문체크 변수가 다르다. 같은 위치에서 벽을 부수고 왔거나 부수지 않고...

Link https://www.acmicpc.net/problem/1967 Note 트리의 최대 지름을 출력해주자. 어떤 경우가 트리의 지름이 최대가 되는지를 생각하는 것이 가장 어려운문제. 질문 게시판에서 해답을 얻었던 문제. 루트노드에서 갈 수 있는 최장 거리 노드는 무조건 리프노드가 된다. 그렇다면 최장 거리에 있는 리프노드를 기준으로 가장 멀리...

Link https://www.acmicpc.net/problem/6118 Note 수혀니와 재서기가 숨바꼭질을 할 때 가장 멀리 있는 지점 중 가장 작은 번호와, 거리, 같은 지점의 개수를 출력해주자. 가중치도 없고, 단순히 거리만 있는 문제이기에 크게 생각할 점이 없다. 최대 지점의 수가 2만이기에 인접 행렬을 사용하지 않아야 한다. 최소 거리만 ...

Link https://www.acmicpc.net/problem/11437 Note 1을 루트로 하는 트리가 주어질 때 두 정점의 가장 가까운 공통 조상의 번호를 출력한다. LCA를 처음 공부할 때 개념을 잡기 좋은 문제라고 한다. 다른 블로그를 돌아다니면서 개념을 익힐 때 왜 깊이를 DFS로 설정해 주는지 의문을 가졌었다. 예제를 직접 노트로 옮겨...

Link https://www.acmicpc.net/problem/1761 Note 가중치가 있는 트리가 주어질 때 두 정점 사이의 가중치의 합을 출력한다. 기존 LCA문제에서 가중치가 추가된 LCA문제. 단지 루트 노드가 지정이 되지 않았기에 어느 노드를 기준으로 깊이를 설정해도 상관은 없다. 가장 일반적이게 1번 노드를 기준으로 깊이를 지정했다. ...

링크 https://www.acmicpc.net/problem/1931 Note 한개의 회의실과 회의 일정이 주어질 때 회의가 겹치지 않게 최대한 많이 배정 할 수 있는 수를 구하여라. 문제 자체에서 그리디 알고리즘이라는걸 알 수 있는 문제였다. 정렬을 이용하면 쉽게 해결 될 꺼 같은 문제 였는데 감이 잡히지 않아 고생좀 했었다. 종료 시간을 기준으로...

Link https://www.acmicpc.net/problem/2217 Note k개의 로프 정보가 주어질 때, 로프를 사용하여 들어 올릴 수 있는 최대 중량을 계산하여라. 알고리즘에 있어 크게 생각할 부분은 없었다. 각 로프 입장에서는 자기가 들 수 있는 값보다 큰 값을 들어올리지는 못하기 때문에 자기 자신을 기준으로 자기보다 많이 들어 올릴 수...

Link https://www.acmicpc.net/problem/1946 Note 한 지원자의 서류 심사 성적과, 면접시험 성적중 적어도 다른 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙 하에 지원자를 선발할 때 선발 할 수 있는 최대 인원 수를 구하여라. 되게 간단한 듯 보이면서 많이 틀렸던 문제다. 서류 심사 성적을 기준으로 정렬을...

Link https://www.acmicpc.net/problem/1543 Note 영어로만 이루어진 문서가 주어질 때 검색하고 싶은 단어가 중복되지 않게 몇번 등장하는지 알아보자. 문제의 난이도에 비해 정답률이 낮은게 의문이었다. 아마 원인은 String 클래스의 find 함수나 indexOf 함수를 이용하며 생기는 검색 속도 문제일꺼 같다. 이번 ...

Link https://www.acmicpc.net/problem/14500 Note 1x1 정사각형 4개로 이루어진 테트로미노를 n x m 크기의 종이에 최대한 배치 할 때, 테트로미노가 놓인 칸의 수의 합을 출력해준다. 일단 이 문제를 보았을 때 떠올린 방법은 나올 수 있는 모든 경우의 수를 배열에 넣어 배치하는 방법밖에 안떠올랐다. 이 후, 다른...

Link https://www.acmicpc.net/problem/17136 Note 10 x 10 의 판에 1 이 적힌 부분을 덮기 위해 필요한 색종이의 수를 구하여라. 삽질에 삽질에 삽질을 했던 문제. 타임아웃 문제를 해결해야 했던 문제도, 그리디로 처리해 오답이 나온 경우도 있었다. 타임아웃의 경우는 한 위치에서 5x5 색종이가 놓는게 가능하다 ...