https://www.acmicpc.net/problem/5639이 문제를 해결하기 위해서는 이진 트리의 특징과 전위 순회 특징에 대한 이해가 있어야 해결할 수 있는 문제이다.=> 즉, 트리의 특징을 제대로 이해했는지 확인하는 기본적인 문제이다.먼저 이진 트리의 특징을 간단하게 생각해보자.1. 2개의 자식 노드를 가진다.이 특징으로 인해 실제 자료구조를 구현 시 배열, 인접 리스트, 포인터 등을 고려해볼 수 있게 된다.또한 배열로 구현하게 된다면 Root 노드는 기본적으로 인덱스 1에 두는 방식을 사용하고 왼쪽 자식 노드는 2 * root index, 오른쪽 노드는 2 * root +1을 하게 된다.인접 리스트는 다른 방법을 생각해보야 하는데, 이 문제는 트리 구조를 입력 값으로 주지 않기 때문에 위 ..
보호되어 있는 글입니다.
https://www.acmicpc.net/problem/1967문제의 초점을 트리보다는 직관적인 부분을 고려해서 문제를 설명해보려고 한다.증명보다는 이미 알고 있는 지식, 직관으로부터 문제를 해결해보자.문제에서는 정점끼리의 가장 긴 길이를 물어보고 있다.위 그림에서 가장 긴 선은 무엇인가? A와 C를 잇는 선이다.왜? AC 선분이 제일 길까? 그냥 제일 길어서다.긴 선분보다 정점의 관점에서 다시 바라보자.가장 멀리 있는 정점 2개를 고르면 가장 긴 길이를 갖는 선분을 가지게 된다.그렇다면 가장 멀리있는 정점 2개를 어떻게 고를까?A에서 C가 가장 멀다.B에서 C가 가장 멀다. D에서 C가 가장 멀다. C에서 D가 가장 멀다.가장 먼 정점은 어느 정점을 골라도 2개로 좁혀진다.이에 대한 설명을 귀류법으로..
https://www.acmicpc.net/problem/1043지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일..
https://www.acmicpc.net/problem/17070문제를 읽다보면 입력 값에 N(3 ≤ N ≤ 16)란 정보를 알 수 있다. 해당 정보에 따라 무언가 백트래킹으로 해결이 가능함을 엿볼 수 있다.그도 그럴게 파이프는 계속 오른쪽으로 옮겨지니, 경우의수가 적지 않을까 싶은 생각도 있었다.다만 이전과 다르게 해당 문제는 파이프가 2개의 칸을 차지 하고 있는 이미지로 인해 어떻게 백트래킹을 구현할 수 있을지 고민이 된다.=> 2개의 좌표로 인해 백트래킹이 어렵다면, 일단 하나의 좌표로 백트래킹을 구현할 수 없는지 고민해보았다.결국 다음 좌표를 결정하는 것은 오른쪽, 아래 등 이동한 좌표의 지점이다. 그렇기 때문에 해당 좌표만 가지고 백트래킹을 구현해보면 간단하게 해결 가능하다.그리고 백트래킹을 ..
https://www.acmicpc.net/problem/15686생각의 흐름1.최대 M개를 고르라는 말의 의미는 무엇이지?=> 최대 M개를 안 고르는 경우도 있나?2. 치킨집을 제거한다고 하는 경우, 다른 치킨집의 거리에 영향이 가는가?=> 좌표로 계산하기 때문에 영향이 없음.=> 1번은 모르겠으나, 2번의 특성을 본다면, 모든 경우의 수를 탐색해서 계산하면 그만이겠다는 생각이 들었다.=> 조금 느릴 것 같은데, 빠르게 하는 방법은 없을까? => 그리디?근데 N이 50이라 워낙 수가 작아서 총 칸이 250이고, 집은 커봐야 2N이라 100 밖에 안 된다는 생각에 모든 경우의 수를 구하려고 했다.=> 마음에 걸리는 요소는 1번, M개 이건 뭐지?조합.. 😑 👍조합을 구현하고, 계산의 요소를 추가한 문..
https://www.acmicpc.net/problem/14442 문제 설명보다는 키포인트를 짚어보겠다. 1. 벽을 부수고 이동한다는 의미기본: 2차원 배열에서 상하좌우로 이동하며 최단 경로를 찾아간다. 응용: k번 만큼 막혀있는 길인 1을 뚫고 지나갈 수 있다. => K번 만큼 길을 뚫고 가는 상태를 visited 배열 상에 나타내야 한다. 어느 분의 말에 따른다면 뚫고 간 상태와 안 뚫고 간 상태를 나타내기 위해서는 차원이 늘어야 한다고 말을 한다. 말이 어렵긴 한데, 자연스럽게 생각해보면 좋을 것 같다.2. Enum 사용enum RoadType { ROAD, BLOCK }; 회사에 취직하기 전엔 코테에서 사용하지 않았던 문법인데 더 알아보기 쉽지 않나 싶어서 써보았다.3.배열의 크기를 미리 선언 ..
객체지향 5 원칙이라해서 프로그램이 견고하며 고치기 쉬운 상태가 된다는 뭐.. 그런 거다. 그런데 이 원칙을 막상 실제 프레임워크를 이용하는, 예컨데 스프링 부트에서 적용하려고 한다면 막막하거나 그런 코드를 본 적이 없지 않은가? 나는 이런 느낌을 이벤트 관련 서비스 개발을 맡았을 때 느꼈다. 첫 번째는 기간 내 1회 참여였으나 이후 1일 1회 참여도 가능하냐는 요건이었다. 처음 코드와 테이블 설계 자체가 기간 내 1회 참여였기에 곤란하다는 느낌도 있었다. 하물며 2가지 요구사항이 시간을 두고 들어와서 기존 코드를 고치는 데 겁이 났었다. 하지만 이 문제는 간단하게 Api의 로직 내 If문 추가로 끝난다. 그 이후 요건이 또 들어왔다. 원래 이벤트 참가 시 참가 기록 및 쿠폰 발급이있다. 새로운 기능인 ..