https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 트리 알고리즘이라고 쓰기는 했지만, DFS, BFS 문항 중 가장 기본 문제인 것 같다. 실버2에 랭크되어 있는 것에 비해 아직 숙련도가 많이 부족해서 입력값 정리, 알고리즘 전개 방식 등 다방면에서 많이 헷갈리더라. 지난번에 포스팅했던 내용과 큰 차이는 없지만 이렇게까지 기억이 안나는 걸 보면 복습이 확실히 중요한 듯싶다. 백준 티어 실버1으로 올랐다. 조금..
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 본격적으로, BFS - DFS 문제들이 등장한다. 어떤 식으로 작동하는지는 책을 통해 공부한 바가 있지만, 실질적으로 구현해보지는 않아서 구글링을 통해 몇 번 연습한 뒤 문제 풀이에 임했다. 우선 느낀 점은 단순히 알고리즘을 구현하는 일과 그걸 직접 문제에 적용시키는 일은 정말 다르다는 점이다. 거의 3시간을 BFS, DFS에 쏟을 정도로 오래 걸리더라. 남의 코드를 직관적으로 이해하는 능력이 조금 부족해서 공부의 효율이 떨어지는 듯한다. 내가 구현해 본 BF..
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 어젯밤에 이진트리 알고리즘 구현 공부를 하다 자서, 감이 올라왔을 때 한 문제라도 풀어보는 게 좋을 것 같아 트리 알고리즘 중에 가장 쉬운 난이도를 골랐다. 확실히 구현 자체와 문제 풀이 간의 차이는 존재하더라. 노드 클래스와 트리 클래스를 정의해서 긴 호흡으로 끌고 가는 게 당연하다고 생각했는데, 생각보다 풀이는 단순하더라. # PYTHON CODE (1) import sys n = int..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수를 구하는 알고리즘은 '에라토스테네스의 체'라는 이름으로 널리 알려져 있다. 밑의 코드에서도 구현하겠지만, 간단한 원리는 소개하는 게 좋을 것 같다. 1. 소수면 True, 아니면 False로 구성된 리스트를 만든다. 2. n ** 0.5 까지 반복문을 돌면서 소수면 그 배수들을 전부 False로 바꾼다. 3. 리스트에서 n까지 반복하며 값이 True인 인덱스를 구한다. 복잡한 듯 싶지만 꽤 간단하며 원리도 직관적이다. 이 문항은 에라토스테네스의 체와 두 포인터가 합쳐진 문젠데, 각각의 개념 자체는 어렵지 않지만..
0. 일주일 동안 블로그를 신경 쓰지 못했다. 핑계 아닌 핑계를 대자면, 내가 작성한 코드를 ColorScript를 통해서 업로드 중이었는데, 깨짐 현상과 줄 간격이 라인 넘버와 맞지 않는 현상이 너무 많이 발생해서 다른 해결책을 강구해야 했다. 그러던 중 티스토리에서 제공하는 코드 블럭을 알게 되었는데, 라인 넘버, 하이라이트, 폰트 등 html/css를 이용해 수정해주면 깔끔하고 더 효율적인 코드 작성이 가능하더라. 문제는 각종 블로그에서 지시하는 대로 따라갔는데도 원하는 스타일이 안 나와서 한참을 헤매다가 오늘에서야 그럴듯한 모양새가 잡혔다. 지난주는 주간 주라 바쁘기도 했고, 코드 첨부 문제도 있었고... 여러모로 험난했다. 그래도 문제는 꾸준히 풀었기 때문에 오늘 그동안 푼 문제들 정리도 할 겸..
https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net output이해를 잘못해서 조금 돌아갔지만, 결과값 s가 아닌 새로이 벼열한 리스트를 return하는 방식의 문제 또한 충분히 좋았을 것 같다. color scripter를 이용해서 코드를 업로드하고 있었는데, 불규칙적으로 사이즈가 커지거나, 정렬 오류가 발생하는 경우가 종종 생겨서 다른 방식의 필요성을 느꼈다. html을 미약하게 공부한 상태라 자신감이 붙어서, 구글링으로 검색한 블로그들..
https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 정렬 알고리즘이긴 하지만, sort 함수의 쓰임새에 조금 더 치중된 문항이다. 이 문제를 푸는데 필요한 역량은, 1) sort함수의 문자열 정렬 기능을 알고 있는가 2) sort함수의 key기능을 알고 있는가 3) sort함수를 여러 번 사용한 경험이 있는가 정도가 될 수 있을 것 같다. 1, 2는 파이썬 기초 문법을 공부할 때 접한 기억이 있어서 자세히는 아니어도 무의식 속에 알고 있..
https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번에 사용한 정렬 알고리즘은 퀵정렬이다. 사실 어떤 정렬 알고리즘의 효율이 더 좋은지는 아직 시간 복잡도에 대한 이해가 부족하여 잘 모르겠지만, 우선은 다양한 알고리즘들을 실제로 사용해보는 것도 좋지 않을까라는 것에 의의를 두기로 한다. 보통의 정렬 알고리즘과 달리 이 문제는 내림차순을 요구하기 때문에 일반적인 풀이와는 미묘하게 다르다. 어느 부분을 수정해야하는지 사고하는 것도 의외로 단순하지만 재밌는 경험이었다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 ..
