CodeLog

문제 링크: https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/549/ Problemevery element in nums(array of int) appears twice except for one. find that single one.nums(정수 배열) 내의 모든 element는 1개를 제외하고 2번 나타난다. 1번 나타나는 single num을 찾아라.Required Complexitytime complexity = O(n)입력 크기 n에 비례하여 처리, 배열/리스트를 1회 순회하는 수준을 기대space complexity = constant(O(1))입력크기 n과 관계없이 추가 메모리를 거의 쓰지 ..

Code Log에 무려 마지막 글을 쓴 지 3년만에 돌아왔다. 알고리즘 공부와 코딩테스트 관련 글을 정리하던 대학생 코드에이블은 원하는 회사에 합격해서 지금은 웹 개발자로 성장중이다. 바쁜 업무에 적응하느라 잠시(잠시라고 하기에는 꽤나 긴 시간동안) 접어두었던 블로그 포스팅을 다시 시작했다. 현재 회사와 업무에 매우 만족중이지만- 개발자로서 계속 성장하고 도전하고자 알고리즘과 코딩테스트를 다시 공부해보겠다는 계획을 세웠기 때문이다. 현직자지만 코딩테스트는 기초부터 탄탄하게 다시 해볼 생각이기 때문에 프로그래밍 공부 방법이 궁금한 개발자 꿈나무 분들도 참고하면 좋을 것 같다. 너무 오랜만에 들어왔는데 생각보다 그동안 많은 분들이 찾아주셔서 다시 열심히 적어봐야 겠다는 의욕이 생겼다 -!(감사합니다-) 1...

최근 삼성전자 자기소개서를 작성하느라 오랜만에 포스팅을 하게 되었다. 이제 코딩테스트를 앞두고 삼성전자 SW역량테스트 빈출문제인 BFS, DFS를 중점으로 포스팅할 예정이다. 이번 포스팅은 BFS(Breadth First Search), DFS(Depth First Search) 개념과 문제를 풀기 전 알아야 하는 사전 지식에 대하여 작성해보려 한다. 1. BFS(너비 우선 탐색, Breath First Search) BFS는 트리나 그래프를 방문 또는 탐색하는 방법이다.(트리의 경우 루트, 그래프의 경우 하나의 정점으로부터 시작해서 모든 노드, 정점을 방문한다.)트리와 그래프를 탐색하는 방식은 크게 DFS, BFS 두 가지인데 DFS에 대한 개념은 를 참고하기를 바란다. 너비 우선 탐색은 말 그대로 시..

백준 알고리즘 문제 원본 보기 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝..

백준 알고리즘 문제 원본 보기 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) 출력 강의실의 개수를 출력하라. 예제 예제 입력 1 예제 출력 1 3 1 3 2 4 3 5 2 아이디어 우선 가장 적은 강의실을 사용하여 수업을 배치..

백준 알고리즘 문제 원본 보기 문제 병든 나이트가 N × M 크기 체스판의 가장 왼쪽 아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자. 입력 첫째 줄에 체스판의 세로 길이 N와 ..

백준 알고리즘 문제 원본 보기 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어 한다. 미르코를 도와 그가 만들고 싶어 하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. 예제 예제 입력 1 예제 출력 1 30 20 예제 입력 2 예제 출력 2 102 210 예제 입력3 예제 출력3 2931 -1 예제 입력4 예제 출력4 80875542 88755420 아이디어 어..

백준 알고리즘 문제 원본 보기 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다. 여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야 하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다. 입력 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ ..