삼성전자
1.[백준] Python 1260 DFS와 BFS
삼성전자 코테를 위한 DFS,BFS 유형을 익혀야 한다.위는 링크텍스트 에 나와있는 DFS+BFS 필수 문제 리스트이다.단순 DFS와 BFS 함수를 구현해서 출력하는 문제다.여기서 주의해야하는 점은, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼
2.[백준] 2178 미로 탐색 Python
전형적인 탐색 문제로, BFS와 DFS를 사용하면 된다.보통, 최소 칸 수를 구하는 프로그램이라 BFS를 사용하면 된다.문제를 풀면서 고민했던 부분은, visited 배열을 만들어서 갔던 곳을 체크하고 얼만큼 이동했는지 알 수 있도록 cnt를 별도로 선언을 할까 고민했
3.[백준] 2606 바이러스 Python
쉽게 말하면 bfs 혹은 dfs를 실행해서 지나가는 노드 수를 count하면 된다.
4.[백준]2667 단지번호붙이기 Python
이 문제는 for문을 돌아가면서 BFS 또는 DFS 구현 시 return 값을 list에 저장 후 오름차순으로 정렬하여 프린트 하면 된다.graph 값을 바꿔가면서 수를 셀까 고민했는데 그냥 cnt를 선언하여 count하고, 지나간 값을 0으로 바꾸는 방식으로 구현했다
5.[백준] 2644 촌수계산 Python
그래프 탐색 문제이다. a,b가 주어졌을 때, 그 관계를 따져서 얼만큼 사다리를 거쳐서 갔는지를 계산하면 된다.문제는, a와 나머지 관계들에 대한 정보를 어떻게 저장해놓을까 고민했는데, 다행히 a와 b에 대한 관계를 문제에서 물어보고 있기에 a에 대한 촌수 관계 리스트
6.[백준] 7569 토마토 Python
평소에 2차원 리스트만 풀었는데, 이 문제는 3차원 리스트를 해야해서 조금 어려웠던 것 같다. 특히, z축을 어떻게 할까 고민이 많았는데 그냥 z축까지 추가하여 dz=0,0,0,0,1,-1 이런식으로 선언하고 for문을 6번 돌리면 된다. 나머지는 평소 bfs대로 구현
7.[백준]1697 숨바꼭질 Python
왜 이 문제가 BFS,DFS 문제인지 생각해 볼 필요가 있다. 먼저, 수빈이가 이동할 수 있는 경우는 세가지다. 이렇게 세 가지의 경우에 따라, 횟수가 진행되는 만큼 그래프가 그려진다. 따라서, 완전탐색 문제로 답을 찾아가야한다.코드를 짜면서 주의해야 하는 점은 for
8.[백준] 5014 스타트링크 Python
이 문제가 왜 BFS,DFS 문제인지 생각해야 한다. 먼저, up과 down을 눌러가면서 진행할수록 가지가 뻗어나간다. 즉, 그래프 문제이고 탐색을 하여 최소 버튼을 누르는 횟수를 구해야하기 때문에 BFS이다.한가지 주의해야할 점은 0 ≤ U, D ≤ 1000000
9.[백준] 2648 안전영역 Python
이 문제를 처음 풀 때에는 복잡하게 풀었던 것 같다.반복문을 얼마나 반복했는지 모른다.이 문제는 map의 가장 작은 수 부터, 가장 높은 수-1까지 반복문을 돌려 bfs를 몇번 실행하게 되는지 count를 하여 제일 큰 안전영역의 수를 return 해야한다.여러 배열을
10.[백준] 2573 빙산 Python
문제를 풀면서 복잡하고 어렵다고 느낀 문제였다. 처음에는 반복문을 써서 노가다?구현을 했는데 시간초과가 나서최대한 반복문을 돌지 않으려고 빙산 구역을 저장하고, 그 부분만 돌았다.문제를 구할 때, 중요한 부분은 빙산 bfs를 먼저 하고 빙산을 깎아줘야한다. 문제에 처음
11.[백준] 9205 맥주 마시면서 걸어가기 Python
처음에는 상하좌우를 탐색하면서 진행해야하나 생각했지만, 다른 사람들의 풀이를 보니 편의점과의 거리를 체크하면 되는 것이였다.BFS 함수를 구현할 때, 홈의 위치를 먼저 넣어주고, 꺼낸 뒤 =<20x50=1000 이면 return True를 해주도록 했고, 되지 않
12.[백준] 16236 아기 상어 Python
먼저, 이 문제가 왜 BFS인지 알아야한다. 삼성전자 코테 필수 유형 중 하나인 상어 시리즈 중 첫 문제를 풀었다.조건이 까다롭고 빡구현+BFS 유형이다. 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 이동할 수 있는 가장 가까운 물고기로 이동해야하기 때문
13.[백준] 14503 로봇청소기 Python
전형적인 구현 문제인데 조건이 조금 까다롭고 방향성을 고려해야하는 문제이다. 또한, 이 문제가 BFS를 사용해야 하는 이유는 여러 방향을 다 탐색하기 때문이다.먼저,로봇 청소기의 방향은 북,동,남,서 순으로 0,1,2,3이다.먼저,4칸을 for문을 통해 둘러보고 청소되
14.[백준] 19236 청소년 상어 Python
아기 상어에서 발전된 문제이다. 먼저, 물고기가 순서와 방향성이 매겨져 있고, 물고기가 순서대로 움직이고 상어가 움직이는 것이다. 이 문제에서 왜 DFS가 쓰였을까 생각을 하면, 물고기가 움직인 후 상어가 움직일 때 상어가 먹을 수 있는 물고기 번호의 합이 최댓값이 되
15.시계방향, 반시계 방향 회전 Python
삼성전자 코딩테스트에 자주 빈출되는 코드를 외워두려고 한다.90도 회전(i,j) -> (j,n-i-1)즉, newj=graphi가 된다.180도 회전(i,j) -> (n-i-1,n-j-1)즉,newn-i-1= graphi270도 회전(i,j) -> (n-j-1,i)즉,
16.[SW Expert] 알파벳을 숫자로 변환 Python
이 문제는 간단하게 string을 받아 각 알파벳에 매칭해주는 문제다.사실 이 문제에서 문제를 푸는 것보다 더 중요한건 ord 함수를 알아가는 것이다.ord는 아스키코드를 숫자로 변환해주는 형태로 주로, A=65, a=97임을 명심하자!따라서, ord('A')-65+1
17.[SW Expert] 초심자의 회문 검사 Python
이 문제는 앞으로 읽으나 뒤로 읽으나 똑같은 회문에 대한 내용이다.처음에는 문자열 길이를 반으로 나누어, 앞과 뒤 각각 하나씩 읽어서 같을 경우 continue, 다를 경우 0을 출력해서 break하도록 풀었다.그런데, 다른 풀이를 찾아보니 ::-1 방법을 찾았다.보통
18.[SW Expert] 백만 장자 프로젝트 Python
처음에는 리스트의 최댓값을 찾아 그 차이를 더해주면 된다고 생각했는데, 세번째 예시에서 중간에 팔고 다시 산 뒤,파는 경우가 최대 이익이 되는 경우가 있었다.따라서, 리스트를 반대로 ::-1부터 순회하여 계산했다.만약, 최대값보다 크면 값을 갱신해주고, 크지 않은 경우
19.[SW Expert] 달팽이 숫자 Python
예전에 이런 문제를 푼 기억이 나는데 어떻게 구현해야할 지 고민하다가 정말 쌩노가다로 구현으로 풀었다ㅋㅋ,,다른 풀이를 참고하니 간단했다. 처음에 dx,dy를 활용해야겠다고 생각했는데 네 방향을 잡고 시작했다. 한가지 고민했던 점이 (남,서),(북,동)이 짝인걸 알았
20.[백준] 1463 1로 만들기 Python
처음에는 bfs로 풀면 되지 않을까 싶어서 from collections import deque를 사용해서 풀었다.하지만, 시간초과가 났다. 아마 문제 조건에 n이 10의 6승이라서 계산하는데 시간이 드는 것 같다.개선해서 푸니깐 또 풀렸다.그래서 dp로 풀어봤다.