문제 보기: https://www.acmicpc.net/problem/1432 문제 이해하기예제 입력이 예제 출력으로 이어지는 과정이 문제에서는 N개의 정점으로 이루어진 그래프에서 모든 간선이 V1 -> V2 형태로 주어질 때, 모든 간선이 V1 2 조건을 만족하도록 각 정점에 번호를 새롭게 부여한 뒤, 새로 정해진 번호들의 결과 수열을 출력해야 하는데요. 만약 여러 개의 답이 존재한다면 사전 순으로 가장 앞선 것을 출력합니다. 먼저, 문제의 조건을 만족하는 번호를 각 노드에 부여할 때 쉽게 떠오르는 아이디어는 간단한데요. 조건을 위반하는 간선이 있다면, 그 간선이 연결하는 두 노드의 번호를 서로 교환하면 된다는 생각을 할 수 있습니다. 하지만 이 접근 방식에는 근본적인 문제가 존재합니다. 특정 간선이 ..

문제 보기 : https://www.acmicpc.net/problem/10000 문제 이해하기이 문제는 바깥 영역을 포함하여 서로 교차하지 않는 원들이 만들어내는 총 영역의 개수를 구해야 합니다. 아래 그림처럼 원들이 바깥 또는 안으로 접해있을 수도 있고, 안에 포함하고 있을 수도 있습니다. 그러면서 각각의 원마다 영역이 하나씩 생기게 됩니다.이때, 아래 그림처럼 어떤 원(부모 원)의 내부에 있는 자식 원들이 연속적으로 이어져서 부모 원의 지름을 꽉 채우는 경우, 부모 원에 대한 영역이 기존의 한 개가 아닌 두 개가 생기게 됩니다.이런 식으로 최대 30만 개의 원이 저런 관계들을 가지며 존재하는 상태에서 만들어지는 총 영역의 개수를 구해야 합니다.  핵심 아이디어이 문제의 핵심은 부모-자식 원 간의 관..

문제 보기 : https://www.acmicpc.net/problem/9079 동전 게임 문제의 핵심 아이디어3 x 3 보드의 각 칸에 동전들이 놓여져 있는 상태를 받은 다음 특정 행, 열 또는 대각선의 칸을 뒤집어 모든 칸의 동전을 앞면 혹은 뒷면으로 만들어야 합니다. 이 문제를 해결하는 단순한 방법은 그저 계속 뒤집어서 모든 면을 앞면(또는 뒷면)으로 만드는 것인데요. 이때 한 상태에서 뒤집는 경우의 수는 총 8가지가 나옵니다.즉, 각 칸을 0~8 까지로 정의했을 때 한 행을 뒤집는 경우 - (0,1,2),(3,4,5),(6,7,8), 한 열을 뒤집는 경우 - (0,3,6), (1,4,7), (2,5,8), 한 대각선을 뒤집는 경우 - (0,4,8), (2,4,6) 8가지 경우의 수가 존재합니다. ..

문제 보기 : https://www.acmicpc.net/problem/1967 트리의 지름 문제의 핵심 아이디어사이클이 없는 무방향 그래프인 트리가 존재하고, 이 때 어떤 두 노드를 선택해도 둘 사이의 경로는 오직 하나만 존재하는데요. 이 때 임의의 두 노드를 선택해 양쪽으로 당길 때 가장 길게 늘어나는 경우, 이 두 노드 사이 경로의 길이를 '트리의 지름'이라고 합니다. 즉 임의의 두 노드 간의 가장 긴 경로 합을 구하는 것이 이 문제의 요구사항입니다. 그러고 나서 문제는 트리의 지름을 이루는 두 노드와 그 안에 있는 나머지 노드들로 이루어진 원 형태의 그림을 보여주는데요, 이 그림이 바로 문제를 푸는 핵심이라고 할 수 있습니다.  그림을 보면 트리의 모든 노드는 이 원 안에 위치합니다. 다시말해 어..

https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 분석하기(1) 주어진 입력N : 전체 스테이지 개수stages : 게임 이용자가 멈춰있는 스테이지 배열(2) 주어진 조건N은 1~500의 자연수stages의 length는 1~200,000각 stage 는 1~N+1의 자연수자연수는 현재 도전중인 스테이지. 즉 이전 스테이지까지 다 깼음을 의미예를 들어 N+1은 마지막 스테이지(N)까지 클리어한 사용자 (3) 구하는 것 : 각 스테이지의 실패율(해당 스테이지에 머무르고 있는 이용자 수 / ..

알고리즘 문제를 잘 푸는 방법이 따로 있을까?알고리즘 문제를 어떻게든 빨리 풀어보려고 요구 사항을 대충 슥 읽고 코딩에 들어가본 적이 있으신가요? 그 결과는 어떠셨나요?정말로 그렇게 해서 성과를 거둔 상황보다는, 내가 짠 알고리즘에 대해 스스로도 이해하지 못한 채 코드로 옮기다 중간에 턱 막히거나 어찌저찌 완성하더라도 핵심 요구 사항을 빼먹는 경우가 대부분일 것이라고 생각합니다. 그러고 나면 왜 안되는 거지? 머리를 싸매다가 정답을 보고 여기 고치고 저기 고치고 해서 찜찜하게 마무리되고 맙니다. 실제 제가 겪었던 경험을 토대로 상황을 설명했지만, 이런 경험을 한 번이라도 해 본 적이 있다면 알고리즘 문제를 해결하는 데 있어 그저 마구잡이로 코딩에 들어가서는 안된다는 것에 대해 충분히 공감하실 것이라 생각..